Синтез МПА в соответствии с моделью Мили

Построение графа автомата и структурной таблицы переходов и выходов

Граф автомата Мили имеет восемь вершин, соответствующих состояниям автомата a0,...,a8. Дуги его отмечены входными сигналами, действующими на каждом переходе (числитель), и набором выходных сигналов, вырабатываемых УА на данном переходе (знаменатель).

Кодирование на D-триггерах

При использовании D-триггеров в качестве ЭП для получения смены состояний на каждом переходе (a_m -> a_s) сигналы возбуждения должны быть поданы на те триггеры, которые в коде состояния перехода a_s содержат "1". Отсюда основное требование к выбору кодов состояний: чем больше переходов в какое-либо состояние, тем меньше "1" должен содержать код этого состояния. Для кодирования 9 состояний (a₀ ,…, a₈) необходимо 4 элемента памяти.

 

Таблица 6.

as	a0	a1	a2	a3	a4	a5	a6	a7	а8
{am}	a8,a0	a0	a2,a1	a2	a3	a4	a7	a6	a1,a3,a7,a8

 

Наибольшее количество переходов в состояние a₈ - закодируем его кодом К(a₈) = 0000. Для остальных состояний первой строки табл.6 назначим коды с одной "1" и более: K(a₀) = 0001, K(a₁) = 0010, К(a₂) = 0011, К(a₃) = 0100, K(a₄) = 0101, K(a₅) = 0110, K(a₆) = 1000, K(a₇) = 1001. Таким образом, таблица кодирования для D-триггеров такова:

Таблица 7.

as	a0	a1	a2	a3	a4	a5	a6	a7	a8
K{as}	0001	0010	0011	0100	0101	0110	1000	1001	0000

 

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

 

Таблица 8. Прямая структурная таблица переходов и выходов.

Исходное состояние am	Код am	Состояние перехода as	Код as	Входной сигнал X(am, as)	Выходные сигналы Y(am,as)	Функция возбуждения D-триггеров
a0	0001	a0 a1	0001 0010	~X1 X1	- y0y2y4	D0 D1
a1	0010	a2 a8	0011 0000	X6 ~X6	y3y5 -	D0D1 -
a2	0011	a2 a3	0011 0100	~X1 X1	- y2	D0D1 D2
a3	0100	a4 a4 a8	0101 0101 0000	X6~X4 X6X4 ~X6	y4 - y4	D0D2 D0D2 -
a4	0101	a5 a5	0110 0110	~X2 X2	- y3y5	D1D2 D1D2
a5	0110	a6 a6	1000 1000	X3 ~X3	y5 -	D3 D3
a6	1000	a7	1001	1	y1	D0D3
a7	1001	a6 a6 a8	1000 1000 0000	~X5~X3 ~X5X3 X5	- y5 -	D3 D3 -
а8	0000	a0 a8	0001 0000	X7 ~X7	y11 -	D0 -

Получение логических выражений для функции возбуждения D-триггеров

Логические выражения для каждой функции возбуждения D-триггера получают по таблице как конъюнкции соответствующих исходных состояний Am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.

 

D0 = a0~x1 V a1x6 V a2~x1 V a3x6~x4 V a3x6x4 V a6 V a8x7= a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2= a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2= a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3

 

Аналогично составляются логические выражения для функций выходов.

 

y0 = a0x1  = a6 = a0x1 V a2x1  = a1x6 V a4x2 = a0x1 V a3x6~x4 V a3~x6 = a1x6 V a4x2 V a5x3 V a7~x5x3

y11 = a8x7

 

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

 

c = a0x1 (2) l = a5x3 (2)= a0 V a2 (2) m = a7~x5x3 (3)= a1x6 (2) n = a3~x6 (2)= a8x7 (2)= a3x6 (2)= a7~x5 (2)= a2x1 (2)= a4x2 (2)= a2~x1 (2)= a0~x1 V a1x6 V a2~x1 V a3x6~x4 V a3x6x4 V a6 V a8x7 = ~x1d V e V g V a6 V f (7)= a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2 = c V e V k V a4 (4)= a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2 = i V g V a4 (3)= a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3 = a5 V a6 V h (3) = c (0) = a6 (0) = a0x1 V a2x1 = x1d (2) = e V j (2) = c V g~x4 V n (5) = e V j V l V m (4)= f (0)

