Курсовой проект_Комп_логика_пример_рус

3. Построение графа переходов автомата

На основании таблицы 2.4, построим граф переходов автомата Мура (Рис. 3.1.).

Рис. 3.1. Граф переходов автомата Мура.

4.Построение матрицы переходов триггера

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

(табл. 4.1).

Таблица 4.1 – сокращенная таблица переходов асинхронного триггера

t		t+1
x	y	Q
0	0	Q(t)
0	1	1
1	0	0
1	1	1

11

Построим полную таблицу переходов асинхронного триггера (табл. 4.2), сокращенную таблицу переходов синхронного триггера (табл. 4.3) и полную таблицу переходов синхронного триггера (табл. 4.4).

Таблица 4.2 – полная таблица переходов асинхронного триггера

	t		t+1
x	y	Q	Q
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Таблица 4.3 – сокращенная таблица переходов синхронного триггера

	t		T+1
C	x	y	Q
0	0	0	Q(t)
0	0	1	Q(t)
0	1	0	Q(t)
0	1	1	Q(t)
1	0	0	Q(t)
1	0	1	1
1	1	0	0
1	1	1	1

Таблица 4.4 – полная таблица переходов синхронного триггера

		t		t+1
C	X	y	Q	Q
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1

12

0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Триггер имеет четыре возможные варианта переходов: “0-0”, “0- 1”, “1-0”, “1-1”. В соответствии с ними построим матрицу переходов и соответствующих им сигналов X и Y (табл. 4.5).

Таблица 4.5 – матрица переходов и соответствующих сигналов X и Y

Q(t)	Q(t+1	x	Y
	)
0	0	0	0
		1	0
0	1	0	1
		1	1
1	0	1	0
1	1	0	0

01

11

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

Таблица 4.6 – матрица переходов триггера

0-0	b1	0
0-1	b2	1
1-0	1	0
1-1	b3	b3vb4

Выберем обозначения b3vb4=b5

13

5. Кодирование входных и выходных алфавитов состояний

Для кодирования входных сигналов выписывается множество сигналов Х={х1,…хm}, которые кодируются векторами длины Квх=int(log(m)), где int это округление до ближайшего целого числа, М мощность множества Х (количество символов входного алфавита). Кодирование входных сигналов осуществляется произвольно.

Исходные входные сигналы нашего автомата Мура Х={х1,х2,х3}, следовательно, Квх=int(log(3))=2. Таким образом, нам понадобится два разряда, чтобы закодировать входные сигналы (табл. 5.1).

Таблица 5.1 – кодирование входных сигналов

X	z1	z2
x1	0	0
x2	0	1
x3	1	0

Выходные сигналы автомата Y={y1,..ys} кодируются векторами длины Квых=int(log(S)), где S мощность множества Y (количество символов выходного алфавита).

Исходные выходные сигналы нашего автомата Мура Y={y1,y2,y3,y4}, следовательно, Квых=int(log(4))=2. Два разряда будет достаточно, чтобы закодировать выходные сигналы.

Для кодирования выходного алфавита применяем весовой метод.

Алгоритм весового метода кодирования:

1.Каждому выходному сигналу уі ставится в соответствие целое число Рі, равное числу появлений сигнала уі в таблице выходов автомата.

2.Числа Рі сортируются по убыванию.

3.Выходной сигнал уі с наибольшим весом (Рі max) кодируются кодом, содержащим все 0 (00...00).

14

4.Следующие L выходных сигналов (где L- число разрядов в двоичном векторе выходного сигнала) по списку убывания веса (см п.

2)кодируются кодами, содержащими одну 1 (00...01, 00...10, ...

,10...00)

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

Каждому выходному сигналу поставим в соответствие весовой

коэффициент Р. (таблица 5.2.)

Таблица 5.2 – весовые коэффициенты выходных сигналов

У	P
y1	3
y2	3
y3	1
y4	2

Весовые коэффициенты сортируются по убыванию (таблица

5.3.).

Таблица 5.3
	У		P
	y1		3
	y2		3
	y4		2
	y3		1

Таблица 5.4 – кодирование выходных сигналов

