Синтез микропрограммного автомата для операции умножения двоичных чисел в ПЗ 4 способом

-структура на основе счетчика выгодна, когда граф проектируемого автомата имеет большое количество последовательных (стандартных) переходов и незначительное число нестандартных;

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

В управляющем автомате в качестве ЭП могут использоваться как D-триггеры, так и RS-триггеры. Также могут использоваться и счетчики.

При использовании D-триггеров в качестве элементов памяти при переходе из одного состояния в другое сигналы возбуждения должны быть поданы на те триггеры, которые в коде состояния содержат единицу. Отсюда следует, что для получения минимального кодирования необходимо закодировать состояния кодами, содержащими наименьшее количество единиц. Для этого используют инверсные таблицы переходов.

Для RS-триггеров лучше использовать соседнее кодирование, так как именно этот способ минимизирует число переключений ЭП.

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

6.1Кодирование  состояний автомата Мили на  D-триггерах

 

Составим инверсную таблицу  переходов (см. таблицу 3) и закодируем состояния четырехразрядными двоичными  числами, в которые будет входить  наименьшее число единиц.

 

Таблица 3.

a0	a1	a2	a3	a4	a5	a6	a7	a8
a0,a4,a6,a8	a0	a1,a2	a2	a3	a4,a6	a5	a6	a1,a3,a4,a6,a7,a8
0001	0011	0010	1010	0110	0100	1100	1000	0000

 

Как видно из таблицы 3, состояние  a₈ с наибольшим числом переходов в него кодируется 0000. Состояния с меньшим числом переходов обозначаются кодом с одной единицей, затем с двумя и до тех пор, пока все состояния графа не будут закодированы.

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

 

Структурная таблица переходов  и выходов представлена в таблице  4

 

 

Таблица 4.  Структурная таблица переходов и выходов кодирования автомата Мили на D-триггерах.

Исходное состояние	Код  am	Состояние перехода  as	Код  as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения D-триггеров
a0	0001	a0 a1	0001 0011	~x1 x1	- y0,y1,y2,y8	D4 D3D4
a1	0011	a2 a8	0010 0000	~x7 x7	y3,y5,y6,y12 y0,y8,y9	D3 -
a2	0010	a2 a3	0010 1010	~x1 x1	- y2	D3 D1D3
a3	1010	a4 a4 a8	0110 0110 0000	~x7x2 ~x7~x2 x7	y3 y3,y8 y0,y8,y9	D2D3 D2D3 -
a4	0110	a0 a5 a5 a8	0001 0100 0100 0000	x4 ~x4~x5x3 ~x4~x5~x3 ~x4x5	y11 y6,y12 - y0,y8,y9	D4 D2 D2 -
a5	0100	a6	1100	1	y4	D1D2
a6	1100	a0 a5 a5 a7 a8 a8	0001 0100 0100 1000 0000 0000	x7x8x6 ~x7x3 ~x7~x3 x7~x8 x7x8~x6x9 x7x8~x6~x9	y11 y12 - y7,y10 y7 -	D4 D2 D2 D1 - -
a7	1000	a8 a8 a8	0000 0000 0000	x5 ~x5x9 ~x5~x9	y0,y8,y9 y7 -	- - -
a8	0000	a0 a8	0001 0000	x10 ~x10	y13 -	D4 -

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

D1=a2x1 v a5 v a6x7~x8

D2=a3~x7 v a4~x4~x5 v a5 v a6~x7

D3=a0x1 v a1~x7 v a2 v a3~x7

D4=a0 v a4x4 v a6x7x8x6 v a8x10

 

y0=a0x1 v a1x7 v a3x7 v a4~x4x5 v a7x5

y1=a0x1

y2=a0x1 v a2x1

y3=a1~x7 v a3~x7

y4=a5

y5=a1~x7

y6=a1~x7 v a4~x4~x5x3

y7=a6x7~x8 v a6x7x8~x6x9 v a7~x5x9

y8=a0x1 v a1x7 v a3~x7~x2 v a3x7 v a4~x4x5 v a7x5

y9=a1x7 v a3x7 v a4~x4x5 v a7x5

y10=a6x7~x8

y11=a4x4 v a6x7x8x6

y12=a1~x7 v a4~x4~x5x3 v a6~x7x3

y13=a8x10

 

t= a2x1

m= a6x7

k= a3~x7

w= a4~x4

p= a6~x7

 

e= a4x4

f= (a1 v a3)x7

q= a7x5

u=w~x5

l=mx8

D1=t v a5 v y10

D2=k v u v a5 v p

D3=y1 v y3 v a2

D4=a0 v y11 v y13

 

 

y0=y1 v y9

y1=a0x1

y2=y1 v t

y3=y5 v k

y4=a5

y5=a1~x7

