43. Канонический метод синтеза микропрограммных автоматов Мили

Отметки внутренних состояний автомата Мили по закодированной ГСА выполняются по следующим правилам:

1. символом отмечается вход первой вершины, следующей за начальной, а также вход конечной вершины;

2. входы вершин, следующих за операторными вершинами, отмечаются символами ;

3. входы двух различных вершин, за исключением конечной, не могут быть отмечены одинаковыми символами;

4. вход вершины может отмечаться только одним символом.

Внутренние состояния автомата Мили отмечены на дугах ГСА (рис. 5.7).

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

Структурные таблицы по существу задают граф переходов автомата в виде списка, что является более компактной, но менее наглядной формой задания закона функционирования автомата.

Прямой структурной таблицей автомата Мили для ГСА на рис. 5.7 является таблица 5.1

Таблица 5.1 – Прямая структурная таблица для автомата Мили

В таблице 5.1 h-указывает номер строки; – исходное состояние автомата для такта t; – двоичный код состояния ; – состояние перехода для момента времени t+1; – двоичный код состояния перехода; – условие перехода для строки h; – выходной сигнал на переходе из в для строки h; – сигналы возбуждения входов триггеров.

Следует отметить, что по сравнению с таблицами переходов и выходов цифрового автомата Мили структурная таблица является их расширением, так как содержит три дополнительных столбца и . Столбец h может отсутствовать в таблице, но его присутствие позволяет осуществить нумерацию переходов и облегчает анализ таблиц. Столбцы и окончательно оформляются после выполнения этапа кодирования внутренних состояний автомата.

Рисунок 5.7 – Разметка ГСА по Типу автомата Мили

Структурная таблица автомата по существу является списочной формой (списком) представления графа переходов автомата, но более компактна по сравнению с ним.

В ряде случаев, оказывается более удобным пользоваться обратной структурной таблицей автомата (таблица 5.2), в которой столбцы обозначены точно также, но сначала записываются все переходы в , затем в и так далее. Таким образом, в прямой структурной таблице автомата Мили ведущим является столбец , в обратной таблице ведущим является столбец .

Таблица 5.2– Обратная структурная таблица для автомата Мили

Теперь построим граф переходов для автомата Мили по табл. 5.2 или 5.1. Каждая строка таблицы соответствует дуге графа (рис.5.8).

Рисунок 5.8 – Граф переходов автомата Мили

Каждое состояние автомата должно быть как-то представлено в схеме, где-то храниться. Состояние кодируется двоичной последовательностью, которая хранится в триггерах. Каждому новому состоянию соответствует своя уникальная двоичная последовательность, чтобы состояния были различимыми.

Минимальное число триггеров для хранения состояний, определяется выражением

,

где n – число триггеров для хранения состояний;

k – количество состояний.

Как кодировать состояния? Существует большое количество методов кодирования, о которых речь пойдет позже. Сейчас рассмотрим алгоритм кодирования состояний, при условии использования D-триггеров. Целью такого кодирования будет минимизация сложности схемы, т.е. минимизация аппаратурных затрат.

Для уменьшения сложности системы, реализующей функции возбуждения D-триггеров лучше использовать частотный алгоритм кодирования состояний автомата. Этот алгоритм состоит из 5-ти этапов.

1. Каждому внутреннему состоянию автомата а_i ставится в соответствие целое число N_i, равное числу переходов в это состояние (N_i равно числу появлений состояния а_i в таблице переходов или числу стрелок, входящих в а_i в графе переходов).

2. Все числа N₁, N₂,… N_i,… N_М сортируются по убыванию.

3. Состояние a_t с максимальным значением N_t кодируется нулевой комбинацией, т.е. кодом k_t=00…00;

4. Следующие n внутренних состояний кодируются кодовой комбинацией с одной единицей: 00…01, 00…10,…

5. Оставшиеся незакодированные внутренние состояния кодируют вначале комбинациями с двумя единицами, затем с тремя и т. д., пока все состояния не будут закодированы.

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

Подобные соображения могут быть использованы при кодировании выходных сигналов для минимизации функции выходов.

Кодирование состояний по выше рассмотренному алгоритму сведено в табл. 5.3

Таблица 5.3– Кодирование состояний автомата Мили на D -триггерах

Граф переходов с закодированными состояниями приведен на рис. 5.9. На дугах графа указаны разряды, на которые имеются единицы кодов состояний, куда входят дуги.

Рисунок 5.9 – Кодирование состояний автомата Мили

Коэффициент качества кодирования определяется как отношение числа букв D на графе к общему числу дуг.

Заполненная прямая структурная таблица для автомата Мили представлена в табл. 5.4.

Таблица 5.4 – Прямая структурная таблица для автомата Мили

Функции возбуждения Z_к и функция выхода Y_l автомата Мили находят по полностью оформленной структурной таблице автомата в виде дизъюнктивных нормальных форм:

Z_к = V а_m·Х_h(а_m,а_s); к,

(а_m,а_s)  h;

Y_l = V а_m·Х_h(а_m,а_s); l,

(a_m,a_s)  h,

где n и m – число сигналов возбуждения и исходных сигналов автомата соответственно; h – номер строки структурной таблицы, в столбце F(а_m, а_s) которой есть отметка сигнала возбуждения Z_К или в столбце Y(а_m, а_s) - отметка исходного сигнала Y_l. Терм (логическое произведение) а_m Х_h(а_m, а_s) включают в выражение Z_к, если сигнал возбуждения Z_к есть в столбце F(а_m, а_s) h-й строки таблицы автомата Мили.

Аналогично терм а_m X_h(a_m, a_s) нужно включить в выражение Y_l, если Y_l есть в столбце Y(a_m,a_s) h-й строки таблицы.

Функции выходов, исходя из таблицы 5.4, в базисах Буля и Шеффера будут иметь следующий вид:

Функции переходов, исходя из таблицы 5.4, в базисах Буля и Шеффера будут иметь следующий вид:

Далее можно строить функциональную электрическую схему автомата.

Рассмотрим реализацию схемы с преддешифрацией. В данном случае будем для формирования одноразрядного сигнала состояния использовать дешифратор, который будет преобразовывать двоичный код состояния в двоичный унитарный код, т.е. код, в котором только один сигнал будет активным, он и будет указывать на состояние, в котором находится автомат в течении рассматриваемого такта.

Для построения функциональной электрической схемы необходимо написать еще одно уравнение для формирования синхросигнала. Для этого предусмотрим сигнал запуска z, активное значение которого будет инициировать подачу синхросигнала C на элементы памяти. Уравнение имеет вид:

где z – сигнал запуска,

C – сигнал синхронизации, подаваемый на схему,

C’ – сигнал синхронизации с генератора тактовых сигналов.

Кроме того, необходимо предусмотреть установку элементов памяти в начальное состояние по включению питания. Для этого понадобятся две простые схемы, представленные на рис. 5.10 а и б.

а) б)

Рисунок 5.10 – Схемы сигналов установки триггеров в начальное состояние

На рис. 5.11 представлены временные диаграммы сигнала напряжения на обкладках конденсатора С, и сигналов А и В с выходов схем установки триггеров.

Рисунок 5.11 – Временные диаграммы сигналов А, В и U_C

Пока конденсатор заряжается, на выходе А держится значение 0, так называемый вынужденный 0. На выходе В – постоянное значение 1. В период t вынужденного нуля держится комбинация А = 0, В = 1. После зарядки конденсатора появляется комбинация А = 1, В = 1. Подключая сигналы А и В к установочным входам триггера. Можно обеспечить его установку в 0 (рис. 5.12 а) или его установку в 1 (рис. 5.12 б) по включению питания. В обоих случаях после зарядки конденсатора устанавливается комбинация А = 1, В = 1, которая позволяет триггеру нормально функционировать.

а) б)

Рисунок 5.12 – Подключение сигналов А, В к триггеру

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

Таблица 5.5 - Количество корпусов интегральных схем

Теперь можно изображать функциональную схему автомата (рис. 5.13). Порядок составления схемы следующий:

1. изображается шина (линии шины в 2 раза толще всех остальных линий) с входами и выходами – слева входы, справа выходы;

2. рисуются микросхемы, справа дешифратор и триггеры, слева все остальные;

3. нумеруются сначала входы (в нашем примере от 1 до 9), а затем выходы всех микросхем (в нашем случае от 10 до 42);

4. выходы триггеров подключаются ко входам дешифратора;

5. определяется, каким выходам дешифратора соответствуют все состояния;

6. реализуются уравнения для сигналов А, В, С и все инверсии состояний;

7. реализуются функции возбуждения триггеров и функции выходов;

8. нумеруются входы триггеров;

9. нумеруются выходные сигналы.

Рассмотрим реализацию схемы без дешифратора. В данном случае дешифратор использовать не будем. Состояние автомата будем представлять в виде конъюнкции выходных значений триггеров, взятых с отрицанием или без отрицания. Например, состояние имеет код 011, т.е. , где – выход соответствующего триггера. Тогда . Отрицание над Q_i ставится тогда, когда оно принимает значение 0 в коде состояния. Отрицательные значения выходов триггеров в схеме берутся с инверсных выходов триггеров.

Функции выходов и переходов в базисах Буля и Шеффера будут использоваться в том же виде, а для формирования сигналов состояний вместо дешифратора будем использовать комбинационную схему, описываемую следующей системой уравнений:

Далее можно строить функциональную электрическую схему автомата.

Оценим аппаратурные затраты (табл. 5.6).

Таблица 5.6 - Количество корпусов интегральных схем