У	w1	w2
y1	0	0
y2	0	1
y4	1	0
y3	1	1

15

6 Кодирование алфавита состояний автомата

Состояния автомата А={а1,а2…,аr} кодируются векторами длины Ксост=int(log(r)), где r мощность множества A (количество состояний). Отметим, что длина вектора состояний определяет и количество элементов памяти (триггеров) данного автомата.

Состояния автомата А={а1, а2, а3, а4, а5, а6, а7, а8, а9} кодируются векторами длины Ксост=int(log(10))=4. Для кодирования будем использовать эвристический метод, который позволяет наиболее эффективно подобрать коды состояний для получения наилучшего коэффициента эффективности кодирования Кэф=W/P, где P- общее количество переходов автомата, а W - весовая функция.

W= tij ,

где tij - расстояние Хэмминга между кодами состояний ai и aj,

Алгоритм состоит из следующих шагов:

1.Построить матрицу М, составленную из всех пар номеров (аr, br) переходов автомата.

2.Переставим строки в матрице таким образом, чтобы в каждой

последующей строке содержался хотя бы один элемент из предыдущих строк.

3.Закодируем состояния из первой строки матрицы М следующим образом: Ка1=00...00, Кb1=00...01.

4.Вычеркнем из матрицы М первую строку с закодированными

состояниями. Получим матрицу М`.

5.В силу п. 3 в начальной строке матрицы М’ закодирован один элемент. Выберем из первой строки матрицы М` незакодированный элемент и обозначим

его γ.

6.Построим матрицу Мγ, выбрав из матрицы М` строки, содержащие γ.

Пусть Вγ={γ1, γ2,…, γf,…, γF} – множество элементов из матрицы Мγ, которые

уже закодированы. Их коды обозначим через Кγ1, Кγ2,…,Кγf,…,КγF

соответственно.

7.Для каждого Кγf (f=1, 2, …,F) найдем C1f - множество кодов, отстоящих

от Кγf на расстояние Хэмминга, равное 1 и еще не занятых для кодирования

16

			F
состояний автомата.	Построим множествоD1 = C1f . Если			D1 =0, то
			f 1
	F
строим новое множество D2 = C 2f , где		C2f -	множество кодов,	у которых
	f 1
кодовое расстояние с кодом Кγf равно 2. Если и D2			=0, строим D3 и т.д., пока не
найдем Dn ≠0. Пусть Dn	={Кγ1,…, Кγg,…, КγG}.

8.Для каждого КγG находим wgf=| Кγg- Кγf|2 – расстояние Хэмминга между Кγ g

ивсеми используемыми кодами Кγf (f=1, 2, …,F).

F

9. Находим wg = wgf, (g=1,…,G).

f1

10.Из Dn выбираем Кγ, у которого wg = wg min. Элемент γ кодируем кодом

Кγ.

11.Из матрицы М` вычеркиваем строки, в которых оба элемента

закодированы, в результате чего получаем новую матрицу, которую также

обозначаем М`. Если в матрице М` не осталось ни одной строки, переходим к п. 12, иначе к п. 5.

12.Вычисляем функцию w=∑tms, где tms|Km-Ks|2.

13.Конец.

Оценкой качества кодирования по рассмотренному алгоритму может

служить число К=W/P, где Р – число переходов в автомате. Очевидно, что К≥1, причем, чем меньше значение К, тем лучше результат кодирования.

Для начала кодирования построим матрицу переходов автомата М. Первые две строки в матрице М кодируем: K1=0000 и K5=0001. Далее следуем эвристическому методу кодирования.

