KL_kur_met

11

Z
1	Z

1	1	1	1	W 1	9	1	X 1
2		5			10
					11
Z	2	6	1	W 2	8		r 1
3		7
1		Z			1		X 2
						3
2	3	1		9
3		3			12	1
							r 2
2		2		10	13
	4				14
3		2
1	5	Z		11	15	1	u 3
3		3			16
1	6	4		12	1		r 3
2		Z			3
1		Z		13
2	7	4
3		Z
				14
1		8
	8
2
		3		15
		1
		Z		16
		4

X 1	1	1
r 1		1
X 2	2	2
r 2		2	W 1

W 2

u 3	3	3
r 3		3

1

Рис. 7. 5 Функциональная схема автомата.

12

ПРИЛОЖЕНИЕ 1

МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ АВТОМАТА. АЛГОРИТМ АУФЕНКАМПА-ХОНА

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

Два состояния автомата аm и as называются эквивалентными (аm ≡ as), если λ (аm, X) = λ (as, X) для всех возможных входных слов длины X.

Если аm и as не эквивалентны, они различимы. Более слабой эквивалентностью является К-эквивалентность. Состояния аm и as К-эквивалентны, если λ (аm, Xk) = λ ( as, Xk)для всех возможных входных слов длины К.

При минимизации числа внутренних состояний автомата Мили S= {X, Y, A, λ, δ, a0} используется алгоритм Ауфенкампа-Хона:

1.Находят последовательные разбиения π1, π 2,..., π к, π к+1, множества А на классы одно-, двух-, ..., К-, (К+1)-эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге

не окажется, что πк= πк+1. В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором πк= πк+1, не превышает N-1, где N- число внутренних состояний автомата.

2.В каждом классе эквивалентности π выбирают по одному элементу (представителю класса), которые образуют множества А’ состояний минимального автомата S’.

3.Функцию переходов δ’ и выходов λ’ автомата S’ определяют на множестве А’xX. Для этого в таблице переходов и выходов вычеркивают столбцы, соответствующие не вошедшим в множество А’ состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А’, (на представителей).

4.В качестве а’0 выбирается одно из состояний, эквивалентное состоянию а0. В частности, удобно принять само состояние а0.

При минимизации автомата Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-эквивалентными называются любые, одинаково отмеченные выходными сигналами, состояния автомата Мура.

В качестве примера рассмотрим минимизацию автомата Мура, заданного таблицей переходов и выходов (Таблица П.1.1.).

Таблица П.1.1

У

у1

у1

у3

у3

у3

у2

у3

у1

у2

у2

у2

у2

А

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

х1

а10

а12

а5

а7

а3

а7

а3

а10

а7

а1

а5

а2

х2

а5

а7

а6

а11

а9

а11

а6

а4

а6

а8

а9

а8

Выполним разбиение π0:

π0={В1,В2,В3}; В1={а1, а2, а8}, В2={а6, а9, а10, а11, а12}, В3={а3, а4, а5, а7}.

13

Построим таблицу разбиения π0:

У

В1

В2

В3

А

а1

а2

а8

а6

а9

а10

а11

а12

а3

а4

а5

а7

х1

В2

В2

В2

В3

В3

В1

В3

В1

В3

В3

В3

В3

х2

В3

В3

В3

В2

В2

В1

В2

В1

В2

В2

В2

В2

Выполним разбиение π1:

π1={С1,С2,С3,С4}; С1={а1, а2, а8}, С2={а6, а9, а11,}, С3={ а10, а12}, С3={а3, а4, а5, а7}.

У

С1

С2

С3

С4

А

а1

а2

а8

а6

а9

а11

а10

а12

а3

а4

а5

а7

х1

С3

С3

С3

С4

С4

С4

С1

С1

С4

С4

С4

С4

х2

С4

С4

С4

С2

С2

С2

С1

С1

С2

С2

С2

С2

Выполним разбиение π2:

π1={D1,D2,D3,D4};