y6=y5 v ux3

 

 

y7=y10 v l~x6x9 v a7~x5x9

y8=y1 v y9 v k~x2

y9=f v wx5 v q

y10=m~x8

y11=e v lx6

y12=y6 v px3

y13=a8x10

Цена по Квайну C=86, причем в схеме УА предлагается использовать 4-х входовой дешифратор.

 

6.2 Кодирование состояний автомата Мили на RS-триггерах

 

Составим матрицу переходов  М и произведем кодирование состояний  автомата.

 

     00                   k₀=0000

     01                   k₁=0001

     12                                  

     18           12      B2 ={0001}

     22       M2= 22      C1={0011,0101,1001}       

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

     38            W₀₀₁₁=1

     34       W₀₁₀₁=1

     40                  W₁₀₀₁=1

     45                  k₂=0011

          48                   

          56                   

     60   

     65

     67

     68

  78

          80

          88      

                     B3={0011} 

      M3= 38     C2={0010,0111,1011}

34       D3={0010,0111,1011}

       23      W₀₀₁₀=1

                            W₀₁₁₁=1

                              W₁₀₁₁=1

k₃=0010

 

                              34            

                    M4= 40

                              48       B4={0000,0010} 

45       C3={0110,1010} C0={1000,0100}

                     D4={0100,0110,1000,1010}

   W₀₁₀₀=ô0100-0010ô²+ô0100-0000ô²=2+1=3

   W₀₁₁₀=ô0110-0010ô²+ô0110-0000ô²=1+2=3

   W₁₀₀₀=ô1000-0010ô²+ô1000-0000ô²=2+1=3

   W₁₀₁₀=ô1010-0010ô²+ô1010-0000ô²=1+2=3

                              k₄=1010

 

 

      45  B5={1010}

      M5= 56 C4={1000,1011,1110}

D5={1000,1011,1110}

     W₁₀₀₀=1

                            W₁₀₁₁=1     

                              W₁₁₁₀=1

k₅=1000 

       

                              56

                              60                             

                   M6=   65 B6={1000,0000} 

67 C5={1001,1100} C0{0100}

       68 D6={0100,1001,1100}

W₀₁₀₀=ô0100-1000ô²+ô0100-0000ô²=2+1=3

W₁₀₀₁=ô1001-1000ô²+ô1001-0000ô²=1+2=3

W₁₁₀₀=ô1100-1000ô²+ô1100-0000ô²=1+2=3

                              k₆=1100

 

              B7={1100}

      M7= 67 C6={1101,1110,0100}

78 D7={1101,1110,0100}

                                        W₁₁₀₁=1

                            W₁₁₁₀=1     

                              W₀₁₀₀=1

k₇=0100 

 

                              78      B8={0001,0010,0000,1101}

                              80 C1={0101,1001} C4{1011,1110} 

                              88  C7={0110,0101}

      M8= 18 C3={0110} C6{1110,1101}

38 D8={0101,0110,1001,1011,1101,1110}

    48 

    60 

W₀₁₀₁=1+2+0+1+3+4+2=13      W₀₁₁₀=1+2+0+3+1+2+2=11

W₁₀₀₁=3+2+0+1+3+2+2=13      W₁₀₁₁=4+3+0+2+2+1+3=15

W₁₁₀₁=2+3+0+2+4+3+1=15      W₁₁₁₀=2+3+0+2+4+3+1=15

k₈=0110

Результат кодирования приведен в  таблице 5.

 

 

Таблица  5 .  Результат кодирования автомата Мили на RS-триггерах.

a0	a1	a2	a3	a4	a5	a6	a7	a8
0000	0001	0011	0010	1010	1000	1100	0100	0110

 

 

 

 

Структурная таблица переходов  и выходов представлена в таблице 6

 

Таблица 6.

Исходное состояние	Код  am	Состояние перехода  as	Код  as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения RS-триггеров
a0	0000	a0 a1	0000 0001	~x1 x1	- y0,y1,y2,y8	- S4
a1	0001	a2 a8	0011 0110	~x7 x7	y3,y5,y6,y12 y0,y8,y9	S3 S2S3R4
a2	0011	a2 a3	0011 0010	~x1 x1	- y2	- R4
a3	0010	a4 a4 a8	1010 1010 0110	~x7x2 ~x7~x2 x7	y3 y3,y8 y0,y8,y9	S1 S1 S2
a4	1010	a0 a5 a5 a8	0000 1000 1000 0110	x4 ~x4~x5x3 ~x4~x5~x3 ~x4x5	y11 y6,y12 - y0,y8,y9	R1R3 R3 R3 R1S2
a5	1000	a6	1100	1	y4	S2
a6	1100	a0 a5 a5 a7 a8 a8	0000 1000 1000 0100 0110 0110	x7x8x6 ~x7x3 ~x7~x3 x7~x8 x7x8~x6x9 x7x8~x6~x9	y11 y12 - y7,y10 y7 -	R1R2 R2 R2 R1 R1S3 R1S3
a7	0100	a8 a8 a8	0110 0110 0110	x5 ~x5x9 ~x5~x9	y0,y8,y9 y7 -	S3 S3 S3
a8	0110	a0 a8	0000 0110	x10 ~x10	y13 -	R2R3 -

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S1=a3~x7

