43301

Создание функциональной схемы микропрограммного управляющего автомата

Курсовая

Информатика, кибернетика и программирование

Построение графа автомата и структурной таблицы переходов и Выходов 12 7.1 Построение графа автомата и структурной таблицы переходов и выходов 22 22 8. Получение логических выражений для функций возбуждения RSтриггеров 28 9 Построение функциональной схемы управляющего микропрограммного автомата 30 10 Заключение 31 Список использованных сокращений 32 Библиографический список 33 Приложение А 34 Приложение Б 35 Приложение В 36 Приложение Г 37 Приложение Д 38 Приложение Е 39 УДК 681. Синтез микропрограммного управляющего автомата.

Русский

2013-11-04

1.09 MB

12 чел.

Содержание

Реферат

1 Постановка задачи

3

2 Алгоритм умножение чисел I сп. в ДК с простой коррекцией

4

3 Численные примеры

4

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

8

5 Разработка содержательной граф-схемы алгоритма

10

6 Построение отмеченной граф-схемы алгоритма

11

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

12

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

12

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

13

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

14

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

16

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

18

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

20

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

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

22

22

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

23

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

25

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

26

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

28

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

30

10 Заключение

31

Список использованных сокращений

32

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

33

Приложение А

34

Приложение Б

35

Приложение В

36

Приложение Г

37

Приложение Д

38

Приложение Е

39


УДК 681.3
   Реферат

Ельцов Д.М. Синтез микропрограммного управляющего автомата. Курсовая работа / ВятГУ, каф. ЭВМ, рук. ст.преподаватель Агалаков  Е.В. – Киров, 2013. Графическая часть 3 л. формата. А2

ОПЕРАЦИОННЫЙ АВТОМАТ, МИКРОПРОГРАММНЫЙ УПРАВЛЯЮЩИЙ АВТОМАТ , ГРАФ-СХЕМА  АЛГОРИТМА, ГРАФ, ФУНКЦИОНАЛЬНАЯ СХЕМА, МОДЕЛЬ МИЛИ, МОДЕЛЬ МУРА

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

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

1. Постановка задачи

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

Функциональную схему устройства построить в основном логическом базисе. Операнды разрядностью 4 байта (тридцать два разряда) поступают по входной шине (ШИВх) в  дополнительном коде (ДК), результат также в ДК  выводится по выходной шине (ШИВых). 

2. Алгоритм умножения двоичных чисел I сп. в ДК с простой коррекцией:

1. Определить знак произведения путем сложения по модулю два знаковых разрядов сомножителей.

2. Проверить множимое на равенство нулю: если равно нулю, операцию умножения следует прекратить, т.к. результат будет также равным нулю.

3. Проверить множитель на равенство нулю: если равен нулю, операцию умножения следует прекратить, т.к. результат будет также равным нулю.

4. Перед циклом умножения произвести коррекцию.

Если хотя бы один из сомножителей отрицателен, выполнить
коррекцию по следующим правилам:

- если один сомножитель отрицателен, к псевдопроизведению прибавляется дополнительный код от модуля положительного сомножителя;

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

5. Произвести анализ цифры очередного разряда множителя.

6. Произвести суммирование множимого с суммой частичных произведений (ЧП), если цифра множителя «1», иначе перейти к п.7 алгоритма.

7. Произвести сдвиг множителя и суммы ЧП на один разряд вправо.

8. Присвоить модулю произведения знак из п.1 данного алгоритма.

3. Численные примеры

Выполним ручной подсчет в соответствии с вышеуказанным алгоритмом.

В качестве множителя возьмём число 55, а в качестве множимого 36.

  1.  Представим числа отрицательными.

A = -55 = 1101112, Апк = 1,110111,   Адк = 1,001001

B = -36 = 1001002, Впк = 1,100100,   Вдк = 1,011100.

                            

Таблица 1.

Множитель

Множимое

Сумматор

Пояснения

1,001001

1,011100

0,000000000000

  0,011100000000

   Сложение

0, 011100000000

Сдвиг

1,000100

0,001110000000

Сдвиг

1,000010

0,000111000000

Сдвиг

1,000001

0,000011100000

Сложение

0,011100000000

Сдвиг

0,011111100000

1,000000

0,001111110000

Сдвиг

1,000000

0,000111111000

Сдвиг

0,000011111100

Произведем коррекцию (прибавим к псевдопроизведению Апк, а затем Впк)

Псевдопроизведение 0,000011111100

Апк 0,110111000000

0,111010111100

                                        Впк 0,100100000000

0,011110111100

Получили результат: 0,011110111100

P = (-55)*(-36) = 1980 = 111101111002

