5.4. Рациональный выбор варианта кодирования состояний синхронных автоматов

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

Кодирование состояний абстрактного автомата, при котором получаются минимальные (в смысле необходимого для технической реализации оборудования) функции возбуждения и выходов, – процесс довольно сложный, связанный с перебором большого числа вариантов. Поэтому в дальнейшем остановимся на рассмотрении правил кодирования, приводящих, в большинстве случаев, к получению близких к минимальным (а иногда и к минимальным) схемам на элементах И, ИЛИ, НЕ, реализующим функции возбуждения элементов памяти синтезируемого автомата. Все дальнейшие рассуждения будем вести в предположении, что для кодирования состояний всегда будет использоваться минимально возможное число элементов памяти.

Рассмотрим абстрактный автомат, заданный таблицей переходов-выходов (табл. 5.36).

Таблица 5.36

x \ a	1	2	3
	3,0	1,1	2,0
	3,1	3,1	2,0

Пусть состояния автомата закодированы в общем виде в соответствии с табл. 5.37, где b_ij{0, 1}.

Таблица 5.37

a \ Q	Q1	Q2
1	b11	b21
2	b12	b22
3	b13	b23

Составим кодированную таблицу переходов (табл. 5.38).

Таблица 5.38

х	Q1	Q2	Q1	Q2
0	b11	b21	b13	b23
0	b12	b22	b13	b23
0	b13	b23	b12	b22
1	b11	b21	b13	b23
1	b12	b22	b11	b21
1	b13	b23	b12	b22
t	t		t+1

Пусть

Условимся, что в качестве элементарных автоматов используются D-триггеры, значения функций возбуждения которых, в соответствии с таблицей переходов, совпадают со значениями Q(t+1). Тогда функции возбуждения элементарных автоматов будут иметь вид

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

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

1. Положить равными нулю переменные b_ij, которые в уравнениях для q имеют наиболее сложные сомножители (коэффициенты).

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

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

В рассматриваемом примере в соответствии с первым правилом положим b₁₃ = b₂₃ = 0. Это приведет к тому, что в уравнениях для q₁ и q₂ последние слагаемые будут равны нулю и могут быть отброшены, а состояние автомата а₃ будет кодироваться двоичным набором 00. Если теперь положить b₁₁ = 0, то b₂₁ = 1, так как кодовая комбинация 00 уже используется для кодирования состояния а₃. Таким образом, состояние а₁ кодируется двоичным набором 01. Для кодирования состояния а₂ используем набор 10, что означает приравнивание к нулю переменной b₂₂ и приравнивание к единице переменной b₁₂.

Окончательно функции возбуждения примут вид

На основании приведенных выше правил и рассмотренного примера можно сделать вывод, что те состояния, в которые осуществляется большое число переходов, должны кодироваться наборами с минимальным числом единиц, а те состояния, между которыми имеются переходы, должны кодироваться наборами, отличающимися, по возможности, наименьшим количеством разрядов.