D1={а1, а2, а8}, D2={а6, а9, а11,}, D3={ а10, а12}, D3={а3, а4, а5, а7}.

Разбиение π2 повторяет разбиениеπ1 – процедура разбиения завершена.

Выберем произвольно из каждого класса эквивалентности D1, D2, D3, D4 по одному представителю – в данном случае по минимальному номеру: А’={а1, а3, а6, а10}.

Удаляя из исходной таблицы переходов “лишние” состояния, определяем минимальный автомат Мура:

У	у1	у3	у2	у2
А	а1	а3	а6	а10
х1	а10	а3	а3	а1
х2	а3	а6	а6	а1

14

ПРИЛОЖЕНИЕ 2

ЭВРИСТИЧЕСКИЙ АЛГОРИТМ КОДИРОВАНИЯ СОСТОЯНИЙ СТРУКТУРНОГО АВТОМАТА

Эвристический алгоритм кодирования состояний (предложен Д.А.Морозом) минимизирует суммарное число изменений элементов памяти на всех переходах автомата

[1].

Введем весовую функцию W= t ij ,

где 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 и еще не занятых для кодирования состояний автомата.

F	F
Построим множествоD1 = C1f . Если D1 =0, то строим новое множество D 2	= C 2f , где
f 1	f 1
C 2f - множество кодов, у которых кодовое расстояние с кодом Кγ f равно 2.	Если и D 2 =0,

строим D 3 и т.д., пока не найдем D n ≠0. Пусть D n ={Кγ 1,…, Кγ g,…, Кγ G}.

8. Для каждого Кγg находим wgf=| Кγg- Кγf|2 – расстояние Хэмминга между Кγ g и всеми используемыми кодами Кγ f (f=1, 2, …,F).

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

f1

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

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

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

13.Конец.

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

	15
	ПРИЛОЖЕНИЕ 3
Таблицы переходов автоматов
Вариант № 1	Вариант № 2

	у1	у2	у2	у4		у3	у2	у1	у2	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	3	1		6	7	2	1	7	10	10
х2	4	2	2		8	2	4	5	1	3	7
х3	1	5	4		9	4	1	3	2	1	8
	Вариант № 3
	у1	у2	у3	у4		у3	у2	у1	у4	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	1	2	9		5	6	1	10	6	9	9
х2	9	1	1		7	1	3	4	10	2	6
х3	3	4	3		8	3	10	2	9	10	8
	Вариант № 5
	у2	у2	у3	у4		у1	у2	у1	у4	у1	у2
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	6	3	10		3	9	5	1	3	1	8
х2	4	2	3		7	4	3	4	7	7	2
х3	9	9	7		5	1	7	3	5	9	9
	Вариант № 7
	у1	у2	у3	у4		у1	у2	у3	у4	у1	у2
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	3	6		4	7	5	4	9	7	2
х2	5	1	3		6	10	9	8	10	9	3
х3	7	4	5		2	8	8	1	3	10	5
	Вариант № 9
	у1	у3	у2	у4		у3	у2	у1	у4	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	2	9		5	6	1	9	6	9	9
х2	9	1	8		7	1	3	4	10	2	5
х3	3	4	3		8	4	10	2	9	10	8
	Вариант № 11
	у1	у2	у3	у4		у3	у2	у1	у2	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	5	2	9		5	3	1	2	6	9	8
х2	9	1	6		7	2	3	4	10	2	6
х3	2	6	3		8	4	10	10	9	10	9
	Вариант № 13
	у1	у2	у3	у4		у3	у2	у1	у2	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	8	5	2		5	1	7	7	3	3	4
х2	6	4	5		9	6	4	5	6	9	6
х3	1	1	9		7	3	6	10	5	1	8

	у2	у3	у2	у1		у2	у1	у4	у2	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	6	1		5	7	2	1	7	8	10
х2	5	2	3		8	8	4	5	1	3	7
х3	1	5	4		9	4	1	3	2	1	8
	Вариант № 4
	у1	у3	у2	у4		у1	у2	у4	у2	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	4	5	2		8	9	4	7	9	2	5