2.Представим числа таким образом: А<0, B>0

A = -55 = 1101112, Апк = 1,110111,   Адк = 1,001001

B = 36 = 1001002, Впк = 0,100100,    Вдк = 0,100100.

                             

Таблица 2.

Множитель

Множимое

Сумматор

Пояснения

1,001001

0,100100

0,000000000000

0,100100000000

0,100100000000

Сложение

Сдвиг

1,000100

0,010010000000

Сдвиг

1,000010

0,001001000000

Сдвиг

1,000001

0,000100100000

0,100100000000

0,101000100000

Сложение

Сдвиг

1,000000

0,010100010000

Сдвиг

1,000000

0,001010001000

Сдвиг

0,000101000100

Произведем коррекцию (прибавим к псевдопроизведению Вдк)

Псевдопроизведение  0,000101000100

Впк 0,011100000000

0,100001000100

Получили результат:  0,100001000100

(A*B)дк=1,100001000100 ,   (A*B)пк=1,011110111100

P = (-55)*36 = -1980 = -111101111002

3.Представим числа положительными:

A = 55 = 1101112, Апк = 0,110111,   Адк = 0,110111

B = 36 = 1001002, Впк = 0,100100,    Вдк = 0,100100.

                            

Таблица 3.

Множитель

Множимое

Сумматор

Пояснения

0,110111

0,100100

0,000000000000

0,100100000000

Сложение

0,100100000000

Сдвиг

0,011011

0,010010000000

0,100100000000

Сложение

0,110110000000

Сдвиг

0,001101

0,011011000000

0,100100000000

Сложение

0,111111000000

Сдвиг

0,000110

0,011111100000

Сдвиг

0,000011

0,001111110000

0,100100000000

Сложение

0,110011110000

Сдвиг

0,000001

0,011001111000

0,100100000000

Сложение

0,111101111000

Сдвиг

0,011110111100

Коррекция не нужна, так как оба сомножителя положительны.

Получили результат:  0,011110111100

P =55*36 = 1980 = 111101111002

4. Выбор и описание структурной схемы операционного автомата

Операционный автомат (ОА) должен содержать:

 - 32-х разрядные сдвиговый влево регистр RG1 и регистр RG2 для приема операндов с ШИВх;

 - 32-х разрядный сдвиговый влево регистр RG3 для записи и хранения результата и частных сумм;

 -32-х разрядный комбинационный  сумматор SM;

 -6-ти разрядный счетчик СТ для  подсчета тактов умножения;

 -32-х разрядную схему дизъюнкции;

 - схема "сложение по модулю 2" для реализации инверсии;

 - схема "сложение по модулю 2" для определения знака произведения;

 -32-х разрядный усилитель-формирователь для выдачи результата на ШИВых.

  Операнды поступают в операционный автомат по 32-разрядной шине ШИВх и записываются в соответствующие регистры. Мантисса множителя записывается в RG1,  а мантисса  множимого в RG2. Операнды поступают в дополнительном коде. Сначала анализируются знаки операндов. Знак результата определяется с помощью схемы “сложения по модулю 2” и подается на усилитель-формирователь. Зная знаки операндов, произведем коррекцию, если это необходимо. Для этого в зависимости от p3 и p1 на плечо A сумматора поступает информация с выхода триггера RG3 или на плечо В с выхода RG2. На плечо B поступает информация либо с прямых, либо с инверсных выходов триггера RG2. Множимое, в зависимости от очередной цифры множителя, либо суммируется с предыдущей частной суммой, либо суммирование не происходит. Цикл сложения выполняется до тех пор пока в шестом разряде счетчика СТ не окажется "1". Перед выдачей результата на ШИВых содержимое RG3 и подается на усилитель-формирователь.

Таким образом, для выполнения операции умножения из управляющего автомата (УА) в операционный автомат необходимо подать управляющие сигналы, реализующие следующие микрооперации:

 

   y0 – запись в RG1, запись в СТ;

   y1 – сдвиг RG1 вправо RG1:=R1(RG1).0, сдвиг RG3 вправо RG3:=R1(RG3).0, СТ: = СТ+1;

   y2 – очистка RG1;

   y3 – запись в RG2;

    y4 – очистка RG2;

   y5 – запись в RG3;

   y6 – сброс RG3;

   y7 – инверсия выхода RG2;

   y8 – обнуление счётчика;

   y9 – управление выдачей информации на ШИВых.

   

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

Х - проверка наличия операндов на ШИВх;

Р1- знак операнда RG1;

Р2- проверка очередной цифры множителя;

Р3 - знак операнда RG2;

Р4=1, один из операндов равен “0”;  

P5=1, выполнения цикла сложения завершено;