Инверсия: (~x1~x5~x6) (3)

Полная цена по Квайну: 58(КС)+8(ЭП)+4(DC)+0(НУ)=70

 

Цена комбинационной схемы по Квайну для автомата Мили, с использованием в качестве элементов памяти D-триггеров, равна С = 70, причем в схеме предполагается использовать 4-входовой дешифратор.

Кодирование на RS- триггерах

Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Но при использовании RS-триггеров придется перекодировать состояния автомата. Кодирование осуществим способом минимизирующим число переключений элементов памяти.

Для этого сначала выпишем матрицу M - матрицу всех возможных переходов автомата. Состояниям автомата a0 и a1 присвоим коды: К(a0)=0000, К(a1)=0001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C1 коды с кодовым расстоянием "1" от кодов В2. Закодировав состояние a2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния a3 аналогично a2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами В_i и D_i. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми, выбираем любой код и кодируем это состояние.

 

1). =a₂

 B={1}  С₁={0011,0101,1001} W₀₀₁₁=1

D₂={0011,0101,1001} W₀₁₀₁=1₁₀₀₁=1

Выбираем любой:

K(a₂)=0011

2). =a₃

 B={2}₂={0010,0111,1011} W₀₀₁₀=1₃={0010,0111,1011} W₀₁₁₁=1₁₀₁₁=1

Выбираем любой:

K(a₃)=0010

). =a₄

 B={3}₃={0110,1010}      W₀₁₁₀=1₄={0110,1010} W₁₀₁₀=1

Выбираем любой:

K(a₄)=0110

). =a₅

B={4}₄={1110,0111,0100}

W₁₁₁₀=1

D₅={1110,0100,0111}

W₀₁₀₀=1

W₀₁₁₁=1

 Выбираем любой:

K(a₅)=0100

5). =a₆

B={5}₅={0101,1100}₀₁₀₁=1

D₆={0101,1100}

W₁₁₀₀=1

Выбираем любой: K(a₆)=1100

6). =a₇B={6}₆={1101,1110,1000}₁₁₀₁=2 ₇={1101,1110,1000}₁₁₁₀=2₁₀₀₀=2

Выбираем:     K(a₇)=1000

). =a₈

B={0,1,3,7}    C₀={Ø} ₁₀₀₁=7

C₁={1001} W₁₀₁₀=7₃={1010} W₁₁₀₀=9₇={1001,1100,1010}

D₈={1001,1010,1100}

Выбираем:     K(a₇)=1001

Кодирования для RS-триггеров изображены в таблице 8.

 

Таблица 8.

as	a0	a1	a2	a3	a4	a5	a6	a7	a8
K{as}	0000	0001	0011	0010	0110	0100	1100	1000	1001

Получение логических выражений для функций возбуждения RS-триггеров

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

 

Таблица 9. Прямая структурная таблица переходов и выходов.

Исходное состояние	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения RS-триггеров
a0	0000	a0 a1	0000 0001	~X1 X1	- y0y2y4	- S0
a1	0001	a2 a8	0011 1001	X6 ~X6	y3y5 -	S1 S3
a2	0011	a2 a3	0011 0010	~X1 X1	- y2	- R0
a3	0010	a4 a4 a8	0110 0110 1001	X6~X4 X6X4 ~X6	y4 - y4	S2 S2 S0R1S3
a4	0110	a5 a5	0100 0100	~X2 X2	- y3y5	R1 R1
a5	0100	a6 a6	1100 1100	X3 ~X3	y5 -	S3 S3
a6	1100	a7	1000	1	y1	R2
a7	1000	a6 a6 a8	1100 1100 1001	~X5~X3 ~X5X3 X5	- y5 -	S2 S2 S0
a8	1001	a0 a8	0000 1001	X7 ~X7	y11 -	R0R3 -

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

 

