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

D1=b0 v b1~x7 v b2 v b3 v b4~x7x3 v b8~x7x3 v b8x7~x8 v b11 v b15

D2=b0x1 v b1~x7 v b4~x7~x3 v b5~x4~x5 v b5x4 v b6~x4~x5 v b6x4 v b7 v b8~x7 v b8x7~x8 v b8x7x8x6 v b9

D3=b0x1 v b1x7 v b2x1 v b3x1 v b4 v b5x4 v b5~x4x5 v b6x4 v b6~x4x5 v b8~x7x3 v b8x7x8x6 v b8x7x8~x6x9 v b10x5 v b10~x5x9

D4=b1~x7 v b2~x1 v b3~x1 v b4~x7 v b5~x4~x5x2 v b6~x4~x5x2 v b8~x7x3 v b8x7x8~x6x9 v b8x7x8~x6~x9~x10 v b10~x5x9 v b10~x5~x9~x10 v b12~x10 v b13~x10 v b14~x10

 

y0=b1 v b12

y1=b1

y2=b1 v b4

y3=b2 v b5 v b6

y4=b8

y5=b2

y6=b2 v b7

y7=b10 v b13

y8=b1 v b5 v b12

y9=b12

y10=b10

y11=b11

y12=b2 v b7 v b9

y13=b15

 

t= b1~x7

m= b4~x7x3

p= b8~x7

w= b8x7

q= b0x1

f= b5~x4

k= b5x4

g= b6~x4

l= b6x4

e= b10~x5         

u= px3 

d= f v g      

n= wx8    

j=b2 v b3

 

D1=b0 v t v j v m v u v w~x8 v b11 v b15

D2=q v t v m v d~x5 v k v l v b7 v p v w~x8 v nx6 v b9

D3=q v b1x7 v jx1 v b4 v k v dx5 v l v u v nx6 v n~x6x9 v b10x5 v ex9

D4=t v j~x1 v b4~x7 v d~x5x2 v u v n~x6x9 v n~x6~x9~x10 v ex9 v e~x9~x10 v (b12 v b13 v b14) ~x10

 

y0=b1 v b12

y1=b1

y2=b1 v b4

y3=b2 v b5 v b6

y4=b8

y5=b2

y6=b2 v b7

y7=b10 v b13

y8=y0 v b5

y9=b12

y10=b10

y11=b11

y12=y6 v b9

y13=b15

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

 

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

 

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

          0 0                          K(b₀)=0000  K(b₁)=0001

          0 1

          1 2                            12     B2{0001}

          1 12               М2=   23     C1{0011,0101,1001}

          2 3                            24     D2{0011,0101,1001}

          2 4                                     W₀₀₁₁=W₀₁₀₁=W₁₀₀₁=1

          3 3                                      K(b₂)=0011 

          3 4

          4 5                             23    B3{0011}

          4 6                   M3=  33    C2{0010,0111,1011}

          412                            34    D3{0010,0111,1011}

          5 7                                     W₀₀₁₀=W₀₁₁₁=W₁₀₁₁=1

          5 8                                     K(b₃)=0010

          511

          512                            34      B4{0011,0010}

          6 7                             24      C2{0111,1011} C3{0110,1010}

          6 8                  M4=   45      D4{0110,0111,1010,1011}

          611                            46      W₀₁₁₀=W₀₁₁₁=W₁₀₁₀= W₁₀₁₁ =3

М=    612                            412     K(b₄)=0110

          7 8

          8 8                              45       B5{0110}

          8 9                              57       C4{0100,0111,1110}

          810                  M5=   58       D5{0100,0111,1110}

          811                             511      W₀₁₀₀=W₀₁₁₁=W₁₁₁₀ =1

          813                             512      K(b₅)=0111

          814

          815                             46       B6{0110}

          9  8                             67       C4{0100,1110}

         1012                 M6=   68       D6{0100,1110}

         1013                            611     W₀₁₀₀=W₁₁₁₀ =1

         1014                            612      K(b₆)=1110

         1015

         11 0

         1214                            57        B7{0111,1110}

         1215                  M7=  67        C5{0101,1111} C6{1010,1111}

         1314                            78        D7{0101,1010,1111}

         1315                                       W₀₁₀₁ =1+3=4   W₁₀₁₀ =3+1=4

         1414                                        W₁₁₁₁ =1+1=2

         1415                                        K(b₇)=1111

         15 0

 

            7 8               B8{0111,1110,1111}

            5 8               C5{0101} C6{1010}  C7{1011,1101}

            6 8               D8{0101,10101011,1101}

            8 8               W₀₁₀₁ =2+1+3=6     W₁₀₁₀ =2+3+1=6

            8 9               W₁₀₁₁ =2+2+1=5     W₁₁₀₁ =2+2+1=5

