Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

Вычисляем значения производной для каждой пары со­ стояний.

Остальные значения производных равны с»

паре состояний даем в соответствие пересечение соответст­ вующих вершин в строящемся дереве.

Согласно алгоритму объединяем в пары состояния -Ь’г, S 5 и Si, S 3 . В результате построили следующий ярус в дереве.

38

Матрица Qc, соответствующая вершинам построенного яруса, имеет следующий вид:

Соответствующая матрице Qc частотная матрица отноше­ ний имеет следующий вид: .

Производные от модели x|)(Qc) на парах состояний имеют следующий вид:

- g - ( S ,n S 6, SiflSe).

Остальные значения производной равны со.

39

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

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

Пусть в рассматриваемый момент переключаются два триггера А и В (первое условие), причем функция возбуж­ дения <р одного из триггеров, например В, содержит в каче­

Два > Іа (Ава — время, в течение которого необходимо на­ личие «старого» значения триггера А в схеме возбуждения триггера В; tA — время задержки сигнала возбуждения триг­ гера А (третье условие).

При наличии этих трех условий значение триггера будет неправильно вычислено (так как для правильного вычисле­ ния значения триггера В необходимо, чтобы триггер А сохра­ нял свое «старое» значение по крайней мере в течение 2т (после начала перехода автомата, а триггер А «обновляет» свое значение через т).

Это явление и называется явлением гонок. При наличии гонок, автомат будет переходить не’ в то состояние, которое

40

указано при данном переходе, что приведет к нарушению ав­ томатного соответствия.

Гонки можно устранить, нарушив одно из трех условий гонок.

Проанализируем эти условия с конца* Для того, чтобы на­ рушить третье условие, т. е., чтобы Два < tA, необходимо

Рис. 3-3

иметь схемы возбуждения триггеров А жВ для подсчета Два

иЭ т и схемы будут получены только на этапе структур-

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

Второе условие наличия гонок, т. е. Фв —Ф (%і,........ZA+ . .. ),

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

41

1

Первое условие (переключение двух и более элементов памяти при одном переходе автомата) нарушается, если при любом переходе автомата переключается только один эле­ мент памяти. Это означает, что каждому внутреннему со­ стоянию автомата сопоставляется такой код, что если суще­ ствует переход из состояния в состояние S j (Sj ф 5 3-), то соответствующие им коды отличаются только в одном разря­ де. Другими словами, при реализации автомата гонки отсут­ ствуют, если соответствующий граф переходов можно рас­ положить в п-мерном гиперкубе, так, чтобы переходы из со­ стояния 5,- в состояние Sj (5, Ф Ss) осуществлялись только по ребрам гиперкуба, и коды соответствующих вершин ги­ перкуба были сопоставлены вершинам графа переходов. Та­ кое кодирование называется соседним.

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

Приведем условие вложимости графа переходов в гипер­

кодирование, необходимо, чтобы он не содержал циклы не­ четной длины. Если же он содержит таковые, то необходимо разорвать все циклы нечетной длины путем введения допол­ нительных внутренних состояний, в которых не реализует­ ся отображение X-*- У. Эти состояния часто называют неус­ тойчивыми внутренними состояниями.

Условие

h ( G ) < 2

является необходимым, но недостаточным условием сущест­ вования соседнего,кодирования. Например, граф G, изобра­ женный на рис. 3-4, имеет хроматическое число h (G), рав­ ное двум, но не обладает соседним кодированием.

Перед тем как рассматривать алгоритм соседнего кодиро­ вания, определим следующие понятия.

Степенью я (у) вершины ѵ графа G называется число .ре­ бер, инцидентных этой вершине.

Степенью s (G) графа G = <V, U > называется

M7 cs (щ), ЩеѴ.

42