Z - проверка возможности выдачи по ШИВых.

Таким образом, управляющий  МПА  должен вырабатывать 10  управляющих сигналов и посылать их в  ОА  в нужные такты машинного времени в соответствии с алгоритмом выполнения операции сложения, ориентируясь на 7  осведомительных сигналов, поступающих из  ОА, структурная схема которой представлена в приложении А.

5. Реализация содержательной ГСА

 Выполнение алгоритма начинается с проверки наличия множителя на ШИВх. Он заносится в RG1, RG2, логическим условием P4 проверяется осведомительный сигнал, если он равен “0”, то поступил не нулевой операнд, иначе алгоритм заканчивается и результат умножения равен “0”. Далее с инверсных выходов RG2 множитель подаётся на плечо В сумматора SM, где получается ДК, а затем заносится в RG3. Далее происходит проверка наличия множимого на ШИВх и занесение его в RG2 с последующей проверкой на “0”. Также в счетчик тактов  заносится 1, знак произведения определяется путём  сложения по модулю 2 знаков множителя  и  множимого в конце алгоритма.

Далее, следуя алгоритму, логическим условием P3 проверяется знак множимого, если он равен “1”, то логическим условием Р1 проверяется знак множителя и в зависимости от его знака на плечо А сумматора SM поступают данные, записанные в RG3 или происходит проверка очередной цифры множителя. Если ли знак множимого равен “0”, то RG3 очищается и происходит проверка знака множителя логическим условием Р1. Далее проверяется очередная цифра множителя логическим условием Р2, если он равен “1”, то производим такт сложения суммы ЧП с множимым, иначе переходим к проверке логического условия P5. Если он равен “0”, то следует произвести сдвиги суммы ЧП и множителя, т.е. RG3 и RG1, в счётчик СТ прибавляется 1, в противном случае такт является последним и производится проверка на возможность выдачи результата на ШИВых, завершение алгоритма.

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

6. Построение отмеченной ГСА

Перед разметкой содержательной ГСА необходимо возле каждой  операторной вершины проставить управляющие сигналы УА и обеспечивающие выполнение требуемых действий в соответствии со списком МО операционного автомата. Совокупность МО для каждой операторной вершины образуют микрокоманды (МК), список которых приведен в таблице 4.

                                                                                                Таблица 4.

MK

Совокупность  МО

Y1

y0,y3,y5

Y2

у7,y5

Y3

у3

Y4

y6

Y5

y5

Y6

y1

Y7

у9

Каждой условной вершине содержательной ГСА поставим  в  соответствие один из входных  сигналов  управляющего  автомата X1, … ,X7, список которых дан в таблице 5.

Таблица 5.

Входной сигнал УА

X1

X2

X3

X4

X5

X6

X7

Логическое условие ОА

X

P1

P2

P3

P4

P5

Z

Далее в полном соответствии с содержательной  ГСА  строим отмеченную  ГСА (рис. 3), условным вершинам которой приписывается один из входных сигналов УА ( Х1,...,Х7 ), а операторным вершинам - одна из МК (в скобках указана совокупность МО для каждой МК). Выделение состояний управляющего  МПА возможно в соответствии с моделью Мили или моделью Мура.

В приложении В приведена разметка  ГСА  для модели Мили символами   a0, а1, ... , а8  и для модели Мура - символами b0, b1, ... , b11. Таким образом, если строить управляющий  МПА  в соответствии с моделью Мили, то он будет иметь 9  состояний, а в соответствии с моделью Мура  -  12 состояний.

В двух вершинах ожидания (5 и 17) при разметке по Муру введены фиктивные состояния автомата  b3 и  b10.

Явно большее число состояний для модели Мура по сравнению с моделью Мили не дает достаточных оснований для выбора модели Мили как более предпочтительной. Сравнение вариантов можно будет выполним лишь на этапе построения функциональных схем  УА, сравнив схемы по сложности и быстродействию. Поэтому далее будем вести проектирование УА  параллельно для модели Мили и для модели Мура.

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

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

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

 

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

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

                  Таблица 6.

as

a0

a1

a2

a3

a4

a5

a6

a7

а8

{am}

a8,a0

a0

a2,a1

a2

a3

a4

а5,a7

a6

a1,a3,a7,a8

Наибольшее количество переходов в состояние a8 - закодируем его кодом К(a8) = 0000. Для остальных состояний первой строки табл.6 назначим коды с одной "1" и более.Таким образом, таблица кодирования для D-триггеров такова:     

                           Таблица 7.

as

a0

a1

a2

a3

a4

a5

a6

a7

a8

K{as}

0001

0101

0010

0110

0011

