Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

под действием любого набора из Е^_м -класса автомат остается в том же состоя­

нии ат и при этом выдает выходной сигнал = (0 . . . 0). При R = 0 под дей­ ствием любого входного набора автомат переходит в то же состояние и выдает тот же выходной сигнал, что и под действием сигнала единицы, приписанного дуге графа автомата.

В качестве примера подобного разбиения рассмотрим автомат с L = 3 вход­ ными и N = 4 выходными каналами. Пусть из некоторого состояния ат этого автомата есть два перехода (рис. 5-4). Число элементарных произведений на вы­

5-2. Синтез микропрограммного автомата Мура

Синтез автомата Мура по граф-схеме алгоритма также состоит из двух этапов: получения отмеченной ГСА и построения графа автомата. На первом из них начальная, конечная и операторные вершины от­ мечаются символами аг, а 2, . . . , ам по следующим правилам:

1. Символом отмечаются начальная и конечная вершины.

2.Различные операторные вершины отмечаются различными сим­ волами.

3.Все операторные вершины должны быть отмечены.

При синтезе автомата Мура в отличие от автомата Мили отмечаются не входы вершин, следующих за операторными, а сами операторные вершины. Число отметок, таким образом, оказывается на единицу большим числа операторных вершин в граф-схеме алгоритма. В ре­ зультате применения рассмотренной процедуры отметки к ГСА на рис.. 4-5 получим отмеченную граф-схему, изображенную на рис. 5-5.

Построение графа автомата Мура начинается с нахождения в от­ меченной ГСА путей перехода вида

g

где emr (/' = 1, . . . , R) и x™ определяются так же, как и в формуле (5-1). Как и ранее, для краткости эти пути будем обозначать атХ (а.т,

74

as) as, причем если между аіп и as имеется несколько путей вида amXh (ат, as) as (h = 1, . . . , Н), то будем считать, что этому мно­

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

II т. д.

75

ходной. сигнал У,. Нетрудно проверить, что подграф автомата Мура, построенный по рис. 5-6, а, будет точно такой же, что и по рис. 5-6, б, в котором имеется всего один путь перехода из ат в as.

На рис. 5-7 приведен граф автомата, построенный по отмеченной ГСАна рис. 5-5.

Уе

5-3. Таблицы переходов микропрограммного автомата

При использовании графов для задания автоматов с большим чис­ лом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать эти графы в виде списков. В связи с этим введем понятие таблицы переходов микропрограммного автомата. В случае автомата Мили эта таблица (табл. 5-1) имеет четыре столбца.

Если между состояниями ат и as имеется переход под действием входного сигнала X (ат, as) с выдачей выходного сигнала У {а,п, a.s), то в первом столбце помещается ат — исходное состояние, во втором— состояние перехода as (состояние, в которое осуществляется переход), в третьем — входной сигнал X (аіп, as), а в четвертом — выходной

У> *7S).

Иногда на переходе (апп as) выдается не один, а множество выход­ ных сигналов — микрокоманд У (аш, as) = {У* (аш, as), . . . , У/ (а,„, as), .. . . , Уj (ат , fls)j, причем в общем случае один и тот же выходной

76

в таблице последовательно перечисляются все пути перехода, начиная

спутей, соответствующих Уг (ат , as). Для выходного сигнала Yj (ат , as) в таблице переходов будет Н строчек:

Прямой таблицей переходов микропрограммного автомата назо­ вем таблицу, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т. д. Табл. 5-1 яв­ ляется примером такой таблицы для автомата Мили на рис. 5-3. В ряде случаев оказывается удобным пользоваться обратной таблицей пере-

77