х2	2	4	4		10	4	6	3	3	5	4
х3	6	7	6		1	6	3	5	2	3	7
	Вариант №6
	у1	у3	у2	у4		у1	у2	у4	у2	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	5	2	9		2	8	1	4	10	7	9
х2	3	1	2		6	3	4	2	3	5	6
х3	8	8	6		4	10	3	6	2	4	10
	Вариант № 8
	у1	у2	у3	у4		у1	у2	у4	у2	у1	у1
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	7	6		5	1	4	5	7	8	1
х2	6	9	5		9	3	8	3	2	2	3
х3	9	5	1		3	8	7	10	2	4	8
	Вариант № 10
	у2	у3	у4	у1		у1	у2	у4	у2	у1	у2
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	8	5	2		6	9	4	6	9	2	5
х2	2	2	4		10	4	6	3	2	5	3
х3	6	4	6		1	6	3	5	3	3	7
	Вариант № 12
	у1	у3	у2	у4		у1	у2	у4	у2	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	1	9	6		8	9	4	7	9	2	9
х2	3	4	10		5	4	6	3	3	5	4
х3	10	2	9		1	6	3	5	2	3	2
	Вариант № 14
	у1	у3	у2	у4		у1	у2	у4	у2	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	9	1	5		6	10	1	7	8	3	8
х2	4	2	1		2	3	4	5	5	1	4
х3	6	5	4		7	8	5	10	10	10	9

16

Вариант № 15

	у1	у2	у3	у4		у4	у2	у1	у3	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	10	2	6		7	1	2	8	9	4	9
х2	5	3	2		3	4	5	6	6	2	6
х3	7	6	5		8	9	4	1	2	10	1
	Вариант № 17
	у1	у2	у3	у4		у3	у4	у1	у4	у1	у2
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	10	2	9		5	3	1	10	3	9	9
х2	8	1	3		7	5	3	4	5	2	6
х3	3	4	3		8	7	10	2	7	10	7
	Вариант №19
	у1	у3	у2	у3		у4	у2	у1	у4	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	6	9	6		2	3	8	7	3	6	6
х2	7	8	8		4	8	10	1	7	9	3
х3	10	1	10		5	1	5	9	6	7	4
	Вариант №21
	у2	у3	у4	у1		у4	у2	у1	у4	у2	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	3	1	4		7	9	5	3	9	10	6
х2	4	5	6		2	7	8	9	10	8	1
х3	2	3	8		6	3	2	7	6	6	7
	Вариант №23
	у1	у3	у2	у3		у4	у2	у2	у4	у1	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	2	1	5		8	4	10	10	6	6	3
х2	9	7	8		2	9	7	8	8	2	9
х3	10	3	10		5	1	5	9	5	7	4
	Вариант № 25
	у1	у2	у3	у4		у4	у2	у1	у3	у1	у4
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	10	2	6		7	1	2	8	9	4	9
х2	4	5	9		2	7	8	9	10	8	1
х3	2	3	8		6	3	9	7	6	6	7
	Вариант № 27
	у2	у3	у4	у1		у4	у2	у1	у4	у2	у3
А	а1	а2	а3	а4		а5	а6	а7	а8	а9	а10
х1	5	2	9		5	3	1	2	6	9	8
х2	9	1	6		7	2	3	4	10	2	6
х3	2	3	8		6	4	9	7	10	6	7

