4.3. Кодирование внутренних состояний автомата

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

Если автомат задается таблицей переходов или ЛСА, то после минимизации числа внутренних состояний автомата (или сформирования микрокоманд) внутренним состояниям (или микрокомандам) порежнему не приписываются состояния ЭП. Это объясняется тем, что на данном этапе нет необходимости рассматривать каждое внутреннее состояние как определенный набор состояний ЭП. Достаточно иметь только номер внутреннего состояния без указания состояний ЭП в этом состоянии. Для построения же структурной схемы автомата, т. е. построения цепей включения ЭП и выходных цепей, необходимо знать набор состояний ЭП, который сопоставляется с тем или иным внутренним состоянием. При этом оказывается, что в зависимости от того, как будут приписаны эти наборы состояний ЭП каждому из внутренних. состояний автомата, могут в значительной степени измениться сложность структуры автомата, его устойчивость в работе и т. п.

Процесс приписывания каждому внутреннему состоянию набора состояний ЭП в теории автоматов носит название кодирования внутренних состояний автомата. Вообще говоря, такие наборы значений двоичных переменных надо приписать не только внутренним состояниям автомата, но и каждому состоянию его входа и выхода. Однако во многих практических случаях состояния входа и выхода оказываются уже закодированными, так как они являются соответственно выходными и входными состояниями других блоков и устройств.

Пусть с каждым внутренним состоянием сопоставлен набор состояний ЭП, т. е. кодовая комбинация. Если такое сопоставление осуществляется произвольным образом, то может оказаться,. что четырем внутренним состояниям автомата приписаны кодовые комбинации 000, Oil, 010 и 001 (рис. 4.4,а). Пусть, кроме того, по условию работы автомат при появлении на его входе состояния pi должен перейти из своего внутреннего состояния, которому приписана кодовая комбинация 000, во внутреннее состояние 011. (Этот переход на рис. 4.4,а показан сплошной линией с указанием состояния входа pi, вызывающим этот переход.) При этом условиями работы не предусматривается переход автомата из внутреннего состояния 000 в остальные два внутренние состояния, которым приписаны кодовые

комбинации 001 и 010.

ООО Я 001

л--1--Х>

l\ oov

8) 011

ООО Я ОО1.

Рис. 4.4

Таким образом, при переходе от состояния 000 к состоянию 011 в автомате должны одновременно сработать второй и третий ЭП. Однако из-за разброса времени срабатывания ЭП (в качестве ЭП могут быть использованы электромагнитные реле, триггеры и другие двухстабильные элементы) может сработать вначале второй или третий ЭП. Из-за этого автомат попадает в одно из Двух непредусмотренных в данном переходе внутренних состояний, которым приписаны кодовые комбинации 010 и 001 соответственно (на рис. 4.4,а указанные переходы обозначены штриховыми линиями). Аналогичное явление может произойти и при отпускании ЭП.

Говорят, в автомате, в котором внутренние состояния закодированы так, что в заданных условиями работы переходах найдется хотя бы один переход, при котором требуется одновременно сработать (отпустить) двум и более ЭП, имеются состязания элементов памяти. Среди состязаний ЭП различают критические и некритические.

К критическим относятся такие состязания, которые могут исказить алгоритм функционирования автомата, т. е. его функции переходов и выходов. Например, если в рассмотренном выше примере автомат из состояний 001 и 010 при состоянии входа pi никуда не должен переходить (рис. 4.4,6), то из-за состязаний ЭП он может lie перейти в состояние 011, что предусмотрено условиями его работы. Это есть пример критических состязаний ЭП, из-за которых искажается функция переходов автомата.

