Тема 7.2. Структурный синтез мпа на жесткой логике. Синтез мпа автоматов

Мили на жесткой логике. Вопросы оптимизации МПА

0. Разметка состояний авто­мата Мили по гса

В отличие от автомата Мура состояния автомата Мили не соответствуют операторным вершинам ГСА, а отмечаются на дугах ГСА перед вершинами, следующими за операторными. Исключение составляет начальное (оно же конечное) состояние автомата. Его удобно обозначать символом а₀ или а₁. Символом а₀ или а₁ отмечают вход вершины, следующей за начальной, и вход конечной вершины ГСА. Входы всех остальных вершин, следующих за операторными, также отмечаются символами: а₁, а₂, … Используем для примера ГСА УА (см. рис. 3.2) для синтеза автомата Мили. Обозначим начальное состояние как а₁, а остальные – а₂, а₃, а₄.

В случае, когда в вершину, следующую за операторной, входит более чем одна дуга, состояние необходимо отметить на дуге так, чтобы для всех входящих дуг соблюдалось правило разметки состояний. На ГСА (рис. 3.19) это состояния а₂ и а₃. Состояние а₂ необходимо отметить ниже входящей слева стрелки, а состояние а₃ – выше входящей справа стрелки. В первом случае в а₂ сошлись пути из двух операторных вершин, а во втором – путь из а₂ не приводит в состояние а₃ (этот переход был бы «пустым», без прохода через операторную вершину), а приводит в состояние а₄ (после операторной вершины).

3.1.2.2. Построение графа переходов автомата Мили по гса

Вершины графа соответствуют со­стояниям автомата, дуги – переходам из со­стояния a_m в состояние a_s. У выхода дуги из вершины графа a_m записываются логические условия, определяющие переход из состоя­ния a_m в состояние a_s , а у входа дуги в со­стояние a_s – микрокоманды, вырабатывае­мые автоматом при переходе из состояния a_m в состояние a_s (рис. 3.20).

Рис. 3.19

Рис. 3.20

3.1.2.3. Построение прямой таблицы переходов автомата Мили

Прямая таблица переходов (табл. 3.8) строится по графу переходов (см. рис. 3.20).

Количество строк в таблице равно количеству переходов в графе переходов. В столбце а_m записываются состояния, из которых начинается переход, в столбце a_{s –} состояния, в которые перешел автомат из состояния а_m.

Таблица 3.8

№ п/п	am	as	Xamas	Yamas
1 2	a 1	a 1 a 2	 x 3 x 3	- y 1 y 2
3 4	a 2	a 3 a 4	x 1  x 1	y 3 y 4 y 5
5	a 3	a 4	1	y 4 y 5
6 7	a 4	a 1 a 2	x 2  x 2	y 7 y 6

В столбце Y a_ma_s записываются Y_{i –} микрокоманды, вырабатываемые автоматом при переходе из состояния a_m в состояние a_s. В столбце Xa_ma_s записываются логические условия (их конъюнкция), обеспечивающие переход из состояния а_m в состояние a_s.

Прямая таблица позволяет проверить полноту переходов, показанных на графе переходов: дизъюнкция всех Xa_ma_s из состояния a_m должна быть равна «1» (Xa_ma_s=1). В нашем примере дизъюнкция всех Xa₁a_s равна Xa₁a_s = Xa₁a₁  Xa₁a₂ =  x ₃  x ₃ = 1. Аналогично Xa₂a_s = Xa₂a₃  Xa₂a₄ = x ₁  x ₁ = 1, Xa₃a_s = Xa₃a₄ = 1,

Xa₄a_s = Xa₄a₁  Xa₄a₂ = x₂  x₂ = 1.