1001

0100

1000

0000

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

Исходное состояние

am

Код   am

Состояние перехода

as

Код as

Входной сигнал

X(am, as)

Выходные сигналы

Y(am,as)

Функция возбуждения D-триггеров

a0

0001

a0

a1

0001

0101

~X1

X1

-

y0y3y5

D0

D2D0

a1

0101

a2

a8

0010

0000

~X5

X5

y7y5

-

D1

-

a2

0010

a2

a3

0010

0110

~X1

X1

-

y3

D1

D2D1

a3

0110

a4

a4

a8

0011

0011

0000

~X5~X4

~X5X4

X5

y6

-

y6

D1D0

D1D0

-

a4

0011

a5

a5

1001

1001

~X2

X2

-

y7y5

D3D0

D3D0

a5

1001

a6

a6

0100

0100

X3

~X3

y5

-

D2

D2

a6

0100

a7

1000

1

y1

D3

a7

1000

a6

a6

a8

0100

0100

0000

~X6~X3

~X6X3

X6

-

y5

-

D2

D2

-

а8

0000

a0

a8

0001

0000

X7

~X7

y9

-

D0

-

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

D-триггеров

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

D0 = a0~x1 V a0x1 V a3~x5x4 V a3~x5~x4 V a4x2 V a4~x2 V a8x7

D1 = a1~x5 V a2~x1 V a2x1 V a3~x5x4 V a3~x5~x4

D2 = a0x1 V a2x1 V a5x3 V a5~x3 V a7~x6x3 V a7~x6~x3

D3 = a4x2 V a4~x2 V a6

 

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

y0 = a0x1

y1 = a6

y3 = a0x1 V a2x1

y5 = a0x1 V a1~x5 V a4x2 V a5x3 V a7~x6x3

y6 = a3~x5~x4 V a3x5

y7 = a1~x5 V a4x2

y9= a8x7

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

c = a0x1             (2)                   i = a4x2       (2)

d = a7~x6          (2)          

e = a1~x5           (2)              

f = a8x7              (2)

g = a3~x5           (2)

h = a2x1              (2)

D0 = a0~x1 V a0x1 V a3~x5x4 V a3~x5~x4 V a4x2 V a4~x2 V a8x7 =

a0 V g V a4 V f   (4)

D1 = a1~x5 V a2~x1 V a2x1 V a3~x5x4 V a3~x5~x4 = e V a2 V g       (3)

D2 = a0x1 V a2x1 V a5x3 V a5~x3 V a7~x6x3 V a7~x6~x3 = c V h V a5 V d     (4)

D3 = a4x2 V a4~x2 V a6 = a4 V a6       (2)

y0 = a0x1 = c          (0)

y1 = a6                    (0)

y3 = a0x1 V a2x1 = c V h     (2)

y5 = a0x1 V a1~x5 V a4x2 V a5x3 V a7~x6x3 = c V e V i V a5x3 V a7 ~x6x3    (10)

y6 = a3~x5~x4 V a3x5         (7)

y7 = a1~x5 V a4x2 = e V i      (2)

y9= a8x7= f      (0)

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

Полная цена по Квайну: 49(КС)+12(ЭП)+4(DC)+4(b)=71

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

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

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

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

1).  

    B2={1} С1={0011,0101,1001}               W0011=1

 D2={0011,0101,1001}               W0101=1

                                                                          W1001=1

                                    Выбираем любой:  K(a2)=0011                                                        

2).

    B8={1, 0} C1={0101,1001}                                   W0101=3

                       С0={0010,0100,1000}                          W1001=3  

 D3={0101,1001,0010,0100,1000}        W0010=3

         W0100=3

         W1000=3

            Выбираем любой:     K(a8)=0101

3).

     B3={2, 8}   C2={0010,0111,1011}     W0010=4

 C8={0100,0111,1101}     W0111=2

 D3={0010,0111,1011,0100,1101}        W1011=4

         W0100=4

         W1101=4

                                  Выбираем любой:     K(a3)=0111

4).

    B4={3} C3={0110,1111}         W0110=1

 D4={0110,1111}                        W1111=1

     

                                  Выбираем любой:     K(a4)=0110

5).

    B5={4} C4={0100,0010,1110}   W0100=1

  D5={0100,0010,1110}   W0010=1

                                                                        W1110=1

                          Выбираем любой:     K(a5)=0100

6).

    B6={5} C5={1100}                          

 D6={1100}                          W1100=1

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

7).

    B7={6, 8}    C6={1101,1110,1000} W1101=2

                         C8={1101}               W1110=4                 

                          D7={1101,1110,1000} W1000=4

                       Выбираем:     K(a7)=1101

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

                                        Таблица 8.

