Санкт-Петербургский Государственный Электротехнический Университет «лэти»

(СПбГЭТУ)

Кафедра ВТ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине:

«МИКРОПРОГРАММНОЕ УПРАВЛЕНИЕ В ЭВМ И

ТЕОРИЯ АВТОМАТОВ»

Выполнил:

ст. гр. 4371

Фадеев С.А.

Преподаватель:

Альшевский А.Н.

Санкт-Петербург

2007 г

1. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

№ вар.	Вариант алгор.	Вариант влияния микрооп	Тип логич. элемента	Коэф. развет	Тип триг-гера	Кол. вых. ПЗУ	Кол. термов ПЛМ	Кол. вых. ПЛМ
24	24	24	3ИЛИ,НЕ	8	J, K	8	8	4

Количество входов у ПЗУ и ПЛМ во всех вариантах равно 6.

24	X1	X2	X3
Y0		
Y1	0
Y2	1		
Y3			
U0	1	0	1

2. АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТА

1. Граф автомата Мура

Начальной и конечной вершинам ГСА (графическая схема алгоритма) сопоставляем начальное состояние автомата S0, остальным операторным вершинам, независимо от содержащихся в них микроопераций, произвольно сопоставляем неповторяющиеся символы состояний S1, S2, S3 и т.д. (см. рис. 1).

Р s6 s7 s0ис. 1. Графическая схема алгоритма.

Закодируем для удобства все возможные входные сигналы X1,X2,X3, символамиPi:

X1	X2	X3	Pi
0	0	0	P0
0	0	1	P1
0	1	0	P2
0	1	1	P3
1	0	0	P4
1	0	1	P5
1	1	0	P6
1	1	1	P7

Закодируем для удобства все возможные выходные сигналы Y0,Y1,Y2,Y3, символамиWi:

Y0	Y1	Y2	Y3	Wi
1	0	0	0	W0
0	1	0	0	W1
0	0	1	0	W2
0	0	0	1	W3
0	1	0	1	W4
0	1	1	0	W5

Граф полностью определённого автомата Мура, реализующего исходную ГСА, представлен на рис.2:

Рис. 2. Граф полностью определённого автомата Мура.

Необходимым, но недостаточным условием правильности построения автомата Мура по ГСА, является существование переходов из каждого состояния по каждому набору значений логических условий:

Wi	Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
W0	S0	S1	S1	S1	S1	S1	S1	S1	S1
W3	S1	S8	S3	S2	S2	S6	S3	S2	S2
W5	S2	S2	S2	S2	S2	S6	S3	S4	S3
W1	S3	S7	S8	S7	S4	S7	S6	S7	S4
W4	S4	S5	S5	S5	S5	S5	S5	S5	S5
W2	S5	S0	S0	S0	S0	S0	S0	S0	S0
W2	S6	S8	S8	S8	S8	S8	S8	S8	S8
W2	S7	S0	S0	S0	S0	S0	S0	S0	S0
W3	S7	S0	S0	S0	S0	S0	S0	S0	S0

Создание теста автомата

Тест составляется по заданной графической схеме алгоритма путём полного обхода всех вершин схемы:

XI	ZZZ	Z01	ZZ0	ZZZ	ZZZ	Z1Z	0ZZ	110	ZZZ	ZZZ
YI	Y3	Y1	Y2	Y0	Y3	Y1,Y2	Y1,Y2	Y1,Y3	Y2	Y0
Pi	P0-P7	P1,P5	P0, P2, P4, P6	P0-P7	P0-P7	P2, P3, P6, P7	P0-P3	P6	P0-P7	P0-P7
Wi	W3	W1	W2	W0	W3	W5	W5	W4	W2	W0
XI	ZZZ	Z01	001	ZZZ	ZZZ	Z1Z	100	ZZZ	ZZZ
YI	Y3	Y1	Y3	Y0	Y3	Y1,Y2	Y2	Y3	Y0
Pi	P0-P7	P1,P5	P1	P0-P7	P0-P7	P2, P3, P6, P7	P4	P0-P7	P0-P7
Wi	W3	W1	W3	W0	W3	W5	W2	W3	W0

1. Проверка автомата Мура

Для проверки мы подаём на вход автомата Мура тестовую последовательность входных сигналов и сравниваем выходные сигналы автомата. Тест считается пройденным, если последовательность выходных сигналов автомата Мура совпадёт с последовательностью выходных сигналов теста автомата, созданного по заданной графической схеме.

Pi	P0-P7	P1,P5	P0, P2, P4, P6	P0-P7	P0-P7	P2, P3, P6, P7	P0-P3	P6	P0-P7	P0-P7
Si	S0	S1	S3	S7	S0	S1	S2	S2	S4	S5
Wi		W3	W1	W2	W0	W3	W5	W5	W4	W2
Pi	P0-P7	P1,P5	P1	P0-P7	P0-P7	P2, P3, P6, P7	P4	P0-P7	P0-P7
Si	S0	S1	S3	S8	S0	S1	S2	S6	S8	S0
Wi	W0	W3	W1	W3	W0	W3	W5	W2	W3	W0