M8=    810              K(b₈)=1101

            811

            813

            814

            815

            9 8

 M9=   89     B9{1101}                                     810         B10{1101}

            98    C8{1001,1100,0101}                   1012        C8{1001,1100}

                    D8{1001,1100,0101}        M10= 1013        D10{1001,1100}

                    W₁₀₀₁=W₁₁₀₀=W₀₁₀₁=2                  1014        W₁₀₀₁=W₁₁₀₀=1

                    K(b₉)=0101                                   1015         K(b₁₀)=1001

            110   B11{0000,0111,1101,1110}

M11=  511   C0{0100,1000} C8{1100}

            611   C6{1010}

            811   D{0100,1000,1010,1100}

                     W₀₁₀₀ =1+2+2=5  W₁₀₀₀ =1+4+2=7

                     W₁₀₁₀ =2+3+1=6  W₁₁₀₀ =2+3+1=6

                     K(b₁₁)=0100

 

             1 12   B12{0001,0110,0111,1110,1001}

             4 12   C6{1010}  C10{1000,1011}

             5 12   D12{1010,1000,1011}

M12=   6 12   W₁₀₀₀ =2+3+4+2+1=12

            1012   W₁₀₁₀ =3+2+3+1+2=11

            1214   W₁₀₁₁ =2+3+2+2+1=10

            1245    K(b₁₂)=1011

             1214     B14{1011,1101,1001}

             814       C12{1010}  C8{1100}  C10{1000}

            1014      D12{1010,1100,1000}

M14=  1314      W₁₀₀₀ =2+2+1=5

            1414      W₁₀₁₀ =1+3+2=6

            1415      W₁₁₀₀ =3+1+2=6

                           K(b₁₄)=1000

 

            1415      B15{1000,1101,1001,1011,0000}

             815       C14{1010,1100}  C8{1100}  C12{1010}

            1015      D12{1010,1100}

M15=  1215      W₁₁₀₀ =1+1+2+3+2=9

            1315      W₁₀₁₀ =1+3+2+1+2=9

            15 0        K(b₁₅)=1010

 

 K(b₁₃)=1100

 

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

Таблица 12.

b0	b1		b2	b3		b4	b5	b6		b7	b8		b9
0000	0001		0011	0010		0110	0111	1110		1111	1101		0101
b10		b11			b12		b13		b14			b15
1001		0100			1011		1100		1000			1010

 

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

Таблица 12.

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода  bs	Код bs	Входной сигнал	Функции возбуждения RS-триггеров
b0	-	0000	b0 b1	0000 0001	~x1 x1	- S4
b1	y0,y1,y2 y8	0001	b2 b12	0011 1011	~x7 x7	S3 S1S3
b2	y3,y5,y6 y12	0011	b3 b4	0010 0110	~x1 x1	R4 S2R4
b3	-	0010	b3 b4	0010 0110	~x1 x1	- S2
b4	y2	0110	b5 b6 b12	0111 1110 1011	~x7~x3 ~x7x3 x7	S4 S1 S1R2S4
b5	y3,y8	0111	b7 b8 b11 b12	1111 1101 0100 1011	~x4~x5x2 ~x4~x5~x2 x4 ~x4x5	S1 S1R3 R3R4 S1R2
b6	y3	1110	b7 b8 b11 b12	1111 1101 0100 1011	~x4~x5x2 ~x4~x5~x2 x4 ~x4x5	S4 R3S4 R1R3 R2S4
b7	y6,y12	1111	b8	1101	1	R3
b8	y4	1101	b8 b9 b10 b11 b13 b14 b15	1101 0101 1001 0100 1100 1000 1010	~x7~x3 ~x7x3 x7~x8 x7x8x6 x7x8~x6x9 x7x8~x6~x9~x10 x7x8~x6~x9x10	- R1 R2 R1R4 R4 R2R4 R2S3R4
b9	y12	0101	b8	1101	1	S1
b10	y7,y10	1001	b12 b13 b14 b15	1011 1100 1000 1010	x5 ~x5x9 ~x5~x9~x10 ~x5~x9x10	S3 S2R4 R4 S3R4
b11	y11	0100	b0	0000	1	R2
b12	y0,y8,y9	1001	b14 b15	1000 1010	~x10 x10	R4 S3R4
b13	y7	1100	b14 b15	1000 1010	~x10 x10	R2 R2S3
b14	-	1000	b14 b15	1000 1010	~x10 x10	- S3
b15	y13	1010	b0	0000	1	R1R3

S1=b1x7 v b4~x7x3 v b4x7 v b5~x4

S2=b2x1 v b3x1 v b10~x5x9

S3=b1 v b8x7x8~x6~x9x10 v b10x5 v b10~x5~x9x10 v b12x10 v b13x10 b14x10

