теория автоматов / automat-p2

Таблица 10.2			Таблица 10.3				Таблица 10.4
	τ			τ			τ	τ
=			=			=		`
=			=			=		`
=!			=!			=!
="			="			="
=#	`		=#			=#
=$	`		=$			=$
=%	`		=%	`		=%	`	`

Из табл.10.3 видно, что пара (a1, a2), (a6, a6) развязана (четверка (0011)). Точно так же развязаны пары, образованные переходом (a2, a2) и всеми последующими переходами в M1. Обратимся к паре (a3, a4), (a5, a6). Из табл. 10.3 получаем соответствующую четверку (1111) – пара не развязана. Вводим переменную t2 и полагаем для a3 è a4 значение τ 2=0, à äëÿ a5 è a6 τ 2= 1 (òàáë. 10.4).

После чего остальные переходы в M1 тоже развязаны. Аналогично для M2 è M3 получим табл.10.5 и 10.6.

Таблица 10.5

Таблица 10.6

	τ	τ	τ !
=
=
=!
="
=#
=$			`
=%	`	`	`

	τ	τ	τ !	τ "
=				`
=
=!
="				`
=#
=$			`	`
=%	`		`

Переходим к минимизации. Исключаем переменную τ 1 (табл. 10.7) и повторяем процесс развязывания пар переходов.

Оказывается, что пара (a1, a2), (a5, a6) не развязана, в связи с чем добавляем переменную τ 5 и развязываем эту пару (табл. 10.8).

Все остальные пары развязаны. Далее исключаем переменную τ 2 и получаем табл.10.9 с тремя переменными τ 3,τ 4, τ 5, в которой после проверки оказываются развязанными все пары.

104

		Таблица 10.7						Таблица 10.8
	τ	τ !	τ "
						τ	τ !		τ "	τ #
=			`
					=
=					=
=!					=					`
					!
="			`		=					`
					"
=					=
#
					#
