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

Построение графа автомата

На основе отмеченной ГСА построен граф автомата Мура (рис.4). Он имеет 12 вершин, соответствующих состояниям автомата b0,b1,...,b11, каждое из которых определяет наборы выходных сигналов у1,..,у7 управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.

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

В таблице 12 представлена прямая структурная таблица переходов и выходов автомата Мура. Так как каждому состоянию автомата Мура соответствует свой набор выходных сигналов, то столбец выходных сигналов в таблице помещен следом за столбцом исходных состояний автомата. Проанализируем синтез автомата Мура на D-триггерах.

При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремиться использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 12 состояний (b₀, b₁,..., b₁₁) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце b_sтаблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть переходы, а во второй - состояния, из которых осуществляются эти переходы(табл. 13).

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения D-триггеров
b0	-	1010	b0 b1	1010 1100	~X1 X1	D1D3 D2D3
b1	y0y2y4	1100	b2 b10 b11	0101 0001 0010	X6 ~X6~X7 ~X6X7	D0D2 D0 D1
b2	y3y5	0101	b3 b4	1000 0011	~X1 X1	D3 D0D1
b3	-	1000	b3 b4	1000 0011	~X1 X1	D3 D0D1
b4	y2	0011	b5 b6 b7 b8 b9	0110 0111 1001 0100 0000	~X6 X6~X4 X6X4X2 X6X4~X2X3 X6X4~X2~X3	D1D2 D0D1D2 D0D3 D2 -
b5	y4	0110	b10 b11	0001 0010	~X7 X7	D0 D1
b6	y4	0111	b7 b8 b9	1001 0100 0000	X2 ~X2X3 ~X2~X3	D0D3 D2 -
b7	y3,y5	1001	b8 b9	0100 0000	X3 ~X3	D2 -
b8	y5	0100	b9	0000	1	-
b9	y1	0000	b8 b9 b10 b11	0100 0000 0001 0010	~X5X3 ~X5~X3 X5~X7 X5X7	D2 - D0 D1
b10	-	0001	b10 b11	0001 0010	~X7 X7	D0 D1
b11	y11	0010	b0	1010	1	D1D3

Таблица 13.

bs	b0	b1	b2	b3	b4		b5	b6	b7
{bm}	b0b11	b0	b1	b2b3	b2b3		b4	b4	b4b6
bs	b8	b9	b10	b11
{bm}	b4b6b7b9	b4b6b7b8b9	b1b5b9b10	b1b5b9b10

 

Коды состояний автомата определим по выше описанному методу кодирования состояний при использовании D-триггеров.

 

Таблица 14.

b	b0	b1	b2	b3	b4	b5	b6
K(b)	1010	1100	0101	1000	0011	0110	0111
b	b7	b8	b9	b10	b11
K(b)	1001	0100	0000	0001	0010

 

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

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

= b1x6 V b1~x6~x7 V b2x1 V b3x1 V b4x6~x4 V b4x6x4x2 V b5~x7 V b6x2 V b9x5~x7 V b10~x7= b0~x1 V b1~x6x7 V b2x1 V b3x1 V b4~x6 V b4x6~x4 V b5x7 V b9x5x7 V b10x7 V b11= b0x1 V b1x6 V b4~x6 V b4x6~x4 V b4x6x4~x2x3 V b6~x2x3 V b7x3 V b9~x5x3= b0~x1 V b0x1 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11

 

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

y0 = b1 = b9

y2 = b1 V b4

y3 = b7

y4 = b1 V b5 V b6

y5 = b7 V b8

y11 = b11

 

Выделив общие части получаем:

 

c = b1x6 (2)= b1~x6 (2)= b2x1 (2)= b4x6~x4 (3)= b3x1 (2)= b4~x6 (2)= e V g V f (3)= k V l (2)= b4x6x4x2 (4)= b6x2 (2)= b9x5 (2)= b5 V m V b10 V d (4)= b1x6 V b1~x6~x7 V b2x1 V b3x1 V b4x6~x4 V b4x6x4x2 V b5~x7 V b6x2 V b9x5~x7 V b10~x7 =

