Г л а в а 25

Кодирование состояний синхронного автомата

25.1.Задача кодирования состояний

Вабстрактной модели автомата M = (A, B, Q, Ψ, Φ) элементами множеств А, В и Q являются абстрактные символы. Как было сказано выше, для реализации заданного поведения в виде логической сети надо перейти от

функций Φ и Ψ к системе булевых функций, т. е. от абстрактной модели автомата надо перейти к структурной модели. При этом переменные а, b и q заменяются векторными переменными:

a→ x = (x1, x2, … , xn);

b→ y = (y1, y2, … , ym); q → z = (z1, z2, … , zk).

Различным значениям многозначных переменных а, b и q должны быть поставлены в соответствие различные значения векторных переменных х, у и z. Векторы х, у и z показывают структуру абстрактных символов а и b и состояния q. Элементами этой структуры являются соответственно двоичные сигналы и состояния двоичных элементов памяти. Функции Φ и Ψ преобразуются соответственно в векторные функции ϕ(x, z) = у и ψ(x, z) = z+, а те, в свою очередь, – в систему булевых функций, число которых m + k:

yi = ϕi(x1, x2, … , xn, z1, z2, … , zk), i = 1, 2, … , m; zj+ = ψi(x1, x2, … , xn, z1, z2, … , zk), j = 1, 2, … , k.

Числа п, т и k должны удовлетворять соотношениям α ≤ 2п, β ≤ 2т и γ ≤ 2k, где α, β и γ – числа абстрактных входных и выходных символов и состояний

соответственно. Минимальные значения		этих	величин	определяются как
п = log2 α , т = log2 β и	k = log2 γ , где	а	означает	минимальное целое
число, не меньшее а.

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

170

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

Чтобы показать неравнозначность выбора вариантов кодирования, приведем следующий простой пример из работы [20]. Пусть табл. 25.1 представляет собой таблицу переходов и выходов заданного автомата, а табл. 25.2 – два варианта кодирования его состояний.

	Таблица 25.1					Таблица 25.2
Таблица переходов и выходов				Варианты кодирования состояний
q1	0	1		q1	Вариант 1	Вариант 2
	q1, 0	q2, 0			1 1	0 0
q2	q1, 0	q3, 1		q2	0 0	1 0
q3	q4, 1	q1, 0		q3	1 0	1 1
q4	q1, 1	q1, 1		q4	0 1	0 1

Соответствующие системы булевых функций представлены матрицами U1, V1 для варианта 1 и U2, V2 для варианта 2:

x z1 z2			z+	z+ y		x z1 z2			z+	z+ y
0 1		1	1	2		0 0 0			1	2
			1 1 0						0 0 0
1 1		1	0 0 0			1 0 0			1 0 0
0 0 0			1 1 0			0 1		0	0 0 0
U1 = 1 0 0 ,			V1 = 1 0 1 ;			U2 = 1 1		0 ,	V2 = 1 1 1 .
0 1		0	0 1		1	0 1		1	0 1		1
1 1		0	1 1		0	1 1		1	0 0		0
0 0 1			1 1		1	0 0 1			0 0		1
1	0 1		1 1		1	1	0 1		0 0		1

После минимизации данных систем булевых функций получим следующие системы ДНФ в матричном представлении:

	x		z1	z2			z+	z+ y
	0 1 0						1	2
							0 1 1				x z1 z2				z+	z+ y
				0							1 − 0				1	2
	1 1						1 1		0						1 0		0
U1 =	0 0			−		,	V1 = 1 1		0 ;	U2 =	− 0		1	,	V2 = 0 0		1 .
							1 0 1								0 1		1
	1 0			−							1 1		0
											0	1	1			1
		0	−	1			1	1	0						0		1
			0	1			1	1	1
	−

171

Отсюда ясно видно, что, выбрав вариант 2 для кодов состояний заданного автомата, получим более простую систему ДНФ.