=		`	`		=		`		`
$					$
=		`			=		`			`
%					%
		Таблица 10.9						Таблица 10.10

	τ !	τ "	τ #
=
=
=!			`
="			`
=#
=$	`
=%	`		`

	τ !	τ "	τ #
=
=
=!
="
=#
=$
=%

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

10.2. Противогоночное соседнее кодирование

Второй способ кодирования, позволяющий избавиться от гонок, – это кодирование соседних состояний автомата соседними кодами (соседнее кодирование). Соседние состояния – это состояния, связанные дугой на графе автомата, а соседние коды – это двоичные наборы, отли- чающиеся только одним разрядом. Расстояние по Хэммингу у таких кодов равно 1. При соседнем кодировании при переходе автомата из одного состояния в другое меняется состояние только у одного элемента памяти и состязания становятся невозможными. Соседнее кодирование не всегда оказывается возможным [4] и в этом случае приходит-

105

ся на графе между соседними состояниями автомата вставлять дополнительные, так называемые неустойчивые состояния. Неустойчивое состояние автомата (состояние ak, на рис. 10.1) отличается тем, что под действием некоторого входного сигнала Zk, по длительности превышающего время перехода в это состояние ak, автомат может его “проско- чить”, перейдя сразу в следующее состояние as.

Zk Zk

am

ak

as

Ðèñ. 10.1

В процессе добавления неустойчивых состояний необходимо следить за тем, чтобы значение выходного сигнала при этом не менялось. Для того чтобы удобнее было находить коды соседних состояний, целесообразно воспользоваться диаграммой Вейча. Число клеток необходимой диаграммы определяется как 2k, ãäå k – число соседей у того состояния автомата, которое имеет их больше всех остальных состояний. Рассмотрим пример кодирования соседними кодами состояний фрагмента графа некоторого автомата, приведенного на рис. 10.2.

a"	Z	W a	Z W	a	Z W	a%
		Z!	Z"		W	Z
		Z W
	W		W Z		W	Z
a!		a$		a	W	a#

Ðèñ. 10.2

Состоянием с максимальным числом соседей (k = 6) является состояние a0. Следовательно, для кодирования удобно воспользоваться диаграммой Вейча размером 8Ч 8=64=42 клеток (рис. 10.3). Поместим состояние a0 в произвольную клетку диаграммы, например соответству-

þùóþ êîäó 110110 (Q1Q2 Q 3Q4 Q5 Q 6). Эта клетка имеет 6 соседних

клеток, куда целесообразно помещать все состояния, соседние a0. Тогда получим следующие коды состояний:

106

k(a0) – 110110, k(a1) – 110100, k(a2) – 110010, k(a3) – 100110

3!

3

3

>>!

	=	>
=!	=	=#	=$
=%	=
	="

3$ 3# 3

Ðèñ. 10.3

Очевидно, коды состояний a1, a2, a3 отличаются от кода состояния a0 только одним разрядом. Поскольку состояние a5 является одновременно соседним и для a0, è äëÿ a1, необходимо поместить его в такую клетку, которая имела бы минимальные расстояния от обоих этих состояний. Такими клетками являются клетки с кодами 010100 и 010110. Выберем одну из них (например, 010110). Тогда, чтобы обеспечить соседнее кодирование, придется ввести дополнительное неустойчивое состояние b1, используя для него второй из этих кодов, а именно код 010100.

После этого оставшиеся состояния a4 è a6 можно поместить в клетки с кодами 110111 и 111110 соответственно. Состояние a7, соседнее состояниям a3 è a2, удачно помещается в клетку 100010, но при этом не получается требуемых соседних кодов у состояний a7 è a1. Поэтому на переходе a7 → a1 необходимо ввести дополнительные состояния (меньше двух при выбранном кодировании не получается) b2 è b3, расположенные соответственно в соседних клетках (a7 ñ b2, b2 ñ b3, b3 ñ a1).

В результате кодирования число состояний графа увеличилось на 4 (рис. 10.4), что, естественно, уменьшает быстродействие автомата.

107

a"	Z	W a	Z W a		Z W b Z W	b!	Z W a%
		Z!			W
		Z W		Z"
					Z b	W
	W	W		Z			Z
a!		a$		a			a#
							W

Ðèñ. 10.4

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

Таблица 10.11

	Состояние абстрактного	Двоичный код	Соответствующие состояния
	автомата		элементов памяти
	=0	110110	31	32	33	34	35	36
	=1	110100	31	32	33	34	35	36
	=2	110010	31	32	33	34	35	36
	=3	100110	31	3	33	34	35	36
	=4	110111	31	32	33	34	35	36
	=5	010110	31	32	33	34	35	36
	=6	111110	31	32	33	34	35	36
	=7	100010	31	32	33	34	35	36
	>1	010100	31	32	33	34	35	36
	>2	100000	31	32	33	34	35	36
	>3	110000	31	32	33	34	35	36

Следует отметить, что в графе переходов можно найти такие пары соседних состояний (am zk→ as), которые не требуют соседнего кодирования. В этом случае коды, появляющиеся в результате состязаний (ложные коды), могут быть использованы для кодирования состязаний автомата, удовлетворяющих одному из следующих условий:

1) кодируемое ложным кодом состояние (ai) должно быть устойчи- вым по отношению к входному сигналу zk, (рис. 10.5); поскольку под

108

действием zk автомат из ai никуда перейти не может, состязания, если они и возникнут, являются некритическими;

2)из состояния ai отсутствует переход по сигналу zk;

3)из кодируемого ложным кодом состояния ai под действием сигнала zk автомат переходит в нужное состояние as (ðèñ.10.6).

			Zk	Zk	Zk	aj
				am	as
				Zk	Zk
am	Zk	as		ai
						ложные
					ai	êîäû
			Ðèñ. 10.5		Ðèñ. 10.6

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

10.3. Кодирование состояний автомата, близкое к соседнему

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

Рассмотрим эвристический алгоритм кодирования состояний [4] и минимизирующий суммарное число изменений элементов памяти на всех переходах автомата.

Введем весовую функцию W = ∑ tms, ãäå tms = |Km–Ks|2 – расстояние между кодами состояний am è as, равное числу элементов памяти, изменяющих свое состояние на переходе (am, as); суммирование производится по всем переходам автомата. Введенная функция W может служить одной из оценок сложности комбинационной схемы автомата S, при этом упрощение комбинационной схемы будет тем больше, чем меньше W.

109

Алгоритм состоит из нескольких шагов. 1. Построим матрицу

	α	1	β	1
		.	.	.
M =	α	r	β	r	,
		.	.	.
	α	R	β	R

состоящую из всех различных пар номеров (ar, br), таких, что в авто-
ìàòå S есть переход из aα r â aβ r.
2. Переставим строки в матрице так, чтобы выполнялось условие
{α r, β r}∩ {α 1, β 1, ..., α r–1, β r–1}≠ , r=2, ..., R.	(10.1)

Условие (10.1) означает, что хотя бы один из элементов r-й строки содержится в какой-нибудь из предыдущих строк. Имеются в виду только связные автоматы S, для которых такая перестановка всегда возможна.

3. Закодируем состояния из первой строки матрицы M следующим образом:

Kα 1 = (00 ... 00); Kβ 1 = (00 ... 01).

4.Вычеркнем из матрицы M первую строчку, соответствующую закодированным состояниям aα 1, è aβ 1. Получим матрицу M’.

5.В силу условия (1) в начальной строке матрицы M закодирован

один элемент. Выберем из первой строчки матрицы M’ незакодированный элемент и обозначим его через γ .

6.Построим матрицу Mγ , выбрав из M’ строчки, содержащие γ . Пусть Âγ = {γ 1, ..., γ f, ..., γ F} – множество элементов из матрицы Mγ , которые уже закодированы. Их коды обозначим Kγ 1, ..., Kγ f, ..., Kγ F соответственно.

7. Для каждого Kγ f (f = 1, ..., F) найдем C1γ		f – множество кодов,
соседних с Kgf и еще не занятых для кодирования состояний автомата.
	F
Построим множество D1γ = UCγ1 f . Åñëè D1γ =		, то строим новое мно-
F	f =1
жество Dγ2 = UCγ2f	, ãäå Cγ2f – множество кодов, у которых кодовое
f =1

110

расстояние с кодом K		равно двум. Если D2			=	, строим аналогично
	γ f			γ
D3	, ..., Dn , до тех пор пока не найдется		Dn	≠		(n = 1, 2, 3, ...). Пусть
γ	γ		γ

Dγn = { Kδ 1, ..., Kδ g, ..., Kδ G}.

8. Для каждого Kδ g находим Wgf = | Kδ g – Kgf |2 – кодовые расстояния между Kδ g и всеми использованными кодами Kgf (f = 1, ..., F). Åñëè â

автомате имеется переход из aγ f â aγ è èç aγ â aγ f òî Wgf, входит дважды в Wg (см. ниже примеры переходов (a4, a5) è (a5, a4)).

9. Находим W	= ∑F	W , g = 1, ..., G.
g	f =1	gf

10. Èç Dγn выбираем Kγ , у которого Wg = min Wg. Элемент γ (состоя-

γ) кодируем кодом Kγ .

11.Из матрицы M’ вычеркнем строчки, в которых оба элемента закодированы, в результате чего получим новую матрицу, которую такие обозначим через M’. Если в матрице M’ не осталось ни одной строчки, переходим к п.12, иначе к п. 5.

12.Вычисляем функцию W = ∑ tms, ãäå tms = |Km– Ks|2.

13.Конец.

Оценкой качества кодирования по рассмотренному алгоритму может служить число k = W/p, ãäå p – число переходов в автомате. Оче- видно, что k ≥ 1, причем чем меньше значение k, тем ближе кодирование к соседнему , при котором k = 1.

Без подробных объяснений приведем пример кодирования состояний автомата, граф которого изображен на рис. 10.7.

1	2					a	a#
2	4
2	5					a	a"
M = 3	2	K	= 000,	K	2	= 001.
4	3	1
						a!
4	5						Ðèñ. 10.7
5	4
5	1

111

Кодирование будем иллюстрировать диаграммой Вейча.

3																		3
																	3!
			2	4
			2	5									2	4
			3	2
													4 3				= {2}.
M′ =			4 3				γ = 4;		M		4	=				B
													4	5		4
			4	5
													5	4
			5	4
			5	1

C21 ={101, 011}; D41 =C21 ={101, 011}. W101=|101–001|2=1; W011=|011-001|2=1. Выбираем K4=101.

					"
3														3
													3!
		2		5
		3		2					2	5
M′ =		4 3			γ = 5; M		=		4	5			B = {2, 4, 1}.
		4		5	5				5	4			5
		5		4					5	1
		5		1

112

C	1	={011};	C1	={100,111};	C1	={100,010};	D1	=C	1		C1		C1	={011,100,111,010}.
	2		4		1		5		2		4		1

W011=|011–001|2+|011–101|2+|011–101|2+|011–000|2=1+2+2+2=7; W100=|100–001|2+|100–101|2+|100–101|2+|100–000|2=2+1+1+1=5; W111=|111–001|2+|111–101|2+|111–101|2+|111–000|2=2+1+1+3=6; W010=|010–001|2+|010–101|2+|010–101|2+|010–000|2=2+3+3+1=9.

W100=min{W001, W100, W111, W010}. Следовательно выбираем K5=100.

				#			"
3															3
													3!
M′ =		3	2		γ = 3;		M		=		3	2		B = {2, 4}.
		4	3				3				4	3		3

C21 ={011}; C41 ={111}; D31 = C21 È C41 ={011, 111}.

W011=|011–001|2+|011–101|2=1+2=3;

W111=|111–001|2+|111–101|2=2+1=3.

W011=W111. Следовательно выбираем K3= 011.

				!
		#	"
3						3
					3!

k = W/p = 10:8 = 1,25.

113