= c V i V j V ~x7(b5 V m V b10 V d) = c V i V j V ~x7n (6)= b0~x1 V b1~x6x7 V b2x1 V b3x1 V b4~x6 V b4x6~x4 V b5x7 V b9x5x7 V b10x7 V b11 = b0~x1 V I V h V x7(b5 V m V b10 V d) V b11 = b0~x1 V I V h V x7n (8)= b0x1 V b1x6 V b4~x6 V b4x6~x4 V b4x6x4~x2x3 V b6~x2x3 V b7x3 V b9~x5x3 = b0x1 V c V h V f V ~x2x3 (b4x6x4 V b6) V x3(b7 V b9~x5) (22)= b0 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11 = b0 V ~x1(b2 V b3) V j (6)= b1 (0)= b8 (0)

y2 = b1 V b4 (2)

y3 = b2 V b6 (2)

y4 = b1 V b5 (2)

y5 = b2 V b6 V b7 (3)

y6 = b8 (0)

Инверсии: (~x1~x2~x4~x5~x6~x7) (6)

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

 

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

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

Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Для этого сначала выпишем матрицу М - матрицу всех возможных переходов автомата. Состояниям автомата b0 и b1 присвоим коды: К(b0)=0000, К(b1)=0001. Далее из матрицы М составим подматрицу М2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C0 и C1 коды с кодовым расстоянием "1" от кодов В2. Для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами В_i и D_i. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми, выбираем любой код и кодируем это состояние.

Таблица 15.

b	b0	b1	b2	b3	b4	b5	b6
K(b)	0000	0001	0011	0010	0110	0111	0100
b	b7	b8	b9	b10	b11
K(b)	0101	1100	1110	1111	1101

 

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

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

 

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения RS-триггеров
b0	-	0000	b0 b1	0000 0001	~X1 X1	- S0
b1	y0y2y4	0001	b2 b10 b11	0011 1111 1101	X6 ~X6~X7 ~X6X7	S1 S1S2S3 S2S3
b2	y3y5	0011	b3 b4	0010 0110	~X1 X1	R0 R0S2
b3	-	0010	b3 b4	0010 0110	~X1 X1	- S2
b4	y2	0110	b5 b6 b7 b8 b9	0111 0100 0101 1100 1110	~X6 X6~X4 X6X4X2 X6X4~X2X3 X6X4~X2~X3	S0 R1 S0R1 R1S3 S3
b5	y4	0111	b10 b11	1111 1101	~X7 X7	S3 R1S3
b6	y4	0100	b7 b8 b9	0101 1100 1110	X2 ~X2X3 ~X2~X3	S0 S3 S1S3
b7	y3,y5	0101	b8 b9	1100 1110	X3 ~X3	R0S3 R0S1S3
b8	y5	1100	b9	1110	1	-
b9	y1	1110	b8 b9 b10 b11	1100 1110 1111 1101	~X5X3 ~X5~X3 X5~X7 X5X7	R1 - S0 S0R1
b10	-	1111	b10 b11	1111 1101	~X7 X7	- R1
b11	y11	1101	b0	0000	1	R0R2R3

 

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

 

R0 = b2~x1 V b2x1 V b7x3 V b7~x3 V b11= b4x6~x4 V b4x6x4x2 V b4x6x4~x2x3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7= b11= b11= b0x1 V b4~x6 V b4x6x4x2 V b6x2 V b9x5~x7 V b9x5x7= b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3= b1~x6~x7 V b1~x6x7 V b2x1 V b3x1= b1~x6~x7 V b1~x6x7 V b4x6x4~x2x3 V b4x6x4~x2~x3 V b5~x7 V b5x7 V b6~x2x3 V b6~x2~x3 V b7x3 V b7~x3= b1 = b8

y2 = b1 V b4

y3 = b2 V b6

y4 = b1 V b5

y5 = b2 V b6 V b7

y6 = b8

Упростив и выделив общие части получаем:

 

o = b4x6x4x2 (4)= b4x6x4~x2 (4)= b1~x6 (2)= b2 V b7 V b11 (3)= b4x6~x4 V o V px3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7 (21)= b11 (0)= b11 (0)= b0x1 V b4~x6 V o V b6x2 V b9x5 (13)= b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3 (14)= q V b2x1 V b3x1 (7)= q V p V b5 V b6~x2 V b7 (7)= b1 (0)= b8 (0)

y2 = b1 V b4 (2)

y3 = b2 V b6 (2)

y4 = b1 V b5 (2)

y5 = b2 V b6 V b7 (3)

y6 = b8 (0)

Инверсии: (~x2~x3~x4~x5~x6) (5)

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

 

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