Пример синтеза управляющего автомата для заданного алгоритма

По заданной содержательной схеме алгоритма в микрооперациях разработать функциональную схему управляющего автомата Мура (Мили) (рисунок 9), в качестве элементов памяти использовать D-триггеры, комбинационную схему реализовать на логических элементах. Дать оценку конструктивной сложности ЦА.

Рисунок 9 – Схема алгоритма в микрооперациях

1) Заменим наборы микроопераций О1, О2, О3, О4 на коды микрокоманд Y1, Y2, Y3, Y4. В результате получим кодированную ГСА в микрокомандах.

2) Построим отмеченную граф-схему алгоритма (ГСА) управляющего автомата Мура (Мили)

В соответствии с требованиями предъявляемыми к разметке состояний цифрового автомата Мура (Мили) получаем отмеченную ГСА цифрового автомата (рисунок 10, а), б)).

а) б)

Рисунок 10 – Отмеченные граф-схемы а) для автомата Мура, б) для автомата Мили

3) Построение графа функционирования автомата

Согласно отмеченной граф-схеме алгоритма управляющего автомата Мура (Мили) строим граф функционирования автомата (рисунок 11, а), б)).

а)

б)

Рисунок 11 – Графы функционирования автоматов: Мура а), Мили б)

4) Кодирование состояний устройства

Число разрядов кода состояния соответствует числу элементов памяти и определяется по формуле: k = ù log₂ S é, где

k – число разрядов (число элементов памяти)

S – число внутренних состояний;

ù é - округление в большую сторону.

В нашем случае для автомата Мура число состояний S = 6. Количество разрядов кода состояния (число элементов памяти): K = ]log₂S[ = ]log₂6[ = 3.

Для автомата Мили число состояний S = 5. Количество разрядов кода состояния (число элементов памяти): k = ]log₂S[ = ]log₂5[ = 3.

Таблицы кодировки состояний для автомата Мура и автомата Мили приведены на рисунке 12, а) и б) соответственно.

Состояние	Код состояния
S0
S1
S2
S3
S4
S5

Состояние	Код состояния
S0
S1
S2
S3
S4

а) б)

Рисунок 12 - Таблицы кодировки состояний для автомата Мура а) и автомата Мили б)

5) Формирование функций перехода, возбуждения и выходов устройства

По отмеченной ГСА или графу функционирования автомата, таблицы кодировки состояний автомата и таблицы переходов триггеров строим таблицы (или таблицу) функций перехода, возбуждения и выходов устройства.

Таблица 2 – Таблица переходов D-триггера

Q(t)®Q(t+1)	D
0 → 0
0 → 1
1 → 0
1 → 1

Таблица 3 – Таблица функций выходов для автомата Мура

Состояние	Код состояния	Выходные функции
Q1	Q2	Q3	Y1	Y2	Y3	Y4
S0
S1
S2
S3
S4
S5

Таблица 4 – Таблица функций перехода и возбуждения для автомата Мура

Исходное состояние	Условия перехода	Последующее состояние	Функции возбуждения
метка	код	метка	код
Q1	Q2	Q3	Q1	Q2	Q3	D1	D2	D3
S0				–	S1
S1				–	S2
S2					S3
	S5
S3					S4
	S5
S4				–	S5
S5				–	S­0

Таблица 5 - Таблица функций выходов,перехода и возбуждения для автомата Мили

Исходное состояние

Условия перехода

Последующее состояние

Выходные функции

Функции возбуждения

метка

код

метка

код

Q1

Q2

Q3

Q1

Q2

Q3

D1

D2

D3

S0

–

S1

Y1,Y2,Y3

S1

–

S2

Y2,Y3

S2

S3

Y1,Y2

S4

–

S3

S4

Y1,Y2,Y3

–

S4

–

S0

Y2,Y3,Y4

6) Минимизация функций возбуждения элементов памяти и функций выходов

Из таблицы функций перехода, возбуждения и выходов автомата Мура (Мили) получаем систему логических уравнений для цифрового автомата Мура (Мили).

Система логических уравнений для цифрового автомата Мура:

Система логических уравнений для цифрового автомата Мили:

Из системы логических уравнений для цифрового автомата Мура получаем полное множество конъюнкций для данного автомата:

Из системы логических уравнений для цифрового автомата Мили получаем полное множество конъюнкций для данного автомата:

Из полного множества конъюнкций получаем таблицу покрытия конъюнкциями системы логических уравнений.

Таблица 6 - Таблица покрытия конъюнкциями для цифрового автомата Мура

K1

K2

K3

K4

K5

K6

K7

K8

K9

K10

K11

K12

D1

+

+

+

D2

+

+

D3

+

+

+

Y1

+

+

Y2

+

+

+

Y3

+

+

+

Y4

+

Таблица 7 - Таблица покрытия конъюнкциями для цифрового автомата Мили

	K1	K2	K3	K4	K5	K6	K7	K8	K9
D1	+	+
D2			+	+
D3				+	+
Y1				+	+	+
Y2			+	+		+	+
Y3						+		+	+
Y4									+

7) Построение функциональной схемы управляющего автомата Мура (Мили)

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

Рисунок 13 - Функциональная схема управляющего автомата Мура

Рисунок 14 - Функциональная схема управляющего автомата Мили

8) Оценка конструктивной сложности управляющего автомата Мура (Мили).

- Определение конструктивной сложности автомата Мура методом Квайна - число входов логических элементов: 59.

- Число ярусов сигнала на самом длинном пути от входа к выходу: 4.

- Количество элементов необходимых для построения функциональной схемы:

Таблица 8 – Оборудование для реализации автомата Мура

Автомат	Логические элементы	на 2 входа	на 3 входа	на 4 входа	D -триггеров	Всего элементов
Мура	И
ИЛИ
И-НЕ

- Определение конструктивной сложности автомата Мили методом Квайна - число входов логических элементов: 51.

- Число ярусов сигнала на самом длинном пути от входа к выходу: 4.

- Количество логических элементов необходимых для построения функциональной схемы:

Таблица 9 – Оборудование для реализации автомата Мили

Автомат	Логические элементы	на 2 входа	на 3 входа	на 4 входа	D -триггеров	Всего элементов
Мили	И
ИЛИ
И-НЕ

Дата добавления: 2015-05-09