Разработка дискретного устройства (ДУ). Синтез преобразователя параллельной формы сигнала в последовательную, страница 15

2  Синтез абстрактного автомата

2.1 построение обобщённой таблицы истинности.

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

Для описания дискретного автомата с памятью, помимо состояний входа X(t) и выхода Z(t), необходимо также знать состояние памяти автомата, его внутреннее состояние S(t). Чтобы задать закон функционирования автомата, необходимо определить, каким образом в зависимости от его  внутреннего состояния происходит переработка входной информации в выходную, и каким образом происходит изменение его внутреннего состояния.

Поэтому в дискретном автомате с памятью необходимо оперировать с двумя разными функциями: j и f. Функция j, называемая функцией переходов, описывает смену внутренних состояний автомата, т.е. изменения содержимого памяти в зависимости от того, что в ней хранилось, и от того, какие изменения входных сигналов имели место. Функция f, называемая функцией выходов, описывает изменение выходных сигналов автомата под воздействием входных сигналов в зависимости от того, что было записано в памяти автомата.

Синтезируем абстрактный автомат, заданный таблицей переходов ТП (табл. 7) и таблицей выходов ТВ (табл. 8).

Таблица 7 – Таблица переходов абстрактного асинхронного автомата    

S	A1	A2
S0	S1	<S0>
S1	S0	<S1>
S2	<S2>	S3
S3	<S3>	S4
S4	<S4>	S2

Таблица 8 – Таблица выходов абстрактного асинхронного автомата

S	A1	A2
S0	0	0
S1	0	0
S2	0	0
S3	1	1
S4	1	1

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

При этом необходимо провести анализ работы автомата на наличие состязаний. Существуют методы кодирования состояний, которые автоматически учитывают все возможные состязания элементов автомата. Поэтому отпадает необходимость в последующем анализе. Воспользуемся одним из таких методов – кодирование состояний по столбцам ТП. Метод основан на группировании состояний автомата в l-классы. l-классом столбца является множество состояний,  содержащее устойчивое состояние и все неустойчивые состояния, из  которых задан переход в данное устойчивое состояние.

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

Столбец А1 содержит l-классы: l₁={S2}; l₂={S3}; l₃={S4}.

Столбец А2 содержит l-классы: l₄={S0}; l₅={S1}.

Необходимо  исключить ложные переходы между l-классами. Для этой цели в столбце  необходимо выделить для  кодирования  состязаний, специальные  внутренние  переменные.

Определим число разделяющих переменных:

Таким образом, для разделения l-классов по столбцу А1 требуются 2 переменные Y1 и Y2, а по столбцу А2 – одна переменная – Y3.

Коды классов столбца А1:

l₁={00};

l₂={01};

l₃={10};

l₄={0};

l₅={1}.

С учетом сказанного составим кодированную таблицу переходов асинхронного автомата.

Таблица 9 – Кодированная таблица переходов асинхронного автомата

S	A1	A2
	Y1Y2	Y3
S0	00	<0>
S1	00	<1>
S2	<00>	0
S3	<01>	0
S4	<10>	0

Отсюда запишем  коды состояний автомата: