Синтез микропрограммного управляющего автомата (стр. 5 из 7)

e=a1 v a3 d=x1(a0 v a2) f=a0x1

h=x2e g=a1x2 v a4x4 p=a8x7

r=f v h q=a7x6 n=h v q

M = n v px8 v a9x9

E+1 = d v x2e v a4 v a5 v a6 v a7x6 v px8

D1 = n

D4 = q

D8 = h

y1 = r

y2 = d

y3 = r v a3x2x3

y4 = g v a5x5

y5 = a6

y6 = g

y7 = a8x7

y8 =a9x9

Цена комбинационной схемы по Квайну составляет С=57.

Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=10), а n наименьшее число ЭП (n=log₂ 16).

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

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

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

На основе отмеченной ГСА построен граф автомата Мура (рисунок 5).Граф автомата Мура имеет 11 вершин,соответствующих состояниямавтомата b₀,b₁,...,b₁₀, каждое из которых определяет наборы выходныхсигналов, управляющего автомата, а дуги графа отмеченывходными сигналами, действующими на данном переходе.

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

Из приведенного рисунка видно, что с увеличением количества состояний автомата наглядность графа теряется и больше удобств представляет табличный способ задания автомата.

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения D-триггеров
b0	-	0001	b0 b1	0001 0111	X1 X1	D4 D2D3D4
b1	y1,y2,y3	0111	b2 b12	1110 0011	X2 X2	D1D2D3 D3D4
b2	y4,y6	1110	b3 b4	1010 0110	X1 X1	D1D3 D2D3
b3	-	1010	b3 b4	1010 0110	X1 X1	D1D3 D2D3
b4	y2	0110	b5 b6 b7 b8 b12	1100 0101 0010 0000 0011	X2X3 X2X3X4 X2X3X4X5 X2X3X4X5 X2	D1D2 D2D4 D3 D3D4
b5	y3	1100	b6 b7 b8	0101 0010 0000	X4 X4X5 X4X5	D2D4 D3
b6	y4,y6	0101	b7 b8	0010 0000	X5 X5	D3
b7	y4	0010	b8	0000	1
b8	y5	0000	b0 b7 b8 b9 b10 b11	0001 0010 0000 1001 0100 1000	X6X7X8 X6X5 X6X5 X6X7 X6X7X8X9 X6X7X8X9	D4 D3 D1D4 D2 D1
b9	y7	1001	b0 b9 b10 b11	0001 1001 0100 1000	X7X8 X7 X7X8X9 X7X8X9	D4 D1D4 D2 D1
b10	-	0100	b10 b11	0100 1000	X9 X9	D2 D1
b11	y8	1000	b0	0001	1	D4
b12	y1,y3	0011	b10 b11	0100 1000	X9 X9	D2 D1

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

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

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

Таблица 16

bs	b0	b1	b2	b3	b4		b5	b6		B7
{bm}	b0b8b9b11	b0	b1	b2b3	b2b3		b4	b4b5		b4b5b6b8
bs	b8	b9	b10			b11			b12
{bm}	b4b5b6b7b8	b8b9	b8b9b10b12			b8b9b10b12			b1b4

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

Таблица 17

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

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

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

D1= b1x2 v b2x1 v b3x1 v b4x2 v b8x6x7 v b8x6x7x8x9 v b9x7 v b10x9 v b12x9

D2= b0x1 v b1x2 v b2x1 v b3x1 v b4x2(x3 v x3x4) v b5x4 v b8x6x7x8x9 v b9x7x8x9 v b10x9 v

v b12x9

D3= b0x1 v b1 v b2 v b3 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b8x6x4

D4= b0 v b1x2 v b4x2x3x4 v b4x2 v b5x4 v b8x6(x7x8 v x7) v b9(x7x8 v x7) v b11

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

y1= b1 v b12

y2= b1 v b4

y3= b1 v b5 v b12

y4= b2 v b6 v b7

y5= b8

y6= b2 v b6

y7= b9

y8=b11

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

d=b2 v b6

g=b0x1

h=b1x2

i=b4x2

j=x4x5

k=b4x2x3

m=b8x6

n=x7x8

r=b2 v b3

q=mvb9

D1= h v x1r v k v m(x7 v nx9) v b9x7 v b10x9 v b12x9

D2= g v h v x1r v i(x3 v x3x4) v b5x4 v nx9q v x9(b10 v b12)

D3= g v b1 v r v j(k v b5) v x5(b6 v b8x6)

D4= b0 v x2(b1 v b4) v x4(k v b5) v (x7x8 v x7)q v b11

y4= d v b7

y6= d

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

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

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

00 k₀=0000

01

12 k₁=0001

1 12

23 12 B2 ={0001}

24 M2= 23 C1={0011,0101,1001}

M= 3324 D2={0011,0101,1001}

34 W₀₀₁₁=1

45 W₀₁₀₁=1

46 W₁₀₀₁=1

47 k₂=0011

48

4 12 23 B3={0011}