6-7. ПРИМЕРЫ СИНТЕЗА КОНЕЧНЫХ АВТОМАТОВ

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

Сумматор последовательного действия

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

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

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

Здесь означает перенос из разряда в — перенос в разряд из

Система функций, полученная нами, есть система вида (6-31). Таким образом, сумматор последовательного действия является конечным автоматом. Роль здесь играет индекс Схема имеет два состояния (отсутствие и наличие переноса из младшего разряда) и один выход. Отсюда таблица-переходов и выходов имеет вид:

Рис. 6-18.

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

Так как эти уравнения формально полностью совпадают с соответствующими соотношениями для одноразрядной суммирующей схемы, полученными нами в гл. 3, то, учитывая связь между как это принято для РБФ-1, мы получаем функциональную схему для сумматора последовательного действия, показанную на рис. 6-18.

Схема сравнения на равенство

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

Рис. 6-19. (см. скан)

Выход схемы определяется следующим образом:

При этом можно считать, что состояние схемы и ее выход совпадают. Таблица, определяющая работу этого конечного автомата, имеет вид:

Отсюда имеем собственную функцию вида

Соответствующая функциональная схема приведена на рис. 6-19,а. На рис. 6-19, б показана реализация этой же схемы с использованием двухвходового триггера. Эта схема получена на основании применения соотношения (6-26) к полученной собственной функции, для которой

Схема сравнения на неравенство

Рассмотрим более сложный пример синтеза. Построй им схему сравнения «больше, меньше, равно». Схема имеет два входа и два выхода, На вход схемы подаются двоичные числа

Выходные последовательности:

определяют числа по следующему правилу:

если

если

если

Соответственно этому схема на каждом такте работы может находиться в одном из трех состояний: «равно» (0, 0), «больше» (0,1) и «меньше» (1,0). Для реализации трех состояний в схеме должны быть предусмотрены две обратные связи, которые, как и в схеме сравнения на равенство, могут быть взяты с выходов синтезируемой схемы. Числа и подаются на соответствующие входы, начиная со старших разрядов.

Опять считаем, что соответствующие выходы, схемы совпадают с двумя компонентами вектора состояний, т. е. рассматриваем конечный автомат Мура. Соответствующая таблица переходов — входов для этого автомата имеет вид:

Из этой таблицы вытекает, что

Соответствующая этим собственным функциям схема приведена на рис. 6-20.

Рис. 6-20

Сдвигающий регистр

На рис. 6-21, а показан разряд сдвигающего регистра. Регистр должен управляться тремя сигналами означающими соответственно параллельную запись числа на регистр, сдвиг записанного числа вправо и сдвиг записанного числа влево.

Рис. 6-21. (см. скан)

Пусть означает содержимое разряда регистра при параллельной записи в него числа из источника чисел, означает содержимое этого разряда после подачи некоторых команд сдвига (при этом допускается отсутствие команд сдвига). Если на регистр не подается ни одна из вышеперечисленных команд, то его содержимое должно сохраняться.

Из описания работы регистра следует, что

Соответствующая функциональная схема приведена на рис. 6-21, б.

Дискриминатор

Дискриминатором называется устройство, которое выдает на выходе единицу, если длительность единичного сигнала на входе не меньше . В § 6-2 мы рассматривали схемы, построенные на основе РБФ-2, которые решают подобную задачу (см. рис. 6-5, б и в). Однако, как там указывалось, эти схемы не всегда хорошо работают. Используя структуру конечного автомата, можно построить дискриминатор, свободный от недостатков схемы, построенной с помощью РБФ-2. Пусть, например, нам необходимо построить дискриминатор, выдающий единицу на выходе только при условии, что входной сигнал принимает единичное значение не меньше трех тактов подряд. Возьмем конечный автомат с четырьмя стояниями и следующей таблицей переходов:

В качестве автомата возьмем автомат Мура. Выходной сигнал в состояниях 0, 1, 2 равен нулю, а в состоянии 3 равен единице. В начальный момент устройство находится в нулевом состоянии. Как видно из таблицы переходов, в состояние 3 автомат попадет лишь при условии, что единица на входе будет сохраняться в течение трех тактов. Таким образом, на выходе схемы единица появится лишь при выполнении указанного условия. Обозначим вектор состояний как Если состояния автомата закодировать соответствующими двоичными числами, то выходной сигнал автомата определится следующей собственной функцией: а собственные функции, определяющие переходы, будут иметь следующий вид:

Схема дискриминатора показана на рис. 6-22.

Необходимо отметить, что проблема синтеза автоматов с памятью отличается от проблемы синтеза

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

Рис. 6-22.

Методы такой минимизации изложены в литературе, список которой дан в конце книги.