as

a0

a1

a2

a3

a4

a5

a6

a7

a8

K{as}

0000

0001

0011

0111

0110

0100

1100

1101

0101

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

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

            

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

Исходное состояние

Код  am

Состояние перехода  as

Код  as

Входной сигнал X(am,as)

Выходные сигналы Y(am,as)

Функции возбуждения RS-триггеров

a0

0000

a0

a1

0000

0001

~X1

X1

-

y0y3y5

-

S0

a1

0001

a2

a8

0011

0101

~X5

X5

y7y5

-

S1

S2

a2

0011

a2

a3

0011

0111

~X1

X1

-

y3

-

S2

a3

0111

a4

a4

a8

0110

0110

0101

~X5~X4

~X5X4

X5

y6

-

y6

R0

R0

R1

a4

0110

a5

a5

0100

0100

~X2

X2

-

y7y5

R1

R1

a5

0100

a6

a6

1100

1100

X3

~X3

y5

-

S3

S3

a6

1100

a7

1101

1

y1

S0

a7

1101

a6

a6

a8

1100

1100

0101

~X6~X3

~X6X3

X6

-

y5

-

R0

R0

R3

a8

0101

a0

a8

0000

0101

X7

~X7

y9

-

R2R0

 -

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

S0 = a0x1 V a6

S1 = a1~x5

S2 = a1x5 V a2x1

S3 = a5x3 V a5~x3

R0 = a3~x5x4 V a3~x5~x4 V a7~x6x3 V a7~x6~x3 V a8x7

R1 = a3x5 V a4~x2 V a4x2

R2 = a8x7

R3 = a7x6

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

l = a2x1          (2)         r = a3x5       (2)    

m = a0x1        (2)         s = a3~x5     (2)

t = a1~x5        (2)

o = a1x5         (2)         u = a7~x6    (2)

p = a8x7         (2)         

i = a4x2          (2)

S0 = m V a6        (2)

S1 = t                   (0)

S2 = o V l            (2)

S3 = a5                (0)

R0 = s V u V p           (3)

R1 = r V a4                (2)

R2 = p                        (0)

R3 = a7x6                  (2)

y0 = m                                (0)

y1 = a6                               (0)

y3 = m V l                          (2)

y5 = m V t V i V a5x3 V a7~x6x3     (10)

y6 = s~x4 V r                      (4)

y7 = t V i                              (2)

y9 = p                                   (0)

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

Полная цена по Квайну: С = 50(КC)+12(ЭП)+4(ДЦ)+4(b) = 70

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

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

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

                                                                                                                  Таблица 10.

As

a0

a1

a2

a3

a4

a5

a6

a7

а8

K{as}

0001

0010

0011

0100

0101

0110

0111

1000

0000

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

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

Исходное состояние

Код  am

Состояние перехода  as

Код  as

Входной сигнал X(am,as)

Выходные сигналы Y(am,as)

Функции возбуждения счётчиков

a0

0001

a0

a1

0001

0010

~X1

X1

-

y0y3y5

-

+1

a1

0010

a2

a8

0011

0000

~X5

X5

y7y5

-

+1

R

a2

0011

a2

a3

0011

0100

~X1

X1

-

y3

-

+1

a3

0100

a4

a4

a8

0101

0101

0000

~X5~X4

~X5X4

X5

y6

-

y6

+1

+1

R

a4

0101

a5

a5

0110

0110

~X2

X2

-

y7y5

+1

+1

a5

0110

a6

a6

0111

0111

X3

~X3

y5

-

+1

+1

a6

0111

a7

1000

1

y1

+1

a7

1000

a6

a6

a8

0111

0111

0000

~X6~X3

~X6X3

X6

-

y5

-

-1

-1

R

a8

0000

a0

a8

0001

0000

X7

~X7

y9

-

+1

-

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

+1 = a0x1 V a1~x5 V a2x1 V a3~x5~x4 V a3~x5x4 V a4~x2 V a4x2 V a5x3 V a5~x3 V a6 V a8x7

- 1 = a7~x6x3 V a7~x6~x3

R =a1x5 V a3x5 V a7x6

y0 = a0x1

y1 = a6

y3 = a0x1 V a2x1

y5 = a0x1 V a1~x5 V a4x2 V a5x3 V a7~x6x3

y6 = a3~x5~x4 V a3x5

y7 = a1~x5 V a4x2

y9= a8x7

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

l = a3~x5        (2)         r = a0x1       (2)    

m = a8x7        (2)         i = a7~x6     (2)

o = a2x1         (2)         n = a4x2       (2)    

t = ix3            (2)         d = l~x4        (2)

