4.3.3. Кодирование состояний автомата

Количество триггеров, требуемых для организации памяти управляющего автомата, определяется ближайшим сверху целым от двоичного логарифма числа состояний M, т.е.:

. (4.4)

Каждому состоянию a_j (т.е. вершине графа автомата) должна соответствовать одна определенная комбинация значений Q₁, ..., Q_R. Различают два подхода к кодированию состояний автомата: случайное и экономичное (существует еще понятие противогоночного кодирования, которое актуально для асинхронных автоматов и здесь не рассматривается). Экономичное кодирование, как правило, приводит к уменьшению сложности комбинационной части, которая формирует выходные сигналы управления и сигналы возбуждения элементов памяти автомата.

Существует много способов экономичного кодирования, однако в большинстве случаев они весьма трудоемки в практическом использовании и требуют специальных знаний из области теории графов и автоматов [6]. Характерной особенностью этих методов является стремление минимизировать либо число переключений элементов памяти на всех переходах графа автомата, либо обеспечить условия, при которых каждое изменение состояния автомата вызывалось бы действием как можно меньшего числа сигналов возбуждения элементов памяти. Из простых способов, относящихся к классу экономичного кодирования, отметим два: способ соседнего кодирования и кодирование с ослабленной зависимостью от входных сигналов [Л. 6,7].

При соседнем кодировании любые два смежных состояния в графе автомата кодируются наборами Q₁, ..., Q_R, отличающимися состояниями лишь одного элемента (в теории кодирования такие кодовые комбинации характеризуются минимальным кодовым расстоянием d=1). Обычно для реализации соседнего кодирования граф автомата накладывают на карту Карно соответствующего ранга, как это показано на рис. 4.8 применительно к графу рис. 4.5, б.

Рис. 4.8. Применение соседнего кодирования для состояний графа автомата Мили рис.4.5,б (переход «34» не удовлетворяет требованиям соседнего кодирования)

Соседнее кодирование, требования к которому сформулированы в работе [6], не всегда возможно. На рис. 4.9 показаны два графа, не допускающие соседнего кодирования.

Кодирование с ослабленной зависимостью от входных переменных группы X={x_k} предусматривает размещение подмножества состояний автомата A(a_m), образованного всевозможными переходами из состояния a_m , расположение в одном столбце или строке карт Карно.

Рис. 4.9 Графы, не допускающие соседнее кодирование

Рис. 4.10. Комбинированный способ

кодирования состояний автомата Мура,

изображенного на рис. 4.7

Н а рис. 4.10 показан один из возможных вариантов использования данного способа для автомата Мура. Здесь подмножество A(a₅)(6,7) и A(a₇)(5,8) расположены в одной строке. Остальные переходы удовлетворяют соседнему кодированию.

4.3.4. Составление структурной таблицы автомата

Структурная таблица автомата представляет собой граф структурного (в отличие от абстрактного) автомата, заданный в виде списка. В табл. 4.4 приведена прямая структурная таблица автомата Мили, построенная на основе графа рис. 4.5,б с кодировкой состояний на рис. 4.8. В качестве элемента памяти выбран синхронный RS- триггер. Табл. 4.4 носит название прямой структурной таблицы, в которой в графе ИСХОДНыЕ СОСТОЯНИЯ перечисляются все состояния автомата, начиная с первого (в обратной таблице указанное последовательное перечисление состояний производится в графе СОСТОЯНИЯ ПЕРЕХОДОВ). Переход автомата из состояния a_m в a_S контролируется частной функцией перехода F_i(a_m,a_S)=a_mX(a_m,a_S), которая и определяет значения выходных сигналов Y_i и функций возбуждения для i-го перехода. Аналитические выражения для определения функций Y_i и _i записываются на основе объединения по ИЛИ соответствующих функций переходов (в данной таблице отсутствуют одинаковые выходные сигналы для разных функций перехода).

Таблица 4.3

№ перехода	исходные состояния				состояния переходов				функции перехо-дов	выход-ные сигналы	сигналы возбужде-ния
	am	Q1	Q2	Q3	aS	Q1	Q2	Q3	Fi(am, aS)	Yi(am, aS)	i(am, aS)
1	a1	0	0	0	a1	0	0	0	a1	------	------
2	a1	0	0	0	a2	0	0	1	a1	Y13	S3
3	a2	0	0	1	a3	0	1	1	a2	Y12	S2
4	a3	0	1	1	a4	1	1	0	a3	Y1	S1, R3
5	a4	1	1	0	a5	1	1	1	a4	Y48	S3
6	a5	1	1	1	a6	1	0	1	a5	Y34	R2
7	a5	1	1	1	a6	1	0	1	a5	------	R2
8	a6	1	0	1	a7	1	0	0	a6	Y33	R3
9	a7	1	0	0	a1	0	0	0	a7	Y3	R1
10					a4	1	1	0	a7	------	S2

Таблица 4.5

Выходные сигналы управления Yi(am, aS)	Сигналы возбуждения RS- триггеров i(am, aS)
Y13=F2=a1Пуск	R1=F9= a7x2
Y12=F3=a3	S1=F4= a3
Y1=F4=a3	R2=F6  F7= a5
Y48=F5=a4	S2=F3  F10= a2  a7
Y34=F6=a5	R3=F4  F8= a3  a6
Y33=F8=a6	S3=F2  F5= a1Пуск  a4
Y3=F9=a7x2

В табл. 4.5 приведен список выражений для искомых функций.

Прямая структурная таблица автомата Мура подобна табл. 4.4 за тем лишь исключением, что в ней будет отсутствовать столбец ВЫХОДНЫЕ СИГНАЛЫ Y_i(a_m,a_S), которые войдут в расширенный столбец ИСХОДНЫЕ СОСТОЯНИЯ с обозначением a_m/Y_i, так.как. для автомата Мура выходной сигнал есть функция только состояния (см. выражение (4.3)).