П5.5. Алгоритм синтеза цифрового автомата

1. Исходя из условий функционирования, определяют число необходимых состояний и требуемый объем памяти цифрового автомата. Число необходимых для реализации состояний определяется как наибольшее значение выходных кодов устройства, формируемых при одном значении входного сигнала. Объем памяти триггерной подсистемы определяется из условия, что n разрядный двоичный код может принимать различных значений. Тогда требуемый объем памяти, т. е. число необходимых триггеров подсистемы памяти определяется из условия:

где функция CEIL означает округление до ближайшего большего целого.

2. Выполняют формальное описание алгоритма работы автомата;

3. Выбирают тип триггера для реализации подсистемы памяти.

4. Используя формальное описание алгоритма работы автомата и таблицу переходов выбранного типа триггеров, составляют расширенную таблицу истинности, характеризующую работу комбинационной подсистемы автомата. Число строк этой таблицы равно максимальному числу входных сигналов, действующих на входе комбинационной подсистемы. В столбцах таблицы записывается следующая информация: Х [ n -1…0] – входной сигнал; S_n [ q –1….0] – текущее состояние автомата; S_{n +1}[ q –1…0] – последующее состояние автомата; Y [ k –1…0] - cигнал ПОС; Z [ m -1…0] – выходной сигнал автомата.

5. Используя расширенную таблицу истинности, минимизируют ФАЛ, описывающие работу комбинационной подсистемы автомата;

6. Используя полученные ФАЛ, синтезируют схему цифрового автомата.

Проиллюстрируем описание алгоритма работы автомата на примере.

Пример П5.1. Спроектировать устройство, формирующее на выходе следующие последовательности выходных кодов:

· при входном сигнале X = 1 – 000, 001, 010, 100;

· при входном сигнале Х = 0 – 100, 010, 001, 000.

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

1. Из заданного алгоритма работы следует, что при одном значении входного сигнала Х на выходе автомата может формироваться 4 кода. Следовательно, число необходимых состояний автомата . Для реализации такого числа состояний достаточно двух триггеров .

2. Синтезируем граф переходов, описывающий заданный алгоритм работы устройства. Обозначим состояния автомата окружностями и обозначим их как S 0, S 1, S 2 и S 3 (рис. П5.6). Используя граф переходов, составим таблицу состояний автомата. В таблице состояний обозначено S 0 = 00, S 1 = 01, S 2 = 10, S 3 = 11 (табл. П5.1).

3. Для реализации триггерной подсистемы можно использовать любой тип синхронного триггера, изменяющего своё состояние по фронту импульса сигнала синхронизации. Используемый тип триггера определяет схему комбинационной подсистемы автомата. Можно сформулировать некоторые общие закономерности выбора типа используемого триггера. При выборе триггера, управляемого двумя информационными сигналами (RS- и JK- триггера) увеличивается разрядность сигнала ПОС, однако, как правило, упрощается схема комбинационной подсистемы.

При выборе триггера с одним управляющим сигналом (D- и T -триггера) уменьшается разрядность сигнала ПОС, но усложняется структура комбинационной подсистемы. Учитывая сказанное, выберем для реализации подсистемы памяти Т -триггеры. Таблица П5.2 соответствует таблице переходов Т -триггера. Таблица П5.2. Таблица переходов Т -триггера Qn Qn+1 T

4. Составим расширенную таблицу истинности (табл. П5.3).

Таблица П5.3. Расширенная таблица истинности заданного алгоритма устройства

X	Sn	Sn+1	Y	Z

Поясним составление расширенной таблицы истинности. В первых двух столбцах таблицы записаны все комбинации фактически возможных входных сигналов комбинационной подсистемы автомата. Это входные сигналы Х и сигналы , формируемые подсистемой памяти в данный момент времени. Очевидно, сигнал S_n определяется комбинацией выходных сигналов триггеров подсистемы памяти, т.е. , где и - выходные сигналы триггеров под номерами 1 и 0.

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

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

Четвертый столбец содержит сигналы ПОС, которые должна формировать комбинационная подсистема для обеспечения заданного порядка переключения триггеров подсистемы памяти. Подсистема памяти в нашем случае состоит из двух Т -триггеров, поэтому сигнал - 2-разрядный код, где и соответственно информационные сигналы первого и нулевого триггеров подсистемы памяти. Значения этих сигналов можно получить из таблицы переходов выбранного типа триггера (см. табл. П5.2). Например, для первой строки расширенной таблицы истинности имеем и т.е. оба триггера должны переключиться. Из таблицы П5.2 имеем, что для перехода триггера из сброшенного состояния в состояние установки на его информационный вход необходимо подать управляющий сигнал . Поэтому сигнал (код) Y для этой строки равен 11.

Последний столбец таблицы П5.3 содержит значения выходных сигналов, которые для известных выбираются либо из графа переходов, либо из расширенной таблицы истинности.

5. Для завершения проектирования необходимо получить ФАЛ, описывающие поведение комбинационной подсистемы. Эти ФАЛ можно синтезировать из расширенной таблицы истинности, которая содержит всю информацию о входных и выходных сигналах подсистемы. Проведем минимизацию этих ФАЛ с использованием карт Вейча. На рис. П5.7 приведены соответствующие карты Вейча.

Используя полученные карты, запишем минимизированные ФАЛ для комбинационной подсистемы проектируемого устройства.

; ; ; ;

.

Преобразуем полученные выражения к базису элементов И-НЕ.

; ;

; .

6. Используя полученные ФАЛ и выбранный тип триггеров для реализации блока памяти, синтезируем схему проектируемого устройства (рис. П5.8)..

На схеме автомата триггер DD1 формирует сигналы и . Триггер DD2 формирует сигналы и . Для получения сигнала «лог.1» используется логический элемент DD3 (2И-НЕ), на вход которого подаются два сигнала нулевого потенциала, который принято считать сигналом «лог.0». Элемент DD4 используется как инвертор для формирования сигнала .

Рис. П5.8. Схема синтезированного автомата

Элементы DD5, DD6 и DD13 формируют сигнал , управляющий работой триггера DD1. Элементы DD7…DD12 и DD14…DD16 формируют выходные сигналы автомата Z.

Приложение 6