17

		1-5		В матрице М вычеркнем первую строку(1-5) и те
		1-1		строки, которые оказались полностью закодированными
		1-7		(1-1, 5-1).
		2-1
		2-3			1-7		Получим матрицу М`.
		2-4
		3-6			2-3		В матрице М`			в первой строке не
		3-3			2-1
		3-5			2-4		закодирован элемент 7. γ=7. Строим
		4-4			3-6
		4-6			3-3		матрицу Мγ (М7), выбрав из матрицы М`
		4-2			3-5		все строки, содержащие γ (7).
		5-7			4-4
М=		5-1			4-6
		5-8			4-2			1-7
		6-5			5-7			5-7
		6-9		М`=	5-8		М7=	7-4
		6-8			6-5			7-8
		7-4			6-9			7-1
		7-8			6-8			9-7
		7-1			7-4		В7={1, 5}={0000, 0001} –				множество
		8-9			7-8
		8-1			7-1		элементов из матрицы М7, которые уже
		8-3			8-9
		9-7			8-1		закодированы. Для			каждого	элемента
		9-9			8-3		этого множества найдем множества
		9-1			9-7
					9-9
					9-1

C1f C711 ={0010, 0100, 1000};

C1f C751 ={0011, 0101, 1001};

D71 {0010, 0100, 1000, 0011, 0101, 1001};

Для каждого кода из множества D71 найдем wgf= кδg- кγf 2 - межкодовое

										F
расстояние Хэмминга и wg wgf
										f 1
	1-7				5-7				7-1
W0010=		0000		+		0001		+		0010		=	4
		0010				0010				0000
W0100=		0000		+		0001		+		0100		=	4
		0100				0100				0000

18

W1000=		0000		+		0001		+		1000		=	4
		1000				1000				0000
W0011=		0000		+		0001		+		0011		=	5
		0011				0011				0000
W0101=		0000		+		0001		+		0101		=	5
		0101				0101				0000
W1001=		0000		+		0001		+		1001		=	5
		1001				1001				0000

Выбираем код, для которого wg имеет минимальное значение.

К7=0010.

Из матрицы М` вычеркнем первую строку (1-7) и те строки, которые оказались полностью закодированными (5-7, 7-1). В результате получаем новую матрицу М`, в первой строке которой не закодирован элемент 2. . γ=2. Строим матрицу Мγ (М2), выбрав из матрицы М` все строки, содержащие γ (2).

	2-1			2-1
	2-3	М2=		2-3
	2-4			2-4
	3-6			4-2
	3-3		В2={1}={0000} – множество элементов из матрицы
	3-5
		М2, которые уже закодированы. Найдем множества
	4-4
	4-6	C1f C211 ={0100, 1000};
	4-2
М`=	5-8	D21 {0100, 1000};
	6-5		Для каждого кода из множества D21 найдем
	6-9
	6-8		wgf= кδg- кγf 2 - межкодовое расстояние по Хэммингу.
	7-4
	7-8	W0100=				0100				=	1
	8-9					0000
	8-1
	8-3	W1000=				1000				=	1
	9-7					0000
	9-9
	9-1	Выбираем К2=0100.
											19

Из матрицы М` вычеркнем первую строку (2-1). В результате получаем новую матрицу М`, в первой строке которой не закодирован элемент 3. . γ=3. Строим матрицу Мγ (М3), выбрав из матрицы М` все строки, содержащие γ (3).

2-3

2-4

3-6

3-3

3-5

4-4

4-6

4-2

5-8

М`= 6-5 6-9

6-8

7-4

7-8

8-9

8-1

8-3

9-7

9-9

9-1

		2-3		В3={2, 5}={0100, 0001} – множество
		3-6		элементов из матрицы М3, которые уже
М3=		3-3
		3-5		закодированы. Найдем множества
		8-3		C1f C321 ={0101, 0110, 1100};

C1f C351 ={1001, 1010, 1100};

D31 {0101, 0110, 1100, 1001};

Для каждого кода из множества D31 найдем wgf= кδg- кγf 2 - межкодовое расстояние по Хэммингу.

	2-3				3-3				3-5
W0101=		0100		+		0101		+		0101		=	2
		0101				0101				0001
W0110=		0100		+		0110		+		0110		=	4
		0110				0110				0001

W1100=		0100		+		1100		+		1100		=	4
		1100				1100				0001
W1010=		0100		+		1010		+		1010		=	6
		1010				1010				0001

Выбираем код с минимальным значеним W.

К3=0101.

Из матрицы М` вычеркнем первую строку (2-3) и те строки, которые оказались полностью закодированными (3-3, 3-5). В результате получаем новую матрицу М`, в первой строке которой не

20