Синтез микропрограммного автомата Мура по граф-схеме алгоритма

Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воздействием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.

Математической моделью является абстрактный автомат, определенный 6-ю компонентами: S=(A,Z,W,d,l,а1)

Z – множество входящих состояний

A - множество внутренних состояний

W - множество выходящих состояний

d - функция перехода (определяет следующее состояние автомата, в зависимости от предыдущего)

l - функция выхода (определяет выходной сигнал в зав-ти от состояния автомата и поступившего входного сигнала)

а1 – исходное состояние автомата.

Уравнения автомата Мура:

a(t+1)=d(a(t), z(t));

w(t) = l(a(t)), t = 0,1,2,...

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

Способы задания ЦА:

· Уравнение в канонической форме

· Таблица переходов

· Граф

Для синтеза автомата Мура необходимо выполнить разметку граф-схемы алгоритма. Она выполняется по следующим правилам:

1). Символом «а0» обозначается начальная и конечная вершина.

2). Символами «а1», «а2», …«аN» обозначаются остальные вершины.

3). Ни одна из вершин не должна обладать одинаковым состоянием (символом) (кроме «а0»)

4). Ни одна из вершин не должна иметь 2 и больше состояний.

СхемаструктурногоавтоматаМура:

 

 

Задание: Синтезировать автомат Мура по граф-схеме алгоритма суммирования:

В алгоритме прямоугольниками и буквами “Y” отмечены процессы (например: суммирование, перемещение, вычитание и т.д.) Ромбами и буквами “X” обозначены условные переходы. Как правило, переход вниз или вправо обозначает переход при 1, влево – при 0.

Итак, первое, что необходимо сделать – разметить состояния автомата (а0, а1…). Размечаются толькопроцессы. Условия не размечаются. Разметка выполняется по правилам выше.

После того как граф-схема алгоритма (ГСА) размечена, необходимо вычислить количество разрядов, необходимое для кодирования всех состояний автомата. В нашем случае у нас 7 состояний. По формуле n=log₂(N_a), где N_a– количество состояний. Причем, nокругляется в большую сторону. В нашем случае n=3. Следовательно для кодирования будут использованы 3 сигнала: Р1, Р2,

Присвоим каждому состоянию свой код:

состояние	Р1	Р2	Р3
а0
а1
а2
а3
а4
а5
а6

Как видно, у нас не задействован наборa7 «111», поэтому этот код следует минимизировать:

Составим карту Карно.

p1\p2p3
	a0	a2	a6	a4
	a1	a3	a7	a5

Не знаю, как называется следующий процесс, но можете его называть «модным склеиванием». Суть его такова: а7 (111) склеивается с а6 (110). У них одна последняя цифра отличается. Поэтому она заменяется на «х» и тогда получается а6 (11х). Далее а7(111) склеивается с а3(011), но уже по первой цифре и получается а3(х11). Затем а7(111) с а5 (101) и получается а5 (1х1). Нетрудно заметить, что склеиваются только соседние состояния с а7.

ВАЖНО: правильно рисуйте карту Карно. Сверху идут цифры не совсем в порядке.

Следующее действие: Составляем таблицу переходов Мура. (примечание, если х1 берется со знаком “не”, то будет писаться «х1’»)

 

Переход	Исходное состояние	Код ИС	След. Сост.	Код С.С.	Вх. Набор	Вых. набор	Сигнал переключения
D-триггер	JK-триггер
	а0		а1		Z	-	D3	J3
	a1		a2		x1	у1, у2	D2	J2,K3
			а3	х11	х1’x2’	D2,D3	J2
			а4		х1’x2	D1	J1,K3
	a2		a3	x11	x2’	y3	D2,D3	J3
			a4		x2	D1	J1,K2
	a3	x11	a5	1x1	x3’	y4	D1,D3	J1
			a6	11x	x3x1	D1,D2	J1
			a0		x3x1’	-	K2,K3
	a4		a5	1x1	x3’	y5	D1,D3	J3
			a6	11x	x3x1	D1,D2	J2
			a0		x3’x1’	-	K1
	a5	1x1	a0		-	y6	-	K1,K2,K3
	a6	11x	a0		-	y3	-	K1,K2,K3

 

Теперь самое главное. Для изменения состояний можно выбирать разные типы триггеров. В нашем случае это DиJK триггеры. Их количество берется из той же формулы, что и количество сигналов для кодирования. Для реализации нашей ГСА следует взять 3 D-триггера: D1, D2, D3. Заполняем таблицу:

Правило: 0->1 =>D

Переход номер 1: 000 -> 00 1 =>D3

Переход номер 2: 001 -> 0 1 0 =>D2

Переход номер 3: 001 ->x 11 =>D2,D3

(ловите логику)

Для реализации нашей ГСА с помощью JK-триггеров следует взять 3 JK-триггера: JK1, JK2, JK3.

Заполняем таблицу:

Правило: 0->1 =>J

1->0 => K

Переход номер 1: 000 -> 00 1 =>J3

Переход номер 2: 001 -> 0 1 0 =>J2,K3

Переход номер 3: 001 ->x 11 =>J2

(ловите логику)

Теперь надо составить уравнения работы этого автомата (включают уравнения состояний и уравнения работы триггеров). Рассмотрим работу этого автомата на D-триггерах

y1 = y2 = a1

y3 = a2+a6

y4 = a3

y5 = a4

y6 = a5

D1 = a1*х1’*x2+ a2*x2 + a3*x3’ + a3*x1*x3 + a4*x3’ + a4*x3*x1

D2 = a1*x1 + a1*x1’*x2’ + a2*x2’ + a3*x1*x3 + a4*x3*x1

D3 = a0*z + a1*x1’*x2’ + a2*x2’ + a3*x3’ + a4*x3’

Эти уравнения определяют работу автомата. Найдём в них похожие элементы. После этого можно приступать к построению.