Можно подсчитать, сколько всего различных и неравнозначных вариантов кодирования существует для конкретного автомата. Пусть γ – число состояний автомата и k – минимальная длина булева вектора, кодирующего состояние. Тогда число различных вариантов кодирования равно числу размещений 2k

	элементов по γ позициям, т. е.	2k!		. Если учесть то,		что перестановка
		(2k −γ )!
	столбцов дает равнозначные варианты, то получим				2k!			. Можно считать
					(2k −γ )!k!

равнозначными варианты, получаемые друг из друга путем инвертирования

	значений внутренних переменных. Тогда получим	2k!	или
		(2k −γ )!k!2k

(2k −1)! . Ясно, что перебрать все варианты реально только при небольшом

(2k −γ )!k!

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

25.2. Метод «желательных соседств»

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

Каждой	паре	состояний qi, qj		автомата	с	множеством	состояний
Q = {q1, q2, … , qγ}		припишем	вес wij = w′ij + w′′ij,		где w′′ij – число столбцов
таблицы переходов, в которых строки qi и qj имеют одинаковые элементы, т. е.
число значений переменной а, при которых						Ψ(a, qi) = Ψ(a, qj),		а w′ij
определяется	следующим		образом.	Пусть	wp	– число	пар	вида
Ψ(as, qp), Ψ(at, qр) ,		где входные символы as и			at имеют соседние			коды,

γ

Ψ(as, qp) = qi и Ψ(at, qp) = qj. Тогда w′ij = ∑wp .

p=1

Желательно, чтобы коды состояний qi и qj были тем ближе друг к другу, чем больше величина wij. Здесь имеется в виду расстояние в гиперкубе, представляющем пространство кодирующих переменных, между вершинами, соответствующими данным кодам. Для объяснения такого правила приведем следующие соображения.

Общий вид матриц U и V, задающих систему булевых функций zj+ (j = 1, 2, … , k), представим следующим образом:

172

x1

U = xs1xt1

x2

...

xn

z1

z2 ...

zk

z+

z+

...

z+

...

...

1

2

k

...

xs2

...

xsn

zp1

zp2 ...

zpk

,

z

i1

z

i2

...

z

ik

,

...

...

V =

...

xt2

...

xtn

zp1

zp2 ...

z j2

...

zpk

z j1

z jk

...

...

...

где (xs1, xs2, … , xsn) и (xt1, xt2, … , xtn) – соседние векторы, являющиеся кодами входных символов as и at и представляющие совокупности входных двоичных

сигналов, а (zp1, zp2, … , zpk), (zi1, zi2, … , zik) и (zj1, zj2, … , zjk) – коды состояний qp, qi и qj соответственно.

Здесь отражена ситуация, которая учитывается при подсчете значения w′ij.
Пара вектор-строк (xs1, xs2, … , xsn, zp1, zp2, … , zpk) и (zi1, zi2, … , zik) матриц U и V
представляет переход автомата из состояния qp в состояние qi				при входном
символе as,	выражаемый формулой Ψ(as, qp) = qi.		Точно так же пара строк
(xt1, xt2, … , xtn, zp1, zp2, … , zpk),		(zj1, zj2, … , zjk)	представляет	переход,
выражаемый	формулой Ψ(at, qp) = qj. Отсюда		видно, что	чем больше

одноименных компонент векторов (zi1, zi2, … , zik) и (zj1, zj2, … , zjk), являющихся кодами состояний qi и qj, совпадают и равны единице, тем больше, возможно,

будет условий для простого склеивания элементарных конъюнкций в получаемой системе ДНФ.

Ситуация, учитываемая при подсчете значения w′′ij, представляется следующими матрицами:

x1

x2 ... xn

z1

z2

...

zk

...

...

x

x

...

x

z

z

...

z

,

U =

u1

u2

un

i1

i2

ik

x

...

...

x

...

x

z

j1

z

j2

...

z

jk

u1

u2

un

...

...

z+		z+
	1	2
		...
z		z
V =	v1	v2
z		...
		z
	v1	v2
		...

... zk+

... zvk .

... zvk