К критическим относятся также и такие состязания ЭП, которые искажают функцию выходов. Например, из рис. 4.4,в видно, что функция переходов автомата не искажается. Действительно, даже если автомат из-за состязаний ЭП перейдет в состояние 001 или 010, то при том же состоянии входа он из этих состояний затем перейдет в заданное условиями работы состояние 011. Однако если с внутренними состояниями 000 и 011 сопоставлено значение выходного сигнала z=l, а с внутренними состояниями 010 и 001 - значение выходного сигнала z=0, то, например, при переходе автомата 000Л-010-Л-011 возникает кратковременное изменение значения выходного сигнала с z=\ на z=0, которого не было бы при непосредственном переходе автомата 000--011. Состязания ЭП, вызывающие такое искажение функции выходов автомата, также называются критическими.

К некритическим относятся состязания ЭП, которые не приводят к искажениям ни функции переходов, ни функции выходов. Например, если бы на рис. 4.4,в с внутренними состояниями 001 и 010 было сопоставлено состояние выхода z=l или 2=~, то имеющиеся в автомате состязания были бы некритическими.

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

В теории автоматов [3] разработаны методы кодирования внутренних состояний, которые позволяют так приписывать кодовые комбинации внутренним состояниям, что в автомате на всех

заданных условиями работы переходах не возникают критические состязания ЭП. Не имея возможности подробно осветить в данном пособии все современные методы кодирования внутренних состоянии автомата, рассмотрим на примере один из них, который является наиболее простым для понимания этого процесса, но который, к сожалению, пригоден лишь для автоматов с небольшим числом внутренних состояний. Метод кодирования внутренних состояний на основе разбиений изложен в [1, З].

Пример 49 Пусть задан автомат (счетчик импульсов) таблицей переходов (табл. 4.14). Требуется закодировать его внутренние состояния.

Для этого вначале составим диаграмму его возможных переходов при состояниях входа р, и ра (рис. 4.5). Затем возьмем развертку л-мерного единичного куба, указывающую связь его вершин с ребрами. Например, на рис. 4.6 изображена развертка трехмерного куба.

Xtf.

-о

3S1 I 4

as if

4

WO 001 101 100 V--6-o-

5)

Рис. 4.5

010 011 m no

Рис. 4.6

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

Как было отмечено ранее, в автомате не будет критических состязаний, если при его переходах будет изменяться только один ЭП. Тогда легко понять, что если совместить каждую из диаграмм переходов автомата (см. рис. 4.5) с разверткой п-мерного единичного куба (см. рис. 4.6), то тогда в автомате не будет критических состязаний. При этом надо стремиться использовать куб с наименьшим числом л. Тогда кодирование автомата будет осуществляться с минимальным числом ЭП.

00

9-

01

10 1f

Рис. 4.7

Рис. 4.8

В нашем случае можно использовать развертку двумерного куба (рис. 4.7). Совмещая диаграмму переходов автомата при рг (см. рис. 4.5,о) с разверткой рис. 4.7, получаем рис. 4.8,а, а диаграмму переходов при pi (см. рис. 4.5,6) с той же разверткой рис. 4.7, получаем рис. 4.8,6. При этом очевидно, что с одними и теми же внутренними состояниями автомата в диаграммах переходов при различных состояниях входа должны сопоставляться одни и те же вершины развертки га-мерного куба.

В табл. 4.14 (последняя колонка) указаны выбранные выше кодовые комбинации (состояния ЭП). Заметим, что в некоторых случаях такое совмещение для п, равного минимальному числу ЭП, невозможно. Тогда берут куб с большим п, причем для любого автомата такое п всегда найдется. В микропрограммном автомате, который относится к синхронным автоматам, состязания ЭП устраняются использованием так называемой «двойной памяти», когда используются два регистра микрокоманд. В связи с этим микрокомандам, представляющим собой внутренние состояния МА, можно приписывать кодовые

комбинации, т. е. набор состояний ЭП, вообще говоря, произвольно. Например, микрокомандам, полученным в примере 4.8, припишем кодовые комбинации ЭП так, как показано в табл. 4.15.

Контрольные вопросы

1.Какие автоматы являются эквивалентными?

2.Могут ли эквивалентные недоопределенные автоматы иметь различное число внутренних состояний?

3.Какие члены ЛСА являются противоречивыми?

4.Какие существуют методы устранения критических состязании ЭП и ДУ?