Файл: Отчет по курсовому проекту по курсу Теория автоматов (наименование учебной дисциплины ).docx

2 Синтез цифрового автомата по граф-схеме алгоритма

Рисунок 2.1 – Алгоритм функционирования
Синтез микропрограммного автомата по граф – схеме алгоритма, приведенный на рисунке 2 .1, осуществлён в два этапа:

1. 
   получение отмеченной ГСА;
   
2. 
   построение графа автомата в виде списковых структур (таблицы переходов).
   

2.1 Кодированная ГСА
Таблица 2.1 – Кодирование логических выражений

	Выражение	Код выражения
w=0	x1	1
j=0	x2	2
АУ завершило работу?	x3	3
ПА = 01	x4	4
П завершила работу?	x5	5

Таблица 2.2 – Кодирование управляющих сигналов

	Сигнал	Код сигнала
Р1АУ:=ИР Р2АУ:=РАРК РКОАУ:=Сл	y1	01
РАРК:=РВАУ	y2	02
РАП:=РАРК	y3	03
РКОП:=Вб ИЗ->П	y4	04
РАРК:=(РВП)а ПА:=(РВП)па	y5	05
СК:=СК+1	y6	06
СК:=РАРК	y7	07
РАП:=СК	y8	10
РК:=РВП	y9	11

На рисунке 2.2 представлена полученная кодированная граф-схема алгоритма.

---

Рисунок 2.2 - Кодированная ГСА

2.2 Отмеченная ГСА

На этапе получения отмеченной ГСА входы вершин отмечены символами а₁, а₂, … , а_H по следующим правилам:

1. 
   символом а₁ обозначен вход вершины, следующий за начальной, а также вход конечной вершины;
   
2. 
   символами а₂, … , а_H обозначаются входы всех вершин, следующих за операторными;
   
3. 
   если вход вершины обозначен, то только одним символом;
   
4. 
   входы различных вершин, за исключением конечного, обозначаются различными символами.
   

Таким образом, отмеченная ГСА представлена на рисунке 2. 3.


Рисунок 2.3 – Отмеченная ГСА

---

2.3 Структурный синтез автомата

Кодирование состояний автомата приведено в таблице 2.3.

Таблица 2.3 – Кодирование состояний

	00	01	10	11
0	a1	a2	a3	a4
1	a5	a6

Из таблицы переходов следует, что в автомате количество состояний М=6, таким образом число элементов памяти составляет: m=] log₂M [=] log₂6 [=3.

Для синтеза использованы D триггеры.

С использованием отмеченной ГСА построена обратная структурная таблица, представленная в таблице 2.4, в которой сначала записываются все переходы в первое состояние, затем во второе и т.д.

В первом столбце указываются все состояния а_m, из которых осуществляются переходы. Коды этих состояний К(a_m) после кодирования занесены во второй столбец. В третьем и четвёртом столбцах записаны состояния a_s, в которых произошли переходы, и их коды К(a_s). Пятый и шестой столбцы содержат входные X(а_т,a_s) и выходные сигналы Y(a_m,a_s), входящие в пути перехода. В седьмом столбце таблицы перечислены обязательные функции возбуждения Ψ(a_m,a_s), вырабатываемые на соответствующих переходах для D-триггера и в восьмом - номер пути перехода для удобства идентификации.

Таблица 2.4 – Обратная структурная таблица

am	K (am )	as	K (as )	Xam, as	Y (am , as )	Ψ(am, as)	Р
а6	101	а1	000		y9	-	1	Ф(а1)
а1	000	a2	001		y1	D1	2
а2	001	a2	001		-	D1	3	Ф(а2)
а2	001	a3	010		y2	D2	4	Ф(а3)
а4	011	a3	011		y5	D2	5
а1	011	a4	011		y3 y4	D1 D2	6
а3	010	a4	011		y3 y4	D1 D2	7	Ф(а4)
а4	011	a4	011		-	D1 D2	8
а1	000	a5	100		y6	D3	9
а1	000	a5	100		y7	D3	10	Ф(а5)
а3	010	a5	100		y7	D3	11
а5	100	a6	101	1	y3 y8	D1 D3	12	Ф(а6)
а6	101	a6	101		-	D1 D3	13

---

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



Рисунок 2.4 – Функционально-логическая схема автомата

---

3 Синтез автомата с программируемой логикой

3.1 Адресация микрокоманд с двумя принудительными адресами

Для того, чтобы реализовать цифровой автомат с программируемой логикой с двумя принудительными адресами, составлен набор микрокоманд. Структура каждой микрокоманды включает в себя: микрооперации, выполняемые за один такт, код проверяемого логического условия и два адреса следующих микрокоманд. Адрес следующей микрокоманды определен в зависимости от кода логического условия КЛУ и значения соответствующего логического условия х_i, либо полем A1, либо полем А2.

Кодировка микропрограммы выполнена в восьмеричной системе счисления. Набор микрокоманд представлен в таблице 3.1.

Длина микрокоманды составила N=33 бит (11 символов × 3бита). Объём занимаемой ёмкости постоянной памяти при данном способе адресации микрокоманд составил Е= 495 бит (15 микрокоманд × 33 бит).

Пример формирования микропрограммы с двумя принудительными адресами представлен на рисунке 3.1.


Рисунок 3.1 – Граф структура микропрограммы с двумя принудительными адресами

Таблица 3.1 – Набор микрокоманд

AT	Y1	Y2	КЛУ	A1	A2
100	00	00	1	101	102
101	00	00	2	103	104
102	06	00	0	113	000
103	01	00	3	105	106
104	00	00	4	107	110
105	00	00	3	105	106
106	02	00	4	107	110
107	03	04	5	111	112
110	07	00	0	113	000
111	00	00	5	111	112
112	05	00	4	107	110
113	03	10	5	114	115
114	00	00	5	114	115
115	11	00	0	116	000
116	77	00	0	000	000	stop

---