Цифровые автоматы (КР). Курсовая работа (Цифровые автоматы). Пояснительная записка к курсовой работе по курсу Цифровые автоматы

• Название: Пояснительная записка к курсовой работе по курсу Цифровые автоматы
• Анкор: Цифровые автоматы (КР
• Дата: 09.01.2021
• Размер: 1.34 Mb.
• Имя файла: Курсовая работа (Цифровые автоматы).docx
• Тип: Пояснительная записка; #166740
• страница: 3 из 11

1.4 Минимизация абстрактного автомата Мили

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

Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов.

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

1.5 Составление классов совместимости

Состояния a_i и a_j называются совместимыми, если двигаясь из этих состояний под воздействием любого входного сигнала, автомат индуцирует одинаковое его отображение.

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

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

Задачей минимизации методом расщепления классов является получение как можно меньшего количества классов конечной совместимости. У начального автомата выходы можно сгруппировать в две группы (0/0), (0/1), (1/0). Таким образом, получаем 3 класса первичной совместимости.

Классы первичной совместимости

C1	Z1	Z2
0	1	2
1	1	1
2	1	1
3	2	2
10	2	3
17	2	3
30	2	3

C2	Z1	Z2
4	2	-
5	2	-
6	1	-
7	2	-
8	3	-
12	2	-
13	1	-
15	3	-
22	2	-
23	2	-
24	1	-
26	2	-

C2	Z1	Z2
27	3	-
29	1	-
31	3	3
33	2	-
34	1	-
37	1	-
18	3	2

C3	Z1	Z2
9	1	-
11	2	-
14	2	-
16	1	-
19	3	-
20	3	-
21	1	-
25	2	-
28	1	-

C3	Z1	Z2
32	2	-
35	3	-
36	2	-
38	3	-
39	3	-
40	3	-
41	1	-

Классы двоичной совместимости

E1	Z1	Z2
1	1	3
2	3	3

E2	Z1	Z2
0	1	6

E3	Z1	Z2
3	4	4
10	9	9
17	5	9
30	7	10

E4	Z1	Z2
4	4	-
5	6	-
7	7	-
12	6	-
22	4	-
23	6	-
26	7	-
33	6	-

E5	Z1	Z2
18	10	4

E6	Z1	Z2
6	2	-
13	2	-
24	2	-
29	3	-
34	2	-
37	2	-

E7	Z1	Z2
8	8	-
15	8	-
27	8	-
31	9	10

E8	Z1	Z2
9	2	-
16	2	-
21	2	-
28	2	-
41	2	-

E9	Z1	Z2
11	4	-
14	7	-
25	4	-
32	4	-
36	6	-

E10	Z1	Z2
19	10	-
20	8	-
35	9	-
38	10	-
39	10	-
40	8	-

Классы троичной совместимости

D1	Z1	Z2
1	2	6

D2	Z1	Z2
2	4	5

D3	Z1	Z2
0	1	12

D13	Z1	Z2
6	3	-
13	3	-
24	3	-
34	3	-
37	3	-

D4	Z1	Z2
3	8	10

D5	Z1	Z2
10	17	18

D6	Z1	Z2
17	11	17

D4	Z1	Z2
3	8	10

D7	Z1	Z2
30	15	22

D8	Z1	Z2
4	9	-
22	9	-

D9	Z1	Z2
5	13	-
12	13	-
23	13	-
33	13	-

D10	Z1	Z2
7	14	-
26	14	-

D11	Z1	Z2
18	22	8

D12	Z1	Z2
29	7	-

D14	Z1	Z2
8	16	-
15	16	-
7	16	-

D15	Z1	Z2
31	17	20

D16	Z1	Z2
9	3	-
16	3	-
21	3	-
28	3	-
41	3	-

D17	Z1	Z2
11	9	-
25	10	-
32	9	-

D18	Z1	Z2
14	14	-

D19	Z1	Z2
36	13	-

D20	Z1	Z2
35	19	-

D21	Z1	Z2
20	16	-
40	16	-

D22	Z1	Z2
19	21	-
38	22	-
39	21	-

Классы четверичной совместимости

F1	Z1	Z2		F2	Z1	Z2		F3	Z1	Z2
1	2	6		2	4	5		0	1	23

F4	Z1	Z2
3	8	10

F5	Z1	Z2		F6	Z1	Z2
10	17	19		17	11	18

F7	Z1	Z2		F8	Z1	Z2
30	15	24		4	9	-
				22	9	-

F9	Z1	Z2		F10	Z1	Z2		F11	Z1	Z2
5	13	-		7	14	-		18	23	8
12	13	-		26	14	-
23	13	-
33	13	-

F13	Z1	Z1		F14	Z1	Z2
6	3	-		8	16	-
13	3	-		15	16	-
24	3	-		27	16	-
34	3	-
37	3	-

F12	Z1	Z2
29	7	-

F15		Z1		Z2			F16	Z1	Z2
31		17		21			9	3	-
							16	3	-
							21	3	-
							28	3	-
							41	3	-
F17	Z1		Z2
11	9		-
32	9		-

F18	Z1	Z2		F19	Z1	Z2		F20	Z1	Z2
25	10	-		14	14	-		36	13	-

F21	Z1	Z2		F22	Z1	Z2		F23	Z1	Z2
35	20	-		20	16	-		19	22	-
				40	16	-		39	22	-

F24	Z1	Z2
38	23	-

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

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