Тест сошёлся.

2. Переход к автомату Мили

В результате переноса для каждого состояния выходных сигналов, которыми отмечены эти состояния, на входящие дуги получается граф автомата Мили, представленный на рис.3:

Рис. 3. Граф автомата Мили.

1. Проверка автомата Мили

Для проверки мы подаём на вход автомата Мили тестовую последовательность входных сигналов и сравниваем выходные сигналы автомата. Тест считается пройденным, если последовательность выходных сигналов автомата Мили совпадёт с последовательностью выходных сигналов теста автомата, созданного по заданной графической схеме.

Pi	P0-P7	P1,P5	P0, P2, P4, P6	P0-P7	P0-P7	P2, P3, P6, P7	P0-P3	P6	P0-P7	P0-P7
Si	S0	S1	S3	S7	S0	S1	S2	S2	S4	S5
Wi		W3	W1	W2	W0	W3	W5	W5	W4	W2
Pi	P0-P7	P1,P5	P1	P0-P7	P0-P7	P2, P3, P6, P7	P4	P0-P7	P0-P7
Si	S0	S1	S3	S8	S0	S1	S2	S6	S8	S0
Wi	W0	W3	W1	W3	W0	W3	W5	W2	W3	W0

Тест сошёлся, значит этап не содержит ошибок.

2. Поиск эквивалентных состояний

Составим таблицу переходов:

Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
S0	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3
S1	S8/W3	S3/W1	S2/W5	S2/W5	S6/W2	S3/W1	S2/W5	S2/W5
S2	S2/W5	S2/W5	S2/W5	S2/W5	S6/W2	S3/W1	S4/W4	S3/W1
S3	S7/W2	S8/W3	S7/W2	S4/W4	S7/W2	S6/W2	S7/W2	S4/W4
S4	S5/W2	S5/W2	S5/W2	S5/W2	S5/W2	S5/W2	S5/W2	S5/W2
S5	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0
S6	S8/W3	S8/W3	S8/W3	S8/W3	S8/W3	S8/W3	S8/W3	S8/W3
S7	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0
S8	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0

Проверка эквивалентности:

S1

X

S2

X

X

S3

X

X

X

S4

X

X

X

X

S5

X

X

X

X

X

S6

X

X

X

X

X

X

S7

X

X

X

X

X

*

X

S8

X

X

X

X

X

*

X

*

S0

S1

S2

S3

S4

S5

S6

S7

S5~S7~S8 – состоянияS5,S7 иS8 эквивалентны, поэтому эти состояния можно объединить вS7:

3. Объединение эквивалентных состояний

Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
S0	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3	S1/W3
S1	S7/W3	S3/W1	S2/W5	S2/W5	S6/W2	S3/W1	S2/W5	S2/W5
S2	S2/W5	S2/W5	S2/W5	S2/W5	S6/W2	S3/W1	S4/W4	S3/W1
S3	S7/W2	S7/W3	S7/W2	S4/W4	S7/W2	S6/W2	S7/W2	S4/W4
S4	S7/W2	S7/W2	S7/W2	S7/W2	S7/W2	S7/W2	S7/W2	S7/W2
S6	S7/W3	S7/W3	S7/W3	S7/W3	S7/W3	S7/W3	S7/W3	S7/W3
S7	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0	S0/W0

После объединения этих эквивалентных состояний получаем автомат Мили, изображенный на рис. 4.

Рис. 3. Граф автомата Мили с убранной эквивалентной вершиной.

1. Проверка автомата Мили

Для проверки мы подаём на вход автомата Мили тестовую последовательность входных сигналов и сравниваем выходные сигналы автомата. Тест считается пройденным, если последовательность выходных сигналов автомата Мили совпадёт с последовательностью выходных сигналов теста автомата, созданного по заданной графической схеме.

Pi	P0-P7	P1,P5	P0, P2, P4, P6	P0-P7	P0-P7	P2, P3, P6, P7	P0-P3	P6	P0-P7	P0-P7
Si	S0	S1	S3	S7	S0	S1	S2	S2	S4	S5
Wi		W3	W1	W2	W0	W3	W5	W5	W4	W2
Pi	P0-P7	P1,P5	P1	P0-P7	P0-P7	P2, P3, P6, P7	P4	P0-P7	P0-P7
Si	S0	S1	S3	S8	S0	S1	S2	S6	S8	S0
Wi	W0	W3	W1	W3	W0	W3	W5	W2	W3	W0

Тест сошёлся, значит этап не содержит ошибок.

3. Учёт взаимодействия управляющего и операционного автоматов

Перед началом работы автомата на его входы подаётся набор значений логических условий

X1X2X3 = 101. Для определения наборов значений логических условий надо последовательно и многократно просмотреть все пути в графе автомата до тех пор, пока для каждого состояния Si его множество входных наборов Ui не будет устойчивым. Схема просмотренных путей в графе приведена на рис.5(см. приложение 1):