j =a3x5           (2)         p = a1~x5     (2)

                                                                                                                               

+1 = r V p V o V l V a4 V a5 V a6 V m      (8)

- 1 = i    (0)

R = a1x5 V j V a7x6        (7)

y0 = r          (0)

y1 = a6        (0)

y3 = r V o    (2)

y5 = r V p V n V a5x3 V t    (7)

y6 = d  V j     (2)

y7 = p V n        (2)

y9 = m          (0)

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

Полная цена по Квайну: С = 51(КС)+8(ЭП)+4(DC)+4(b)=67.

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

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

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

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

Граф автомата по модели Мура представлен в приложении Д.

8.2. Кодирование состояний на D-триггерах

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

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

Таблица 12.

bs

b0

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

b11

{bm}

b0, b11

b0

b1

b2,

b3

b3,

b2

b4

b4

b4, b6

b9, b6, b7

b6,

b7,

b8,

b9

b5,

b9,

b10,

b1

b10

K(b)

1000

1010

1100

0011

0101

1001

0111

0100

0010

0000

0001

0110

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

Исходное состояние

Код

bm

Состояние перехода  bs

Код

bs

Входной сигнал

Выходные сигналы

Функции возбуждения D-триггеров

b0

1000

b0

b1

1000

1010

~x1

x1

-

D3

D3D1

b1

1010

b2

b10

1100

0001

~x5

x5

y0y3y5

D3D2

D0

b2

1100

b3

b4

0011

0101

~x1

x1

y7y5

D1D0

D2D0

b3

0011

b3

b4

0011

0101

~x1

x1

-

D1D0

D2D0

b4

0101

b5

b6

b7

1001

0111

0100

x5

~x5~x4

~x5x4x2

y3

D3D0

D2D1D0

D2

b5

1001

b10

0001

~x7

y6

D0

b6

0111

b7

b8

b9

0100

0010

0000

x2

~x2x3

~x2~x3

y6

D2

D1

-

b7

0100

b8

b9

0010

0000

x3

~x3

y7y5

D1

-

b8

0010

b9

0000

1

y5

-

b9

0000

b8

b9

b10

0010

0000

0001

~x6x3

~x6~x3

x6

y1

D1

-

D0

b10

0001

b10

b11

0001

0110

~x7

x7

-

D0

D2D1

b11

0110

b0

1000

1

y9

D3

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

D-триггеров

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

D0 = b1x5 V b2~x1 V b2x1 V b3~x1 V b3x1 V b4x5 V b4~x5~x4 V b5~x7 V b9x6 V b10~x7

D1 = b0x1 V b2~x1 V b3~x1 V b4~x5~x4 V b6~x2x3 V b7x3 V b9~x6x3 V b10x7

D2 = b1~x5 V b2x1 V b3x1 V b4~x5~x4 V b4~x5x4x2 V b6x2 V b10x7

D3 = b0~x1V b0x1 V b1~x5 V b4x5 V b11

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

y0 = b1

y1 = b9

y3 = b1 V b4

y5 = b1 V b2 V b7 V b8

y6 = b5 V b6

y7 = b2 V b7

y9 = b11

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

с = b0x1                 (2)          f  = b6x2       (2)    

d = b4~x5~x4        (3)           i = b4x5        (2)

e = b4~x5x4x2      (4)           g = b1~x5       (2)

p = b10x7                (2)   

D0 = b1x5 V b2 V b3 V i V d V b5~x7 V b9x6 V b10~x7      (16)

D1 = c V b2~x1 V b3~x1 V d V b6~x2x3 V b7x3 V b9~x6x3 V p       (20)

D2 = g V b2x1 V b3x1 V d V e  V f  V p                          (11)

D3 = b0~x1 V c V g V b4x5 V b11                                                       (9)

y0 = b1                              (0)

y1 = b9                              (0)

y3 = b1 V b4   (2)

y5 = b1 V b2 V b7 V b8    (4)

y6 = b5 V b6   (2)

y7 = b2 V b7   (2)

y9 = b11   (0)

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

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

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

