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

ходов, в которой столбцы обозначены точно так же, но сначала запи­ сываются все переходы в первое состояние, затем во второе и т. д. (табл. 5-2 для того же автомата).

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

Таблица 5-3

Прямая таблица переходов автомата Мура

78

Продолжение

Таблица 5-4

Обратная таблица переходов автомата Мура

79

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

5-4. Минимизация микропрограммных автоматов

Изложенный в первой главе метод минимизации полностью опреде­ ленных абстрактных автоматов можно модифицировать для миними­ зации микропрограммных автоматов. Напомним, что два состояния автомата Мили будут одноэквивалентными, если под действием оди­ наковых входных сигналов они выдают одинаковые выходные сигналы. В связи с этим для выяснения одноэквивалентности состояний а,- іГаумикропрограммного автомата необходимо сравнить множества микро­ команд, выдаваемых на переходах из этих состояний. Пусть, например, эти множества совпадают и равны {Уф, . . . , У,, . . . , Уг ), причем микрокоманда Y t выдается под действием сигналов X t (У,) и Аф (У,) для состояний а,- и ау соответственно. Тогда, очевидно, aL и a-t будут

Два состояния at и а:- микропрограммного автомата будут /«-экви­ валентны, если выполняются следующие условия:

1 Проверка эквивалентности двух булевых функций, заданных в некотором виде, отличном от совершенной дизъюнктивной нормальной формы, может быть осуществлена с помощью операции вычитания кубических покрытий [17’].

80

Таблица 5-5

Автомат Мили, построенный по ГСА на рис. 5-8

лучаем множество А' = (ах> а3, а4, ав, а8) состояний минимального микропрограммного автомата Мили. При выборе представителя из некоторого класса в Л ' целесообразно выбирать состояния с наимень­ шим числом строчек в таблице переходов, именно поэтому из класса С2 взято а4. Таблица переходов минимального автомата (табл. 5-8) получена из табл. 5-5 вычеркиванием массивов переходов из состоя­ ний, не вошедших в А ' , и заменой в столбце «состояние перехода», не вошедших в А', состояний на эквивалентные из множества А'.

82