1. Минимизация частичного автомата Мили

U0 = {100}, {101}, {110}, {111} = {P4, P5, P6, P7}

U1= {000}, {001}, {010}, {011} = {P0,P1,P2,P3}

U2= {010}, {011}, {110}, {111} = {P2,P3,P6,P7}

U3= {001}, {011} = {P1,P3}

U4 = {010}, {011}, {110} = {P2,P3, P6}

U5 = {110}, {111} = {P6, P7}

U6 =-

U7 =-

U8= {100}, {101} = {P4, P5}

Т.к. U5~U7~U8 (эквивалентны), тоU7 = {U5}U{U7}U{U8}= {P4,P5,P6,P7}

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

Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
S0	-	-	-	-	S1/W3	S1/W3	S1/W3	S1/W3
S1	S7/W3	S3/W1	S2/W5	S2/W5	-	-	-	-
S2	-	-	S2/W5	S2/W5	-	-	S4/W4	S3/W1
S3	-	S7/W3	-	S4/W4	-	-	-	-
S4	-	-	S7/W2	S7/W2	-	-	S7/W2	-
S7	-	-	-	-	S0/W0	S0/W0	S0/W0	S0/W0

Граф частичного автомата Мили изображён на рис. 6.

Рис. 6. Граф частичного автомата Мили.

Проверка минимального автомата Мили

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

XI	101	000	101	111	010	011	110	011	110	100
YI	Y3	Y3	Y0	Y3	Y1,Y2	Y1,Y2	Y1,Y3	Y2	Y0	Y3
Pi	P5	P0	P5	P7	P2	P3	P6	P3	P6	P4
Wi	W3	W3	W0	W3	W5	W5	W4	W2	W0	W3
XI	001	001	100	110	011	111	011	Z10	111
YI	Y1	Y3	Y0	Y3	Y1,Y2	Y1	Y1,Y3	Y2	Y0
Pi	P1	P1	P4	P6	P3	P7	P3	P2,P6	P7
Wi	W1	W3	W0	W3	W5	W1	W4	W2	W0

Проверка графа частичного автомата Мили производится аналогично проверке в пункте 2.2.1.

Pi

P5

P0

P5

P7

P2

P3

P6

P3

P6

P4

Si

S0

S1

S7

S0

S1

S1

S1

S4

S7

S0

Wi

W3

W3

W0

W3

W5

W5

W4

W2

W0

Pi

P1

P1

P4

P6

P3

P7

P3

P2,P6

P7

Si

S1

S0

S7

S0

S1

S1

S0

S4

S7

S0

Wi

W3

W1

W3

W0

W3

W5

W1

W4

W2

W0

Тест сошёлся, значит этап не содержит ошибок.

2. Поиск пар совместимых состояний

Совместимые состояния:

S1	~
S2	X	~
S3	~	X		X
S4	X	X		X		X
S7	X	~		X		~		X
	S0	S1		S2		S3		S4

S0~S1

S0~S3

S1~S2

S1~S7

S3~S7

{S0,S1,S2,S3,S4,S7}

S0≠S2,S7

{S1,S2,S3,S4,S7}

{S0,S1,S3}

S1≠S3

{S1,S2,S7}

{S0,S1,S3}

{S3,S4,S7}

S4≠S3,S7

{S1,S2}

{S1,S7}

{S0,S1}

{S0,S3}

{S3,S7}

{S4}

	S0	S1	S2	S3	S4	S7
C1	V	V
C2	V			V
C3				V		V
C4					V
C5		V	V
C6		V				V

S0 = C2 = {S0,S3}

S1 = C1 = {S1,S2}

Используя новые состояния, получаем таблицу частичного автомата Мили:

Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
S0	-	S7/W3	-	S4/W4	S1/W3	S1/W3	S1/W3	S1/W3
S1	S7/W3	S0/W1	S1/W5	S1/W5	-	-	S4/W4	S0/W1
S4	-	-	S7/W2	S7/W2	-	-	S7/W2	-
S7	-	-	-	-	S0/W0	S0/W0	S0/W0	S0/W0

Получили граф частичного автомата Мили (см. рис.7).

Рис. 7. Граф частичного автомата Мили.

Проверка графа частичного автомата Мили производится аналогично проверке в пункте 2.2.1.

Pi

P5

P0

P5

P7

P2

P3

P6

P3

P6

P4

Si

S0

S1

S7

S0

S1

S1

S1

S4

S7

S0

Wi

W3

W3

W0

W3

W5

W5

W4

W2

W0

Pi

P1

P1

P4

P6

P3

P7

P3

P2,P6

P7

Si

S1

S0

S7

S0

S1

S1

S0

S4

S7

S0

Wi

W3

W1

W3

W0

W3

W5

W1

W4

W2

W0

Тест сошёлся, значит этап не содержит ошибок.