1 Цель работы

Изучение метода синтеза асинхронных автоматов с исключением критических состязаний.

2 Основные понятия

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

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

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

Таблица 1

Совмещенная таблица переходов и выходов

S	x
	0	1
1	(1), 0	7
2	3	(2), 0
3	(3), 1	5
4	(4), 1	7
5	4	(5), 1
6	(6), 0	2
7	6	(7), 0

Шаг 1. Формирование разделяющих переменных по каждому столбцу и определение -классов.

Переходы в таблице осуществляются по столбцам x=0 и x=1. Переход осуществляется в то состояние, номер которого указан в рассматриваемой клетке таблицы переходов, например, из клетки будет реализован переход в клетку столбца x=0 с номером состояния S=6. Объединяя все возможные переходы по каждому столбцу рассматриваемой таблицы переходов, получаем систему λ-классов каждого столбца. Каждый такой класс будет содержать одно устойчивое и все неустойчивые состояния, из которых задан переход в данное устойчивое состояние. Другими словами, каждый λ-класс будет содержать номера тех состояний, которым соответствуют одинаковые цифры по каждому столбцу таблицы переходов. Рис. 1 поясняет методику выделения λ-классов.

Рис. 1. Определение λ-классов в заданной таблице переходов

В столбце x=0 сформировано ₁=4 λ-класса, а в столбце x=1 – ₂=3 λ-класса. Каждый обозначенный в табл. 1 переход осуществляется внутри одного из семи λ-классов (рис. 1). Если в результате состязаний реле в работе автомата возникает переход из одного λ-класса в другой (например, как это показано на рис. 1 – ложный переход 24 вместо 23), то нарушается алгоритм работы автомата – возникает так называемое критическое состязание [1]. Поэтому необходимо исключить такие ложные переходы между λ-классами. С этой целью в каждом столбце x=0 и x=1 вводятся разделяющие внутренние переменные, кодирующие λ-классы. Разделяющие переменные обладают следующими свойствами.

Свойство 1. Для состояний, принадлежащих одному λ-классу, разделяющие переменные имеют одинаковые значения.

Свойство 2. Для состояний, принадлежащих разным λ-классам, разделяющие переменные имеют разные значения.

Свойство 3. При любом переходе внутри столбца x=0 или x=1 разделяющие переменные не меняют своих значений.

Свойство 4. Поведение асинхронного конечного автомата в столбце x=0 или x=1 зависит только от разделяющих переменных.

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

Осуществим кодирование каждого λ-класса.

Шаг 2. Кодирование -классов.

Для каждого столбца на основании числа λ-классов в нем определяется минимально необходимое число разделяющих переменных y_i:

(1)

где _j – число λ-классов в столбце j;

N – число разделяющих переменных в столбце j;

– ближайшее целое, превосходящее a (целое сверху от a).

Пользуясь формулой (1), находим:

В табл. 2 приведен результат кодирования λ-классов. Видно, что каждый λ-класс по столбцам x=0 и x=1 разделен.

Таблица 2