Вариант № 16

	у4	у3	у2	у1	у4	у2	у4	у2	у2	у3
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	1	3	7	8	2	3	9	10	7	2
х2	6	5	3	4	5	6	7	5	3	6
х3	8	7	6	9	10	5	2	3	6	1
	Вариант № 18
	у1	у3	у2	у4	у1	у2	у4	у2	у1	у3
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	3	5	2	8	3	4	7	9	2	5
х2	5	4	4	10	5	6	3	6	5	4
х3	7	7	6	9	7	3	5	2	3	7
	Вариант № 20
	у1	у3	у4	у1	у3	у2	у4	у2	у1	у2
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	2	1	5	8	4	10	10	6	6	3
х2	9	7	8	2	9	7	8	8	2	9
х3	7	4	2	10	6	9	2	9	4	7
	Вариант № 22
	у4	у3	у1	у1	у3	у2	у4	у2	у1	у2
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	8	1	5	4	6	3	2	9	1	5
х2	6	6	6	3	8	2	6	2	7	2
х3	7	9	7	1	10	8	9	3	5	8
	Вариант № 24
	у1	у3	у4	у1	у3	у2	у4	у2	у1	у2
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	6	9	6	2	3	8	7	3	6	6
х2	7	8	5	4	8	10	1	7	9	3
х3	4	4	2	10	6	9	2	9	4	7
	Вариант № 26
	у4	у1	у3	у4	у1	у4	у2	у2	у2	у3
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	9	7	8	3	9	7	8	8	2	9
х2	7	4	2	10	6	9	2	9	4	7
х3	8	6	6	9	10	5	1	3	6	1
	Вариант № 28
	у4	у3	у1	у1	у3	у2	у4	у2	у1	у2
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	2	7	6	5	1	4	5	7	8	1
х2	6	9	5	4	3	8	3	2	2	3
х3	8	6	7	9	10	5	1	3	6	10

Вариант № 29

	у1	у2	у2	у4	у3	у2	у1	у2	у1	у4
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	10	2	6	7	1	2	8	9	4	9
х2	5	3	2	3	4	5	6	6	2	6
х3	7	6	5	8	9	4	1	2	10	1

17

Вариант № 30

	у2	у3	у2	у1	у2	у1	у4	у2	у1	у4
А	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10
х1	9	7	8	3	9	7	8	8	2	9
х2	6	5	2	1	4	10	2	6	4	7
х3	8	6	4	9	7	1	6	7	6	1

ПРИЛОЖЕНИЕ 4

Варианты используемых триггеров
Входы												Номер варианта
Х	У		1			2		3	4	5		6	7							8	9		10					11		12		13					14
0	0		Q(t)			1		0	0	1		Q(t)		0			0				Q(t)			Q(t)					1		1	0					Q(t)
0	1		0			0		1	1	Q(t)		1	Q(t)								1			1					0		1	Q(t)					1
																		Q(t)
1	0		Q(t)			Q(t)		0	Q(t)	0		0		1			0				0			1					1		Q(t)	0					0
1	1		1			Q(t)		Q(t)	1	0		1	Q(t)				1				0			Q(t)				Q(t)			0	1					0
Входы												Номер варианта
Х	У		15			16		17	18	19		20		21			22					23			24				25		26		27					28
0	0		1			1		0	1	1		1					Q(t)					Q(t)			1				0		0		Q(t)					0
														Q(t)
0	1		Q(t)			Q(t)		1	1	0		Q(t)		1			0					Q(t)							Q(t)		0		0					0
																										Q(t)
1	0					0		Q(t)	0	Q(t)		1	Q(t)				1					1			Q(t)				1		Q(t)							0
																																		Q(t)
				Q(t)
1	1		0			Q(t)		Q(t)	Q(t)	0		0		0			1					0					1		1		1		1					1
																ПРИЛОЖЕНИЕ 5
Матрицы переходов стандартних триггеров.
	Триггер-D									Триггер-T																Триггер-RS																Триггер-JK
Q(t)			Q(t+1)					D	Q(t)		Q(t+1)				T					Q(t)						Q(t+1)					R						S				Q(t)	Q(t+1)	K	J
0			0					0	0			0			0					0				0							0						0				0	0	0	0
0			1					1	0			1			1					0				1							0						1				0	1	0	1
1			0					0	1			0			1					1				0							1						0				1	0	1	0
1			1					1	1			1			0					1				1							0						0				1	1	0	0

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.Баранов С. И. Синтез микропрограммных автоматов. – Л., Энергия. 1979.

2.Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. – Л. Машиностроение. 1979.