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

стояния в другое триггер памяти Я,- изменяет свое состояние с 0 на 1, то соответствующая дуга графа автомата отмечается символом ср,- . Если же триггер памяти П{ переходит из состояния 1 в состояние О, то дуга отмечается символом фг. Очевидно, что, как и в случае триг­ гера со счетным входом, каждой дуге графа автомата будет приписано столько символов из указанного множества, сколько элементов па­ мяти автомата изменяют свои состояния на соответствующем ей пере­ ходе (рис. 2-9, в).

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

УіУг

г

Рис. 2-9. Графический метод синтеза автомата

ставляет собой конъюнкцию произведения, соответствующего коду состояния, из которого выходит дуга, отмеченная символом ср,- (ф,-), и входного сигнала (или дизъюнкции входных сигналов, если их не­ сколько), приписанного этой дуге. Аналогично выражение для вы­ ходного сигнала уп (п = 1...........Я, где Я — число выходных кана­ лов для реализации выходных сигналов типа 1) получается как дизъюн­ кция выражений, каждое из которых представляет собой конъюнк­ цию произведения, соответствующего коду состояния, из которого выходит дуга, отмеченная символом уп, и приписанного этой дуге входного сигнала (или дизъюнкции входных сигналов, если их не­ сколько), под действием которого происходит переход с выдачей со­ ответствующего выходного сигнала уп. Выражение для выходного сигнала rd (d = 1, . . . , D, где D — число выходных каналов для реа­ лизации выходных сигналов типа 2) получается как дизъюнкция конъюнкций, каждая из которых соответствует коду состояния, ко­ торому приписан символ rd, т. е. в соответствующем этому состоянию

39

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

Полученные при графическом синтезе формулы (2-8), (2-9), (2-10), (2-11) и (2-12) совпадают соответственно с формулами (2-1), (2-3), (2-5), (2-6) и (2-7) — результатами табличного метода синтеза авто­ мата S.

Глава третья

КОДИРОВАНИЕ СОСТОЯНИИ АВТОМАТА

3-1. Гонки в автомате

Как уже отмечалось во второй главе, задача кодирования состоя­ ний является одной из основных задач канонического метода струк­ турного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний эле­ ментарных автоматов памяти одинаковой длины I (в данном пара­

40

графе для простоты ограничимся использованием в качестве элемен­ тов памяти триггеров с раздельными входами, которые будем обозна­ чать 7 \, . . . , ТI, . . . , Т,). При кодировании разным состояниям автомата соответствуют разные коды. Так как триггер с раздельными входами может находиться в двух различных состояниях, 0 и 1, то очевидно, что для автомата с М состояниями минимальная длина кода равна ]log2M [. Переход автомата из одного состояния в другое осу­ ществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния ат с кодом 0101 в состояние as с ко­ дом 1001, это означает, что триггер Т г переходит из состояния 0 в со­ стояние 1, триггер Т о — из состояния 1 в состояние 0, а состояния триггеров Т 3 и Т4 не изменяются.

Рис. 3-1. Состязания между элементами памяти: а — некритические, б — критические

При функционировании автомата могут появиться так называе­ мые состязания. Явление состязаний возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие вре­ мена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных авто­ матов по логическим цепям, имеющим неодинаковую длину. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти со­ стязания, т. е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах неког торых запоминающих элементов до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния а,п в состояние as под дейст­ вием входного сигнала zf автомат может оказаться в некотором про­ межуточном состоянии ак или aLв зависимости от того, какой элемент памяти выиграет состязания. Если затем при том же входном сигнале автомат из ак и а, перейдет в состояние as (рис. 3-1, а), то такие со­ стязания являются допустимыми, или некритическими. Если же в этом автомате есть переход, например, из ак в а;- =^= as под действием того же сигнала zf (рис. 3-1, б), то автомат может перейти в ajtа не в as и правильность его работы тем самым будет нарушена. Такие со­

41

стязания называются критическими состязаниями или гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называется противогопочным.

Один из способов ликвидации гонок состоит в тактировании вход­ ных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов .ѵ-,, . . . , xL имеется еще один канал р от генератора синхроимпульсов (ГСП), по которому поступает сигнал р = 1 в момент прихода импульса и р — 0 при его отсутствии. В связи с этим входным сигналом на переходе (ат, as) будет не z;, а рг;-. Тогда если длительность импульса tp меньше самого

сигналы обратной связи не смогут измениться до тех пор, пока р не станет равным нулю. Но тогда входной сигнал pzf также равен нулю, а потому гонок быть не может.

Наряду с аппаратурными способами для устранения гонок могут использоваться специальные методы кодирования.

3-2. Противогоночное кодирование состояний

Пусть (а, ß) и (у, б) — две пары двоичных кодов длины /. Пары (а, ß) и (у, б) называются развязанными, если при некотором і (1^г'<7) і-й разряд кода принимает одно значение на паре (ос, ß) и противопо­ ложное — на паре (у, б). В противном случае пары двоичных кодов (а, ß) и (у, б) называются связанными. В работе [151 доказана следую­ щая теорема: в автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (ат, as) и (ak, at), as ah происхо­ дящих под действием одного и того же входного сигнала, соответствую­ щие пары кодов состояний развязаны.1 В этой же работе приведен ос­

рассматривать синхронную модель, а устойчивость автомата обеспечивать ка­

42

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

Алгоритм противогоночного кодирования заключается в последо­ вательном развязывании подлежащих развязыванию пар переходов. На промежуточных этапах алгоритма состояниям автомата будут со­ ответствовать .коды, значения некоторых разрядов которых могут быть не определены. Такие коды будем называть неполными. В дальнейшем неопределенные разряды кодов отмечаются черточкой. Пусть (ат, as),

1.Положить і = 0. Перейти к п. 2.

2.Если і = 0, то переход к п. 8, иначе переход к п. 3.

3.Если при некотором г (1 <7) значения r-го разряда чет­ верки а, ß, у, б образуют набор ООП или набор 1100, то переход к п. 9, иначе переход к п. 4.

43