8.4. Кодирование состояний на RS-триггерах

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

                    2) g=2

                     B2={1}        С1={0011,0101,1001}     W0011=1

                                       D2={0011,0101,1001}     W0101=1               

                                                                              W1001=1   

                                     Выбираем любой:  K(b2)=0011

                   3) g=10

                      B10={1}        С1={0101,1001}      W0101=1

                                          D10={0101,1001}       W1001=1

                                         Выбираем любой:   K(b10)=0101

                  

  4) g=3

                        В3 ={2}        С2={0010,0111,1011}       W0010=1

                                          D3={0010,0111,1011}       W0111=1

        W1011=1

                                         Выбираем любой:   K(b3)=0010

 5) g=4

                       B4={2,3}                                                                                                     

                                 C2={0111,1011}                        W0111=3

      C3={0110,1010}                        W1011=3

                                 D4={0111,1011,0110,1010}      W0110=3

                                                                                W1010=3                                                                 

                                Выбираем любой:   K(b4)=0110

            

                  6) g=5

                   B5={4,10}    C4={0111,0100,1110}           W0111=1 

                                      C10={0100,0111,1101}          W0111=1 

                                         D5={0111,0100,1110,1101}  W0100=1

                                                                                 W1110=1

                               Выбираем любой:   K(b5)=0111                   

        7)   g=6

             B6={4}      C4={0100,1110}   W0100=1

                               D6={0100,1110}   W1110=1

                             

                                                               

                             Выбираем любой:        K(b6)=1110

     8)   g=7

                          B7={4,6}      C4={0100 }                     W0100=3

                                              C6={1111,1100,1010}             W1111 =3           

                                              D7={0100,1111,1100,1010}   W1100=3

                                         W1010=3

                   Выбираем любой:     K(b7)=1111           

  9)   g=8

                     B8={6,7}    C6={1100, 1010}                  W1100=3

                                        C7={1101,1011}                         W1010=3              

                                              D8={1100,1010,1101,1011}      W1101=3

            W1011=3

                                        Выбираем: K(b8)=1100

 10)   g=9

       B9={6,7,8,10}          C6={1010}                      W1010=9

                                         C7={1101, 1011}          W1101=5          

                                         C8={1101,1000,0100}       W1011=9

                                         C10={0100,1101}               W1000=9

                                         D9={1010,1101,1011,1000,0100}   W0100=7

                                           Выбираем: K(b9)=1101

   

  11)  g=11

       B11={0, 10}                       C0={0100, 1000}      W0100=2

                                                  C10={0100}               W1000=4

                                                  D11={0000,1000}       

                                           Выбираем: K(b11)=0100

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

                                                           

                                                        Таблица  15.

B

b0

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

b11

K(b)

0000

0001

0011

0010

0110

0111

1110

1111

1100

1101

0101

0100

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

RS-триггеров

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

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

Исходное состояние bm

Выходные сигналы

Код

bm

Состояние перехода  bs

Код

bs

Входной сигнал

Функции возбуждения RS-триггеров

b0

-

0000

b0

b1

0000

0001

~X1

X1

-

S0

b1

y0y3y5

0001

b2

b10

0011

0101

~X5

X5

S1

S2

b2

y7y5

0011

b3

b4

0010

0110

~X1

X1

R0

b3

-

0010

b3

b4

0010

0110

~X1

X1

-

S2

b4

y3

0110

b5

b6

b7

0111

1110

1111

X5

~X5~X4

~X5X4X2

S0

S3

S3S0

b5

y6

0111

b10

0101

~X7

R1

b6

y6

1110

b7

b8

b9

1111

1100

1101

X2

~X2X3

~X2~X3

S0

R1

R1S0

b7

y7,y5

1111

b8

b9

1100

1101

X3

~X3

R1R0

R1

b8

y5

1100

b9

1101

1

S0

b9

y1

1101

b8

b9

b10

1100

1101

0101

~X6X3

~X6~X3

X6

R0

-

R3

b10

-

0101

b10

b11

0101

0100

~X7

X7

-

R0

b11

y9

0100

b0

0000

1

R2

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

R0 = b2~x1 V b2x1 V b7x3 V b9~x6x3 V b10x7

R1 = b5~x7 V b6~x2x3 V b6~x2~x3 V b7x3 V b7~x3

R2 = b11

R3 = b9x6

S0 = b0x1 V b4x5 V b4~x5x4x2 V b6x2 V b6~x2~x3 V b8

S1 = b1~x5

S2 = b1x5 V b2x1 V b3x1

S3 = b4~x5~x4 V b4~x5x4x2

y0 = b1

y1 = b9

y3 = b1 V b4

y5 = b1 V b2 V b7 V b8

y6 = b5 V b6

y7 = b2 V b7

y9 = b11

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

с = b7x3                (2)              

 d = b6~x2~x3        (3)          

 e = b4~x5x4x2      (4)              

R0 = b2  V c V b9~x6x3 V b10x7       (8)

R1 = b5~x7 V b6~x2x3 V d V b7        (8)

R2 = b11     (1)

R3 = b9x6     (2)

S0 = b0x1 V b4x5 V e V b6x2 V d V b8      (12)

S1 = b1~x5          (2)

S2 = b3x1             (2)