S0 = a0x1 V a3~x6 V a7x5= a1x6= a3x6~x4 V a3x6x4 V a7~x5~x3 V a7~x5x3= a1~x6 V a3~x6 V a5x3 V a5~x3= a2x1 V a8x7= a3~x6 V a4~x2 V a4x2

R2 = a6= a8x7

 

После упрощения и выделения общих частей, получим:

 

l = a2x1 (2) r = a3x6 (2) x = a7~x5 (2)= a0x1 (2) s = a7x5 (2)= a3~x6 (2) t = a1~x6 (2)= a1x6 (2) u = a3x6~x4 (3)= a8x7 (2) v = a5x3 (3)= a4x2 (2) w = a7~x5x3 (3)= m V n V s (3)= o (0)= r V x (2)= t V n V a5 (3)= l V p (2)= n V a4 (2)= a6 (0)= p (0) = m (0) = a6 (0) = m V l (2) = o V q (2) = m V u V n (3) = o V q V v V w (4)= p (0)

Инверсии: (~x6~x4~x5) (3)

Полная цена по Квайну: С = 55(КC)+12(ЭП)+4(ДЦ)+4(НУ) = 75

 

С использованием в качестве элементов памяти RS-триггеров, цена комбинационной схемы по Квайну для автомата Мили равна C= 75, причем в схеме предполагается использовать 4-входовой дешифратор.

Кодирование на счетчике

Для кодирования состояний автомата на счётчике необходимо, чтобы разность кодов между соседними состояниями составляла единицу. Данная кодировка представлена в таблице 10.

 

Таблица 10.

As	a0	a1	a2	a3	a4	a5	a6	a7	а8
K{as}	0000	0001	0010	0011	0100	0101	0110	0111	1000

 

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

Таблица 11. Прямая структурная таблица переходов и выходов автомата Мили.

Исходное состояние	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения счётчиков
a0	0000	a0 a1	0000 0001	~X1 X1	- y0y2y4	- +1
a1	0001	a2 a8	0010 1000	X6 ~X6	y3y5 -	+1 D3EWR
a2	0010	a2 a3	0010 0010	~X1 X1	- y2	- -
a3	0011	a4 a4 a8	0100 0100 1000	X6~X4 X6X4 ~X6	y4 - y4	+1 +1 D3EWR
a4	0100	a5 a5	0101 0101	~X2 X2	- y3y5	+1 +1
a5	0101	a6 a6	0110 0110	X3 ~X3	y5 -	+1 +1
a6	0110	a7	0111	1	y1	+1
a7	0111	a6 a6 a8	0110 0110 1000	~X5~X3 ~X5X3 X5	- y5 -	-1 -1 +1
a8	1000	a0 a8	0000 1000	X7 ~X7	y11 -	R -

 

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

 

+1 = a0x1 V a1x6 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2 V a5x3 V a5~x3 V a6 V a7x5 - 1 = a7~x5~x3 V a7~x5x3= a8y11EWR = a1~x6 V a3~x6

После упрощения и выделения общих частей, получим:

 

1 = a4x2 (2) 7 = a8x7 (2) 13 = a5x3 (2)

= a0x1 (2) 8 = 6x3 (2) 14 = a7~x5 (2)

= a3x6 (2) 9 = a1~x6 (2) 15 = 9 V 4 (2)

= a3~x6 (2) 10 = a7x5 (2)

= a1x6 (2) 11 = a2x1 (2)

= a1 V a3 (2) 12 = 3~x4 (2)

+1 = 2 V 5 V 3 V a4 V a5 V a6 V 10 (7)

1 = 14 (0)= 7 (0)EWR = 15 (0) = 2 (0) = a6 (0) = 2 V 11 (2)  = 5 V 1 (2) = 2 V 12 V 4 (3) = 5 V 1 V 13 V 8 (4)= 7 (0)

Инверсии: (~x4~x6~x5) (3)

Полная цена по Квайну: С = 51(КС)+9(ЭП)+4(ДЦ)+0(НУ)=0.

 

Сравнивая относительно аппаратурных затрат варианты построения автомата Мили на RS, D-триггерах можно убедиться что цена логических выражений для функций возбуждения оказывается приблизительно равной: для D цена - 70, для RS цена - 75, а для счетчика - 64.