Здесь	пары	строк (xu1, xu2, … , xun, zi1, zi2, … , zik),		(zv1, zv2, … , zvk)		и
(xu1, xu2, … , xun, zj1, zj2, … , zjk), (zv1, zv2, … , zvk) представляют переходы в одно и
то же состояние		qv при одном и том же значении au		переменной а,		т. е.
Ψ(au, qi) = Ψ(au, qj) = qv. Ясно,			что желательно иметь соседними		коды	тех
состояний qi	и qj, для которых переменная а принимает много значений аи,
удовлетворяющих		Ψ(au, qi) = Ψ(au, qj). Тогда возможно простое склеивание
элементарных конъюнкций,			представленных показанными		строками

матрицы U.

173

Одна из реализаций метода «желательных соседств» представляется как процесс построение k-мерного гиперкуба, напоминающий сборку некоторой простой механической конструкции. При этом вершины гиперкуба, являющиеся первоначально вершинами некоторого пустого графа (без ребер), заранее поставлены в соответствие состояниям автомата и на парах этих вершин заданы величины wij.

Исходными данными для построения k-мерного гиперкуба являются величины wij и число состояний автомата γ. Предполагается, что это число минимально или по каким-то причинам не подлежит минимизации. Если γ не представляет собой целой степени двойки, то оно увеличивается до γ′= 2k и считается, что wrs = 0, если хотя бы одно из qr и qs является дополнительно введенным таким образом состоянием.

Построение k-мерного гиперкуба представляется как последовательность k шагов. На p-м шаге рассматривается множество (p – 1)-мерных гиперкубов, они объединяются в пары, и из каждой пары получается один p-мерный гиперкуб путем соответствующего добавления ребер. При этом по возможности для соединения ребрами выбираются те вершины, которым соответствуют наибольшие из оставшихся значения wij. Вершинам полученного гиперкуба приписываем k-компонентные булевы векторы с соблюдением отношения соседства, представленного ребрами гиперкуба.

На первом шаге из γ′ изолированных вершин, или 0-мерных гиперкубов, строятся одномерные гиперкубы в виде γ′/ 2 попарно несмежных ребер. На последнем k-м шаге из двух ( k – 1)-мерных гиперкубов собирается один k- мерный гиперкуб путем добавления 2k - 1 ребер.

Продемонстрируем этот процесс на примере автомата, таблицей переходов которого является табл. 25.3. Введем два фиктивных состояния q7 и q8, чтобы довести число состояний до 8 = 23. Значения wij удобно задать в виде табл. 25.4, где строки и столбцы соответствуют состояниям автомата.

На первом шаге получаем четыре одномерных гиперкуба, изображенных на рис. 25.1. Максимальное значение имеет вес w23 = 3. Поэтому в первую очередь ребром соединяются вершины q2 и q3. Затем ребрами соединяются

вершины q1 с q6, q4 с q5 и q7 с q8.

Чтобы из четырех одномерных гиперкубов получить два двухмерных, надо добавить четыре ребра. Для этого выбираются такие ребра, чтобы сумма их весов была максимальна. Сначала строится один гиперкуб, для которого выбираются два ребра с максимальной суммой весов. Затем точно так же собирается второй гиперкуб. На рис. 25.2 показаны варианты выбора ребер для получения первого двухмерного гиперкуба.

Вершины q7 и q8 здесь не участвуют, так как все инцидентные им ребра имеют нулевой вес и сумма их весов заведомо не максимальна. Максимальной суммой весов обладает четвертый вариант. Для второго гиперкуба все варианты одинаковы.

174

На рис. 25.3 изображены два двумерных гиперкуба, из которых надо собрать один трехмерный гиперкуб, добавив четыре ребра. Варианты такой сборки представлены на рис. 25.4. Сумма весов ребер показана ниже каждого изображения варианта сборки.

			Таблица 25.3							Таблица 25.4
	Таблица переходов							Значения wij
q		х1 х2				q2 q3 q4 q5 q6 q7 q8									q1
	00		01	10		2	1	0	0		2	0	0
q1		q1	q2	q6			3	1	2		2	0	0		q2
q2		q3	q2	q1				2	1		0	0	0		q3
q3		q2	q3	q5					2		0	0	0		q4
q4		q4	q5	q2							2	0	0		q5
q5		q3	q5	q4								0	0		q6
q6		q3	q2	q4									0		q7

					• q2		• q1		• q4	• q7
			q3 •		q6 •		q5 •		q8 •
		Рис. 25.1. Результат первого шага построения гиперкуба