S3 = b4~x5~x4 V e           (4)

y0 = b1                              (0)

y1 = b9                              (0)

y3 = b1 V b4   (2)

y5 = b1 V b2 V b7 V b8    (4)

y6 = b5 V b6   (2)

y7 = b2 V b7   (2)

y9 = b11   (0)

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

Полная цена по Квайну: С = 64(КС)+12(ЭП)+4(НУ)+4(b) = 84

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

9. Построение функциональной схемы микропрограммного

управляющего автомата

Сравнивая построения автомата на основе модели Мура и Мили, видно, что построение автомата по модели Мили требует меньше аппаратурных затрат, чем построение автомата по модели Мура.

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

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

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

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

Список использованных сокращений:

ДК – дополнительный код

ФЗ – фиксированная запятая

УА – управляющий автомат

ОА – операционный автомат

МО – микрооперация

ЛУ – логическое условие

ГСА – граф-схема алгоритма

МК – микрокоманда

ЭП – элемент памяти

КС – комбинационная схема

~ – знак инверсии (инвертируется то, перед чем стоит этот знак)


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

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

В.Ю. Мельцов.  Синтез микропрограммных управляющих автоматов. Учебное пособие. Киров, 2000.

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


 

А также другие работы, которые могут Вас заинтересовать

44950. Однокристальные микроконтроллеры серии PIC 231 KB
  Микроконтроллеры семейств PIC (Peripheral Interface Controller) компании Microchip, обладающие особой популярностью, построены на основе передовых технологий микроконтроллеров. Им свойственны следующие особенности: электрически программируемые пользователем ППЗУ, минимальное энергопотребление, высокая производительность, хорошо развитая RISC-архитектура
44952. Автоколебательный мультивибратор 33.87 KB
  Проанализируем нашу программу, реализующую функцию автоколебательного мультивибратора, с одним выходом. Форма сигнала меандр (скважность, т.е. отношение периода к длительности импульса – 2). Под этот выход можно назначить любой из выводов порта А или В...
44953. Устройство формирования сигнала тонального вызова 87.52 KB
  Полупериоды формируем используя €œзакольцовку рабочей точки программы в подпрограммах задержки по аналогии с программой Multi. К моменту начала составления текста программы желательно определиться с как можно большим количеством исходных данных. Так как программа должна исполняться непрерывно то в случае нахождения устройства в режиме ожидания включения на передачу рабочая точка программы должна €œзакольцеваться€ до последующего нажатия на кнопку в какой-нибудь подпрограмме. Часто такого рода закольцовки осуществляют в...
44954. Сканирование с прерыванием 110.21 KB
  Определимся с терминологией применяемой при описании программы работы устройства. Для удобства объяснения и восприятия целесообразно разделить рабочую часть программы на две части. Условимся называть группу команд в которой осуществляется сканирование каналов на наличие сигнала прерывания “основным телом†программы а часть которая отрабатывается после ухода в прерывание как подпрограмму прерывания. Следовательно речь идет о необходимости “ухода†рабочей точки программы на время наличия сигнала прерывания в подпрограмму...
44956. Индивидуальные и общественные потребности 35 KB
  Индивидуальные и общественные потребности Общество состоит из индивидов имеющих свои биологические особенности – состояние здоровья особенности физиологических процессов в организме различия в строении и функционировании нервной системы которые определяют природные задатки человека. В простейшем случае общественные потребности представляют собой просто сумму потребностей индивидуальных. В более сложных случаях общественные потребности выходят за пределы индивидуальных и не сводятся к их сумме. Томас Гоббс считал что государство необходимо...
44957. Потребности в общении, самореализации, собственности и статусе. Смысл богатства 35.5 KB
  Любой человек будет испытывать дискомфорт когда блокирована его потребность в Познании например когда долгое время нет доступа к новой информации.Потребность в общении Человек испытывает потребность поделиться е другими своими мыслями и чувствами читать газеты книги и журналы смотреть кинофильмы в спектакли слушать музыку и т. Следует особо выделить такую духовную потребность как потребность в общении с другими людьми. Возникшая на заре человеческого общества потребность в общении породившая язык как средство общения была наряду с...
44958. Природа и сущность человека и его потребностей 30.5 KB
  Природа и сущность человека и его потребностей. Понятия природа сущность человека часто употребляются как синонимы. В марксистской системе рассуждения понятие природы соотносилось обычно с биологическим естеством человека в то время как сущность человека усматривалась в его социальности в его общественной природе. В принципе под природой человека подразумеваются стойкие неизменные черты общие задатки и свойства выражающие его особенности как живого существа которые присущи хомо сапиенс во все времена независимо от биологической эволюции...