Синтезирование асинхронного автомата, заданного таблицей переходов и таблицей выходов. Асинхронный автомат

2. Автомат

2.1. Синтез автомата

Требуется синтезировать асинхронный автомат, заданный таблицей переходов и таблицей выходов. В качестве элементов памяти используется JK-триггеры, базис реализации И-ИЛИ-НЕ.

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

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

Таблица 2.1.1

Таблица переходов

Таблица 2.1.2

Таблица выходов

Синтез асинхронного автомата будем производить по следующему алгоритму: 1. Определения минимально необходимого числа внутренних элементов памяти (ЭП). 2.  Кодирование строк таблицы переходов. 3. Построение кодированных таблиц переходов (ТП) и таблиц выходов (ТВ). 4. Исключение критических состязаний.

1.  Определение минимально необходимого числа внутренних ЭП.

Минимально необходимое число внутренних ЭП определим по формуле

где r – число строк ТП;  - обозначение ближайшего целого числа, большего или равного .

В нашем случае требуется  внутренних ЭП. Обозначим их Y1, Y2 и Y3.

2.  Кодирование строк ТП.

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

Таблица 2.1.3

Таблица кодирования строк ТП

3.  Построение кодированных ТП и ТВ

Цифры состояний в клетках ТП и ТВ заменим двоичным кодом, приписанным соответствующему состоянию. В результате образуются ТП (таблица 2.1.4) и ТВ (таблица 2.1.5). Так число состояний схемы (5) меньше числа трехразрядных двоичных кодов (8), коды 101, 010 и 011 не использованы при кодировании. Реальная схема, построенная на трех внутренних ЭП, имеет восемь состояний, которые делятся на основные и неосновные. Полные состояния, клетки которых расположены в строках неосновных состояний, недопустимы при работе схемы. В этих клетках ставят знак безразличного состояния и в них могут быть произвольные коды.

Таблица 2.1.4

Кодирования ТП

Таблица 2.1.5

Кодирования ТВ