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

где — состояние, соответствующее паре (alt R 0), а В\ — все осталь­

ные состояния, порождаемые аЛ. Переходы из В 4 определим следую­ щим образом: из всех состояний В\ построим переходы в состояние Ьг

(начальное состояние) под действием сигнала единицы, т. е. факти­ чески под действием тактирующего сигнала р. Из состояния Ь1 будут переходы во все состояния Ь/— (as, Rj), если в автомате S' есть пе­ реход из состояния аг в состояние as с выдачей длинного сигнала Rj. В рассматриваемом примере из состояния Ьѵ будет переход в состоя­

ние 612 под действием сигнала х5 х4 с выдачей короткого сигнала г/2. Если же множество В[ — 0 (перед конечной вершиной нет опера­

торных вершин без длинной микрокоманды), то вводим дополнитель­

в начальное состояние Ьх под действием сигнала единицы (тактирую­ щего импульса р).

Минимизация полностью определенного микропрограммного С-ав- томата отличается от минимизации автомата Мили лишь тем, что од­ ноэквивалентным состояниям должны соответствовать одинаковые микрокоманды.

Глава шестая

СИНТЕЗ ЛОГИЧЕСКОЙ СХЕМЫ МИКРОПРОГРАММНОГО АВТОМАТА

6-1. Структурная таблица микропрограммного автомата

Структурные таблицы микропрограммного автомата являются расширением таблиц переходов, рассмотренных в § 5-3. Структурная таблица автомата Мили (табл. 6-1) имеет семь столбцов.

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

92

ваются состояния as, в которые происходят переходы, и их коды К (as). Пятый и шестой столбцы содержат входные X (ат, as) и выходные сигналы Y (ат, as), входящие в пути перехода. В седьмом столбце таб­

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

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

93

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

Для простоты в этой таблице в качестве кода каждого состояния взят двоичный эквивалент его номера, например К (я3) = 011, /С'(я4)= = 100 и т. д. В обратной структурной таблице столбцы обозначены так же, но сначала записываются все переходы в первое состояние, затем во второе и т. д. В табл. 6-3 приведена обратная структурная таблица того же автомата.

Структурные таблицы автомата Мура— как прямая, так и обрат­ ная, будут иметь на один столбец меньше, так как выходной сигнал в них записывается рядом с исходным состоянием (в прямой таблице) или с состоянием перехода (в обратной). В табл. 6-4 построена обрат­ ная структурная таблица автомата Мура, таблица переходов которого представлена таблицей 5-4.

94

Таблица 6-4

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

Структурный синтез микропрограммного автомата проиллюстри­ руем на примере автомата Мили, синтезированного по ГСА на рис. 6-1. После отметки состояний (рис. 6-1) построим обратную структурную таблицу микропрограммного автомата (табл. 6-5).

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

95

турного синтеза автоматов. Так, для срх и у7 из табл. 6-5 имеем1:

Однако для встречающихся на практике микропрограммных авто­ матов подобные выражения очень сложны: они представляют собой

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

Первым шагом при минимизации логической схемы микропрограмм­ ного автомата является объединенное построение компонент функций возбуждения и функций выходов, записанных в одних и тех же строч­

96