S2=a1x7 v a3x7 v a4~x4x5 v a5

S3=a1 v a6x7x8~x6 v a7

S4=a0x1

R1=a4x4 v a4~x4x5 v a6x7

R2=a6x7x8x6 v a6~x7 v a8x10

R3=a4x4 v a4~x4~x5 v a8x10

R4=a1x7 v a2x1

 

y0=a0x1 v a1x7 v a3x7 v a4~x4x5 v a7x5

y1=a0x1

y2=a0x1 v a2x1

y3=a1~x7 v a3~x7

y4=a5

y5=a1~x7

y6=a1~x7 v a4~x4~x5x3

 

 

y7=a6x7~x8 v a6x7x8~x6x9 v a7~x5x9

y8=a0x1 v a1x7 v a3~x7~x2 v a3x7 v a4~x4x5 v a7x5

y9=a1x7 v a3x7 v a4~x4x5 v a7x5

y10=a6x7~x8

y11=a4x4 v a6x7x8x6

y12=a1~x7 v a4~x4~x5x3 v a6~x7x3

y13=a8x10

t= a3~x7

p= a1x7

m= a3x7

k= a4~x4

f= a6x7

w= a4x4

d= a6~x7

h= a2x1

g= a7x5

u=kx5    

e=fx8

S1=t

S2=p v m v u v a5

S3=a1 v e~x6 v a7

S4=y1

 

R1=w v u v f

R2=ex6 v d v y13

R3=w v k~x5 v y13

R4=p v h

 

y0=y1 v y9

y1=a0x1

y2=y1 v h

y3=y5 v t

y4=a5

y5=a1~x7

y6=y5v k~x5x3

 

 

y7=y10 v e~x6x9 v a7~x5x9

y8=y1 v y9 v t~x2

y9=p v m v u v g

y10=f~x8

y11=w v ex6

y12=y6 v dx3

y13=a8x10Цена по Квайну C=96, причем в схеме УА предлагается использовать 4-х входовой дешифратор.

 

6.3Кодирование  состояний автомата Мили на  счетчике

 

Закодируем состояния таким  образом, чтобы разность значений кодов  между соседними состояниями  составляла единицу (см.таблицу 7).

Таблица 7

a0	a1	a2	a3	a4	a5	a6	a7	a8
0001	0010	0011	0100	0101	0110	0111	1000	0000

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

Исходное состояние	Код  am	Состояние перехода  as	Код  as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения счетчика
a0	0001	a0 a1	0001 0010	~x1 x1	- y0,y1,y2,y8	- E+1
a1	0010	a2 a8	0011 0000	~x7 x7	y3,y5,y6,y12 y0,y8,y9	E+1 M
a2	0011	a2 a3	0011 0100	~x1 x1	- y2	- E+1
a3	0100	a4 a4 a8	0101 0101 0000	~x7x2 ~x7~x2 x7	y3 y3,y8 y0,y8,y9	E+1 E+1 M
a4	0101	a0 a5 a5 a8	0001 0110 0110 0000	x4 ~x4~x5x3 ~x4~x5~x3 ~x4x5	y11 y6,y12 - y0,y8,y9	D1M E+1 E+1 M
a5	0110	a6	0111	1	y4	E+1
a6	0111	a0 a5 a5 a7 a8 a8	0001 0110 0110 1000 0000 0000	x7x8x6 ~x7x3 ~x7~x3 x7~x8 x7x8~x6x9 x7x8~x6~x9	y11 y12 - y7,y10 y7 -	D1M M E+1 M E+1 E+1 M M
a7	1000	a8 a8 a8	0000 0000 0000	x5 ~x5x9 ~x5~x9	y0,y8,y9 y7 -	M M M
a8	0000	a0 a8	0001 0000	x10 ~x10	y13 -	E+1 -

Таблица 8

 

Работа счётчика производится в  соответствии с таблицей 9

Таблица 9

М	E+1	Режим
1 0 1 0	0 1 1 0	Запись  в счётчик Прямой счёт Обратный счёт Хранение

 

E+1=a0x1 v a1~x7 v a2x1 v a3~x7 v a4~x4~x5 v a5 v a6~x7 v a6x7~x8 v a8x10

M=a1x7 v a3x7 v a4x4 v a4~x4x5 v a6x7x8 v a6~x7 v a7

