Конечный автомат, асинхронный автомат, синхронный автомат, таблица переходов, таблица выходов, граф состояния, синтез, элемент памяти

2.1 Кодирование асинхронного автомата При синтезе асинхронного автомата необходимо решить вопрос ис-ключения критических состязаний элементов памяти (ЭП) Наиболее рас-пространенными способами, предполагающими исключение критических состязаний в процессе синтеза, являются методы кодирования таблиц пе-реходов таким образом, чтобы при функционировании автомат не смог оказаться в не заданных по условиям переходов состояниях. Универсаль-ным является метод кодирования ТП по столбцам [2], использование ко-торого рассмотрим на примере синтеза автомата, заданного ТП (таблица 2.1) и ТВ (таблица 2.2). При этом методе вводится понятие -класса, представляющего собой множество, включающее устойчивое и все неустойчивые состояния, из которых заданы переходы в данное устойчивое состояние. Критические состояния возникают в том случае, когда схема в результате состязаний ЭП попадает вместо одного устойчивого состояния в другое, т. е. из одного -класса схема ошибочно перейдет в другой. Для исключения этого явления вводятся переменные, разделяющие -классы внутри каждого столбца ТП. Они имеют одинаковое значение в кодах состояний одного -класса и различное для кодов состояний других -классов. Для разделения состояний внутри одного -класса вводятся дополнительные переменные, которые одновременно являются разделяющими для -классов другого столбца.

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

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

X X

X0 X1 X0 X1

S0 S1 S2 S0 Z1 Z0

S1 S0 S3 S1 Z0 Z1

S2 S1 S3 S2 Z0 Z1

S3 S2 S0 S3 Z1 Z0

Согласно используемому методу для первого столбца заданной таблицы (таблица 2.1) 11=0,2, 12=1,3, а для второго — 21=1,2, 22=0,3, где в скобках указаны номера строк с устойчивыми и неустойчивыми состояниями.

Необходимое количество элементов памяти определяется по формуле:

(2.1)