q2 •			• q3	q2	•		• q3	q2 •	• q3	q2 •	• q3
q1 •			• q6	q6	•	• q1		q4 •	• q5	q5 •	• q4
w12 + w36 = 2				w26 + w13 = 3				w24 + w35 = 2		w25 + w34 = 4
q1 •			• q6	q1	•		• q6
q4 •			• q5	q5	•	• q4
w14 + w56 = 2				w15 + w46 = 0

Рис. 25.2. Варианты сборки двухмерного гиперкуба

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

q2	q3	q1	q7
q5	q4	q6	q8

Рис. 25.3. Результат сборки двумерных гиперкубов

175

q1

q6

q6

q1

q7

q1

q8

q6

q2 q7

q3

q8

q2 q8

q3

q7

q2 q8

q3

q6

q2 q7

q3

q1

q5

2

q4

q5

3

q4

q5

1

q4

q5

q4

0

q7

q8

q8

q7

q1

q7

q6

q8

q2

q3

q2

q3

q2

q3

q2

q3

q5

q1

0

q4 q6

q5

q6

2

q4 q1

q5

q6

4

q4

q8

q5

q1

q4

q7

2

Рис. 25.4. Варианты сборки трехмерного гиперкуба

Булев автомат, соответствующий данному варианту кодирования, представим тремя картами Карно, которые задают не полностью определенные функции z1+, z2+ и z3+ и строкам которых соответствуют состояния заданного автомата (рис. 25.6).

q6(101) q8

••

q5(001) q4(011)

••

q1(100) q7

••

q2(000)

•• q3(010)

Рис. 25.5. Результат сборки гиперкуба с кодами состояний

					х1 х2						х1 х2						х1 х2
0	1	0				1	0		0			0	0		0		q2
																	q5
0	1	1 0				1	1		0			0	1		1
0	0	0				1	0		0			1	0		1		q4
0	0	0				0	0		1			0	1		0		q3
																	q6
0	0	0				1	1		0			0	1		0
																	q1
1	1	0				0	0		0			0	1		0

z1			z1			z1
	z2 z3			z2 z3			z2 z3
		z1+			z2+			z1+
	Рис. 25.6. Представление функций z1+, z2+ и z3+ с помощью карт Карно

Минимизированная система булевых функций, описывающая заданное поведение, представляется следующими матрицами:

176

x1 x2 z1 z2 z3									z+	z+	z+
1 − − 0 0									1	2	3
									1	0	0
		0	1	− 0						0
−									1		0
	0	0	0	0	−					1
	0 0 − − 1								0		0
									0 1 0
U = 1 − − 0 1							,	V =	0 1		1 .
		− − 1			0					0
1									0		1
		1	− 1		0					1
−									0		0
	0 − − 1				1				0 0		1
		1	0	− 1
−									0 0		1
1		−	1	− −					0	0	1

Для сравнения приведем минимизированную систему булевых функций, получаемую при произвольном кодировании, например, путем приписывания состояниям чисел от 0 до 5 в двоичной системе счисления согласно порядку номеров состояний. Матрица кодирования и матрицы, представляющие данную систему булевых функций, имеют следующий вид:

				x1 x2 z1 z2 z3									z+	z+	z+
				0 0 0 − 1									1	2	3
													0 1 0
z1	z2 z3				0 0 −			1
									−				0 0 1
0 0		0		− 1 −				0	1				0 0 1
				−		1	−	1	1				1	0	0
0	0	1			−	1	1	−	0
														0	0
				U = 1 − 0									1
С = 0 1		0	,					− 0			,	V =	1 0 0 .
						0 1
0 1		1		−				− −					0 1 0
	0			− 1 −				1	0				0 1 0
1		0				− −		0	0
1 0 1				1									0 0 1
				1 − −				1	1				0 0 1
				1 − 1 − −									0 0 1
						1 0
				−				− −					0 0 1

Последняя система ДНФ оказалась сложнее – число различных элементарных конъюнкций в ней на две больше, чем в предыдущей системе.

177