D1=a4x4 v a6x7x8x6

 

y0=a0x1 v a1x7 v a3x7 v a4~x4x5 v a7x5

y1=a0x1

y2=a0x1 v a2x1

y3=a1~x7 v a3~x7

y4=a5

y5=a1~x7

y6=a1~x7 v a4~x4~x5x3

y7=a6x7~x8 v a6x7x8~x6x9 v a7~x5x9

y8=a0x1 v a1x7 v a3~x7~x2 v a3x7 v a4~x4x5 v a7x5

y9=a1x7 v a3x7 v a4~x4x5 v a7x5

y10=a6x7~x8

y11=a4x4 v a6x7x8x6

y12=a1~x7 v a4~x4~x5x3 v a6~x7x3

y13=a8x10t= a2x1

m= a3~x7

k= a4~x4

p= a6~x7

f= a6x7

g= (a1 v a3)x7   l= a4x4

e= a7x5  

h=fx8 

n=kx5

u= k~x5

E+1=y2 v y3 v u v a5 v p v y10 v y13

M=g v l v n v h v p v a7

D1=y11

y0=y1 v y9

y1=a0x1

y2=y1 v t

y3=y5 v m

y4=a5

y5=a1~x7

y6=y5 v ux3

y7=y10 v h~x6x9 v a7~x5x9

y8=y1 v y9 v m~x2

y9=g v n v e

y10=f~x8

y11=l v hx6

y12=y6 v px3

y13=a8x10

Цена по Квайну C=85, причем в схеме УА предлагается использовать 3-х входовой дешифратор. 

6.4Кодирование  состояний автомата Мура на D-триггерах

 

Составим  инверсную таблицу переходов (см. таблицу 10) и закодируем состояния четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц.

 

Таблица 10.

b0	b1	b2	b3	b4	b5	b6	b7	b8	b9
b0,b11,b15	b0	b1	b2,b3	b2,b3	b4	b4	b5,b6	b5,b6,b7,b8,b9	b8
1000	1110	1101	1001	1010	0111	1011	0101	0100	1111

 

b10	b11	b12	b13	b14	b15
b8	b5,b6,b8	b1,b4,b5,b6,b10	b8,b10	b8,b10,b12,b13,b14	b8,b10,b12,b13,b14
1100	0110	0010	0011	0001	0000

 

Как видно  из таблицы 10, состояние b₁₅ с наибольшим числом переходов в него кодируется 0000. Состояния с меньшим числом переходов обозначаются кодом с одной единицей, затем с двумя и до тех пор, пока все состояния графа не будут закодированы.

 

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

 

Таблица 11.

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода  bs	Код bs	Входной сигнал	Функции возбуждения D-триггеров
b0	-	1000	b0 b1	1000 1110	~x1 x1	D1 D1D2D3
b1	y0,y1,y2 y8	1110	b2 b12	1101 0010	~x7 x7	D1D2D4 D3
b2	y3,y5,y6 y12	1101	b3 b4	1001 1010	~x1 x1	D1D4 D1D3
b3	-	1001	b3 b4	1001 1010	~x1 x1	D1D4 D1D3
b4	y2	1010	b5 b6 b12	0111 1011 0010	~x7~x3 ~x7x3 x7	D2D3D4 D1D3D4 D3
b5	y3,y8	0111	b7 b8 b11 b12	0101 0100 0110 0010	~x4~x5x2 ~x4~x5~x2 x4 ~x4x5	D2D4 D2 D2D3 D3
b6	y3	1011	b7 b8 b11 b12	0101 0100 0110 0010	~x4~x5x2 ~x4~x5~x2 x4 ~x4x5	D2D4 D2 D2D3 D3
b7	y6,y12	0101	b8	0100	1	D2
b8	y4	0100	b8 b9 b10 b11 b13 b14 b15	0100 1111 1100 0110 0011 0001 0000	~x7~x3 ~x7x3 x7~x8 x7x8x6 x7x8~x6x9 x7x8~x6~x9~x10 x7x8~x6~x9x10	D2 D1D2D3D4 D1D2 D2D3 D3D4 D4 -
b9	y12	1111	b8	0100	1	D2
b10	y7,y10	1100	b12 b13 b14 b15	0010 0011 0001 0000	x5 ~x5x9 ~x5~x9~x10 ~x5~x9x10	D3 D3D4 D4 -
b11	y11	0110	b0	1000	1	D1
b12	y0,y8,y9	0010	b14 b15	0001 0000	~x10 x10	D4 -
b13	y7	0011	b14 b15	0001 0000	~x10 x10	D4 -
b14	-	0001	b14 b15	0001 0000	~x10 x10	D4 -
b15	y13	0000	b0	1000	1	D1