Пример структурного синтеза автомата Мили

Зададим автомат Мили таблицами переходов и выходов (рис.6):

Рисунок 6. Исходный КА Мили

1. Выбираем в качестве элементов памяти JK - триггеры. Базис ло­гических элементов - произвольный.

2. Для данного примера очевидно:

к = 4 - число внутренних состояний (а_к);

р = 3 - число входных сигналов (Z_i);

s=3- число выходных сигналов (W_I).

3. Находим:

- число элементов памяти r > log ₂ k = log ₂ 4 = 2;

- число разрядов входной шины n > log ₂ p = log ₂ 3 = 2;

- число разрядов выходной шины m > log ₂ s = log ₂ 3 = 2.

4. Кодируем автомат, ставя в соответствие каждому символичес­кому сигналу произвольный двоичный код (число разрядов кода со­ответствует найденным r, n, m).

Таблица 4 – Кодировка автомата Мили

С учетом введенных кодов переводим таблицы переходов и выходов в двоичный алфавит (рис.7).

Рисунок 7. Двоично-кодированные таблицы КА Мили

4. По таблице выходов λ составляем логические уравнения для выходных сигналов у₁ и у₂. Учтем, что в каждой клетке таблицы левый бит характеризует сигнал у₁, правый - у₂. Записывая уравнения " по единицам", получаем СДНФ:

5. Преобразуем таблицу переходов автомата в таблицу возбуждения памяти. Для обеспечения каждого отдельного перехода из исходного состояния памяти в последующее нужно подать на входы элемен­тов памяти (синхронных триггеров) определенные сигналы. Именно эти сигналы и заносятся в соответствующие клетки таблицы возбуждения памяти.

На рис.8 для примера рассмотрены возможные переходы в первом столбце таблицы переходов (состояния входов х₁х₂ на данном этапе несущест­венны):

Рисунок 8. Пример переходов КА Мили

Выделим первое возможное изменение состояния Q₁Q₂: 00→ 00. По­скольку каждый бит характеризует состояние выхода отдельного JK-триггера, то согласно таблице возбуждения такого триггера для перевода его выхода из состояния 0 в состояние 0 (т.е. сохранение состояния) необходимо подать на вход J сигнал 0, а на вход К - все равно нуль или единицу. Безразличное состояние входа изображается прочерком в таблице возбуждения памяти. Это иллюстрируется рис. 9:

Рисунок 9. Заполнение таблицы возбуждения памяти

Ясно, что переход второго триггера должен быть отображен аналогичной комбинацией его входных сигналов (на рисунке не показано).

При переходе памяти в следующее возможное состояние процесс показан на рис.10:

Рисунок 10. Переход памяти в следующее состояние

Окончательный вид таблицы возбуждения памяти автомата после рассмотрения переходов по всем столбцам приведен в таблице 5.

Таблица 5 – Таблица возбуждения памяти, выполненной на JK- триггерах

Если в качестве элементов памяти использовать Т-триггеры, то таблица возбуждения памяти будет иметь более простой вид, так как Т-триггер имеет один информационный вход (таблица 6).

Таблица 6 – Таблица возбуждения памяти, выполненной на Т- триггерах

В случае использования D-триггеров таблица возбуждения памяти повторяет таблицу переходов.

6. По таблице возбуждения памяти (для JK-триггеров) составляем логические уравнения сигналов на каждом информационном входе каж­дого триггера. Записывая их " по единицам”, получаем следующие СДНФ:

7. Минимизируем уравнения, полученные в пп.4 и 6, при помощи карт Карно. Так как функции переходов и выходов не определены на некоторых наборах аргументов, доопределяем карты Карно на этих на­борах единицами или нулями с целью проведения контуров наиболее высокого ран­га (положение этих единиц отмечено на картах символом *). Так, для y₁ и y₂ карты Карно имеют вид рис. 11:

Рисунок 11. Карты Карно для выходных сигналов

Записываем минимальные ДНФ:

Проводя минимизацию остальных функций, получаем следующие функции:

8. По полученным минимальным формам составляем логическую схе­му автомата на микросхемах выбранной серии. Этот процесс сложности не представляет, поэтому приведем только функциональную схему автомата Мили (рис.12).

Рисунок 12. Функциональная схема КА Мили