S4=b0x1 v b4~x7~x3 v b4x7 v b6~x4

R1=b6x4 v b8~x7x3 v b8x7x8x6 v b15

R2=b4x7 v b5~x4x5 v b6~x4x5 v b8x7~x8 v b8x7x8~x6~x9 v b11 v b13

R3=b5~x4~x5~x2 v b5x4 v b6~x4~x5~x2 v b6x4 v b7 v b15

R4=b2 v b5x4 v b8x7x8 v b10~x5 v b12

 

y0=b1 v b12

y1=b1

y2=b1 v b4

y3=b2 v b5 v b6

y4=b8

y5=b2

y6=b2 v b7

y7=b10 v b13

y8=b1 v b5 v b12

y9=b12

y10=b10

y11=b11

y12=b2 v b7 v b9

y13=b15

 

t= b4~x7

m= b4x7

p= b5~x4

w= b10~x5

q= b8x7x8

f= b6~x4

k= b5x4

g= p v f

l= q~x6~x9

 

S1=b1x7 v tx3 v m v p

S2=(b2 v b3)x1 v wx9

S3=b1 v lx10 v b10x5 v w~x9x10 v (b12 v b13 v b14)x10

S4=b0x1 v t~x3 v m v b6~x4

R1=b6x4 v b8~x7x3 v qx6 v b15

R2=m v gx5 v b8x7~x8 v l v b11 v b13

R3=g~x5~x2 v k v b6x4 v b7 v b15

R4=b2 v k v q v w v b12

 

y0=b1 v b12

y1=b1

y2=b1 v b4

y3=b2 v b5 v b6

y4=b8

y5=b2

y6=b2 v b7

y7=b10 v b13

y8=y0 v b5

y9=b12

y10=b10

y11=b11

y12=y6 v b9

y13=b15

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

 

7. Выбор и обоснование структурной  схемы УА. Построение логической  схемы управляющего микропрограммного  автомата

 

Сравнивая построения автомата на основе модели Мура и Мили, видно, что построение автомата по модели Мили требует меньше аппаратурных затрат, чем построение автомата по модели Мура. Модель Мили на D-триггерах имеет цену по Квайну 86, на RS-триггерах цена составляет 96, на счётчике цена составляет 85.

Т.к. цена по Квайну кодирования автомата Мили на D-триггерах и счетчике отличается лишь на 1 пересчитаем её с учетом входов элементов памяти, дешифратора и элементов, используемых для начальной установки. Тогда сложность на D-триггерах составит 86+8(элементы памяти) + 3(дешифратор) + +2(начальная установка)+2(формирование состояния а7) =101, а для счетчика – 85+7(элементы памяти) + 3(дешифратор)+2(начальная установка)+ +2(формирование состояния а7) =99. Таким образом выигрывает автомат Мили на счетчике.

В приложение Е приведена функциональная схема проектируемого МПА, управляющего выполнением умножения двоичных чисел в формате ПЗ четвертым способом в ДК с простой коррекцией и порядками. Функциональная схема построена в основном логическом  базисе  И, ИЛИ, НЕ в полном соответствии с приведенной для модели Мили системой логических уравнений для функций возбуждения элементов памяти.

 

8. Заключение

 

В ходе выполнения курсовой работы была разработана функциональная схема МПА, управляющего выполнением умножения двоичных чисел в формате ПЗ четвертым способом в ДК с простой коррекцией и порядками.

При синтезе МПА была рассмотрена  модель Мили и модель Мура. В результате проделанной работы оказалось, что наименьшие аппаратурные затраты даёт модель Мили с использованием счётчика в качестве элементов памяти.

 

Приложение А (обязательное):

Функциональная  схема операционного автомата

 

 

 

 

 

 

 

 

Приложение Б (обязательное)

Содержательная граф-схема алгоритма

 

 

Приложение В (обязательное)

Отмеченная граф-схема алгоритма

 

 

Приложение Г (обязательное)

Граф автомата для модели Мили

 

 

 

 

 

 

 

 

 

Приложение Д (обязательное)

Граф автомата для модели Мура

 

 

 

Приложение Е (обязательное)

Функциональная  схема управляющего микропрограммного  автомата

 

 

 

Библиографический список:

1. Курс лекций по дисциплине “Дискретная математика”.
2. В.Ю.Мельцов, Т.Р.Фадеева.  Синтез микропрограммных управляющих автоматов. Учебное пособие. Киров, 2010 год.
3. Т.Р. Фадеева, Л.И.Матвеева, М.Л. Долженкова. Арифметические основы ЭВМ. Методические указания к курсовой работе. Киров, 2007 год.
4. Б.Г.Лысиков. Арифметические и логические основы цифровых автоматов. Мн: Выш. школа, 1980 год.

Курс лекций по дисциплине “Теория автоматов”.