.

Синтез микропрограммного управляющего автомата

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 1749
Скачать документ

Министерство общего и профессионального образования РФ

Вятский государственный технический университет

Факультет автоматики и вычислительной техники

Кафедра электронных вычислительных машин

ДОПУСКАЮ К ЗАЩИТЕ

Руководитель работы _______ О.А. Залетов

СИНТЕЗ МИКРОПРОГРАММНОГО

УПРАВЛЯЮЩЕГО АВТОМАТА

Пояснительная записка

курсовой работы

по теории автоматов

ТПЖА.220100.22.29 ПЗ

Разработал студент гр. ВМ-22 ( _______ ) Р.В. Гонта

Проверил преподаватель кафедры ЭВМ ( _______ ) О.А. Залетов

Нормоконтролер ( _______ ) В.Ю. Мельцов

Председатель комиссии ( _______ ) В.Д. Матвеев

Члены комиссии ( _______ ) В.Ю. Мельцов

Работа защищена с оценкой ( _______ )

1999

Содержание

Введение

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

2 Описание используемого алгоритма умножения

2.1 Алгоритм умножения чисел в форме с ПЗ с простой коррекцией

2.2 Алгоритм умножения первым способом

3 Ручной подсчет

4 Выбор и описание структурной схемы ОА

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

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

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

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

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

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

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

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

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

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

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

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

7.10 Получение уравнений для счетчика

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

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

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

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

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

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

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

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

Заключение

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

Перечень сокращений

УДК 681.3

Реферат

Гонта Р.В. Синтез микропрограммного управляющего автомата. Курсовая
работа / ВятГТУ, каф. ЭВМ, рук. О.А. Залетов – Киров, 1999. Гр. ч. 3 л.
ф. А2

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

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

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

Введение

Потребность в вычислениях возникла у людей на самых ранних стадиях
развития человеческого общества. Причем с самого начала для облегчения
счета люди использовали различные приспособления. Многие из них были
весьма интересными и остроумными по принципу действия, но все они
обязательно требовали, чтобы в процессе вычислений активно участвовал
человек-оператор. Качественно новый этап развития вычислительной
техники наступил с изобретением и созданием электронных
вычислительных машин, которые работают автоматически, без участия
человека, в соответствии с заранее заданной программой. Появление таких
машин вызвано объективными условиями современного развития науки,
техники и народного хозяйства. Во многих областях человеческой
деятельности уже в середине ХХ века объем и сложность
вычислительных работ настолько возросли, что решение некоторых задач
без применения вычислительной техники было бы практически не
возможным. В настоящее время электронные вычислительные машины
применяются во многих областях науки, техники и народного хозяйства. В
основном они используются: для решения сложных математических и
инженерных задач, в качестве управляющих машин в промышленности и
военной технике, в сфере обработки информации.

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

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

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

2 Описание используемого алгоритма умножения

Процесс умножения состоит из последовательности операций сложения и
сдвигов.

2.1 Алгоритм умножения чисел в форме с ПЗ с простой коррекцией

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

Перемножить модули мантисс сомножителей по правилам с ФЗ:

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

Правила введения коррекции при умножении чисел в ДК:

Если сомножители положительны, коррекции нет.

Если один из сомножителей отрицателен, к псевдопроизведению надо
прибавить ДК от модуля положительного сомножителя.

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

2.2. Перемножить модули сомножителей, представленных в ДК, одним из
четырех способов получить псевдопроизведение.

Определить характеристику произведения алгебраическим сложением
характеристик сомножителей.

Нормализовать мантиссу результата и выполнить округление если
необходимо.

2.2 Алгоритм умножения первым способом

Умножение с младших разрядов множителя со сдвигом частных сумм вправо.

В каждом такте цикла умножения первым способом необходимо:

Сложить множимое с предыдущей частной суммой, если очередной разряд
множителя равен 1, и результат (новую частную сумму) запомнить; в
случае если очередной разряд множителя равен 0 суммирование не
выполнять;

Уменьшить вдвое частную сумму, что равносильно сдвигу ее на один
разряд вправо.

3 Ручной подсчет

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

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

3.1 Сомножители положительные (A>0, B>0)

A = 9 = 10012, Апк = 0,1001, Адк = 0,1001

B = 13= 11012, Впк = 0,1101, Вдк = 0,1101

Определим знак произведения: 0 + 0 = 0

Перемножим модули сомножителей:

Таблица 1

Множимое Множитель Сумматор Пояснения

0,1101 0,1001 0,00000000

0,11010000

0,11010000 Сложение

0,01101000 Сдвиг

0,0100 0,00110100 Сдвиг

0,0010 0,00011010 Сдвиг

0,0001 0,00011010

0,11010000

0,11101010 Сложение

0,01110101 Сдвиг

Получили псевдопроизведение: 0,01110101

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

3.1.4 Присвоение произведению знака:

(A*B)дк=0,01110101

(A*B)пк=0,01110101

A*B = (9)*(13) = 117 = 11101012

3.2 Сомножители разных знаков (А0)

A =-9=-10012, Апк = 1,1001, Адк = 1,0111

B =13= 11012, Впк = 0,1101, Вдк = 0,1101

Определим знак произведения: 1 + 0 = 1

Перемножим модули сомножителей:

Таблица 2

Множимое Множитель Сумматор Пояснения

0,1101 0,0111 0,00000000

0,11010000

0,11010000 Сложение

0,01101000 Сдвиг

0,0011 0,01101000

0,11010000

1,00111000 Сложение

0,10011100 Сдвиг

0,0001 0,10011100

0,11010000

1,01101100 Сложение

0,10110110 Сдвиг

0,0000 0,01011011 Сдвиг

Получили псевдопроизведение: 0,01011011

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

0,01011011

Вдк= 0,00110000

0,10001011

3.2.4 Присвоение произведению знака:

(A*B)дк=1,10001011

(A*B)пк=1,01110101

A*B = (-9)*(13) = -117 = -11101012

3.3 Сомножители разных знаков (А>0, B4 Выбор и описание структурной схемы операционного автомата (ОА)ОА должен содержать:регистры RG1, RG2 для приема мантисс операндов с ШИВх;регистр RG3 и счетчик CT1 для приема характеристик с ШИВх;регистр RG4 для записи и хранения результата и частных сумм;комбинационные сумматоры SM;счетчик CT2 для подсчета тактов умножения;три сумматора по модулю 2 для получения обратного кода множимого и определения ПРС;триггер T1 для хранения знака результата;схему конъюнкции;триггер T2 для фиксации ПРС;усилитель-формирователь для выдачи результата на ШИВых.Операнды поступают в операционный автомат по 32-разрядной шине ШИВх. Перед началом умножения необходимо обнулить регистр частных сумм RG4, так как именно с него поступает информация на плечо A в SM, в счетчик CT2 необходимо занести “001001”, а триггер T1 сбросить. Операнды поступают в дополнительном коде. Сначала мантисса множителя записывается в RG1 и RG2, а его характеристика в RG3 и CT1. Мантисса первого операнда преобразуется в ДК с помощью схемы сложения по модулю 2 и сумматора и заносится в RG4. Затем записываются мантисса и характеристика множимого в RG2 и CT1 соответственно. После анализа знаков операндов произведем коррекцию, если это необходимо. Если знаковый разряд множимого (p2) равен 0, то обнуляем RG4. Если знаковый разряд множителя (p1) равен 1, то в RG4 заносим информацию с плеча S сумматора. После проведения коррекции начинается процесс получения псевдопроизведения. В процессе умножения происходят сдвиги регистров RG1 и RG4, а также увеличение счетчика CT2. Кроме того производится анализ младшего разряда RG1 (p4). Если он равен 1 тогда в RG4 заносим информацию с плеча S сумматора. Получение псевдопроизведения происходит до тех пор пока 5-й разряд в счетчике CT2 не окажется равным “1”. Далее производится анализ старшего разряда мантиссы результата. Если он равен “0” – требуется нормализация. Нормализация осуществляется путем сдвига RG4 влево и уменьшеня счетчика CT1. Характеристика произведения получается обычным сложением характеристик операндов, причем старший разряд характеристики у множителя подается инверсным на плечо сумматора A. Перед выдачей результата на ШИВых содержимое RG3, T1 и информация с плеча S сумматора SM2 подается на усилитель-формирователь.Таким образом, для выполнения операции умножения из управляющего автомата в операционный автомат необходимо подать управляющие сигналы, реализующие следующие микрооперации:y1 - запись в RG1,запись в RG3,сброс T1,занесение “001001” в CT2;y2 - запись в RG2,запись в CT1,разрешить запись в T1;y3 - обнуление RG4;y4 - запись в RG4;y5 - CT2:=CT2+1,сдвинуть вправо RG1:=0.R1(RG1),сдвинуть вправо RG4:=0.R1(RG4);y6 - SMp=1 – подача “1” на вход переноса сумматора,управление совокупностью схем сложения по модулю 2;y7 - CT1:=CT1-1,сдвиг влево RG4:=L1(RG4).0;y8 - управление выдачей на ШИВых;Из операционного автомата в управляющий автомат необходимо передать осведомительные сигналы о состоянии устройств операционного автомата, определяемые списком следующих логических условий.Х - проверка наличия операндов на ШИВх,p1 - знак операнда в RG1;p2 - знак операнда в RG2;p3 - проверка на наличие нулевого операнда в RG2;p4 - проверка очередной цифры множителя;p5 - проверка условия выхода из цикла;p6 - проверка результата на нормализованность;p7 - проверка условия ПРС;Z - проверка возможности выдачи по ШИВых.Таким образом, управляющий МПА должен вырабатывать 8 управляющих сигналов и посылать их в ОА в нужные такты машинного времени в соответствии с алгоритмом выполнения операции сложения, ориентируясь на 9 осведомительных сигналов, поступающих из ОА, структурная схема которой представлена на рисунке 1.5 Реализация содержательной ГСАСодержательная граф-схема алгоритма представлена на рисунке 2. Выполнение алгоритма начинается с проверки наличия операндов на ШИВх (блоки 1 и 5). При поступлении первого операнда происходит его занесение в RG1, RG2, RG3 и CT1, а также обнуление RG4, занесение “001001” в CT2 и сброс триггеров T1 и T2 (блок 2). Затем в регистр RG4 поступает ДК от первого операнда (блок 4). При поступлении второго операнда происходит его занесение в RG2 и CT1 (блок 6). После каждого занесения производится анализ p3. Если хотя бы в одном случае p3=1 (блоки 3 и 7), значит операнд равен нулю и значит необходимо обнулить RG4, RG3, CT1, T1 (блок 19) и перейти к блоку 20. В противном случае продолжается процесс коррекции. Если p2=0 (блок 8) тогда обнуляется регистр RG4 (блок 9). Если p1=1 (блок 10) тогда получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 11).Далее получается псевдопроизведение. Если p4=0 (блок 12), тогда получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 13). В любом случае выполняется блок сдвигов (блок 14): содержимое RG1 и RG4 сдвигаются вправо, CT2 увеличивается на “1“. Далее проверяется p5 (блок 15) - условие выхода из цикла. Если p5=1, цикл завершается, иначе переход к блоку 12.Затем производится нормализация. Если p6=0 (блок 16), то выполняется блок сдвигов (блок 18): содержимое RG4 сдвигается влево, CT2 уменьшается на “1“.При сложении характеристик одинакового знака возможно переполнение разрядной сетки (ПРС). Если p7=1 (блок 17), возникло ПРС и операция умножения завершается.Затем результат при Z=1 (блок 21) будет передан по ШИВых (блок 22) в другие устройства.6 Построение отмеченной ГСАПеред разметкой содержательной ГСА поставим возле каждой операторной вершины управляющие сигналы УА и обеспечивающие выполнение требуемых действий в соответствии со списком МО операционного автомата. Совокупность МО для каждой операторной вершины образуют микрокоманды (МК), список которых приведен в таблице 5. Таблица 5MK Совокупность МОY1 y1,y2,y3Y2 y2Y3 y3Y4 y4Y5 y5Y6 y4,y6Y7 y7Y8 y8Y9 y1,y3Каждой условной вершине содержательной ГСА поставим в соответствие один из входных сигналов управляющего автомата X1, … ,X9, список которых дан в таблице 6. Таблица 6Входной сигнал УА X1 X2 X3 X4 X5 X6 X7 X8 X9Логическое условие ОА X p3 p2 p1 p4 p5 p6 p7 ZДалее в полном соответствии с содержательной ГСА строим отмеченную ГСА (рисунок 3), условным вершинам которой приписывается один из входных сигналов УА (x1,...,x9), а операторным вершинам - одна из МК (в скобках указана совокупность МО для каждой МК). Выделение состояний управляющего МПА возможно в соответствии с моделью Мили или моделью Мура.На рисунке 3 приведена разметка ГСА для модели Мили символами a0,а1,...,а9 и для модели Мура - символами b0,b1,...,b12. Таким образам, если строить управляющий МПА в соответствии с моделью Мили, то он будет иметь 10 состояний, а в соответствии с моделью Мура - 13 состояний.Замечание. В двух вершинах ожидания (5 и 20) при разметке по Муру введены фиктивные состояния автомата b3 и b10.Явно большее число состояний для модели Мура по сравнению с моделью Мили не дает достаточных оснований для выбора модели Мили как более предпочтительной. Сравнение вариантов можно будет выполним лишь на этапе построения функциональных схем УА, сравнив схемы по сложности и быстродействию. Поэтому далее будем вести проектирование УА параллельно для модели Мили и для модели Мура.7 Синтез МПА в соответствии с моделью Мили7.1 Построение графа автоматаНа основе отмеченной ГСА построен граф автомата Мили (рисунок 4). Граф автомата Мили имеет 10 вершин, соответствующих состояниям автомата а0, а1,...,а9, дуги его отмечены входными сигналами, действующими на каждом переходе (числитель), и набором выходных сигналов, вырабатываемых УА на данном переходе (знаменатель).Из приведенного рисунка видно, что с увеличением количества состояний автомата наглядность графа теряется и больше удобств представляет табличный способ задания автомата.7.2 Построение структурной таблицы переходов и выходовТаблица 7. Прямая структурная таблица переходов и выходов автомата Мили.Исходное состояниеКод am Состояние перехода asКод as Входной сигнал X(am,as) Выходные сигналы Y(am,as) ФункциивозбужденияD-триггеровa0 0001 a0a1 00010011 X1X1 -Y1(y1,y2,y3) D4D3D4a1 0011 a2a9 00100000 X2X2 Y6(y4,y6)Y9(y1,y3) D3a2 0010 a2a3 00100110 X1X1 -Y2(y2) D3D2D3a3 0110 a4a4a9 110011000000 X2X3X2X3X2 -Y3(y3)Y9(y1,y3) D1D2D1D2a4 1100 a5a5 01000100 X4X4 -Y6(y4,y6) D2D2a5 0100 a6a6 01010101 X5X5 -Y4(y4) D2D4D2D4a6 0101 a7 1001 1 Y5(y5) D1D4a7 1001 a5a8 01001000 X6X6 -- D2D1a8 1000 a0a8a9 000110000000 X7X8X7X7X8 -Y7(y7)- D4D1a9 0000 a0a9 00010000 X9X9 -Y8(y8) D47.3 Кодирование на D-триггерахПри кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремится использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 10 состояний (a0 ,…, a10) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце as таблицы 7, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу 8, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы. Таблица 8As a0 a1 a2 a3 a4 a5 a6 a7 a8 a9{am} A0a8a9 a0 a1a2 a2 a3 a4a7 a5 a6 a7a8 a1a3a8a9Наибольшее количество переходов в состояние a9 - закодируем его кодом К(a9)=0000. Состояниям a0, a2, a5, a8 назначим коды с одной "1": K(a0) =0001, К(a2) =0010, К(a5)=0100, К(a8)=1000. Для кодирования других состояний будем использовать слова с двумя "1" в кодовом слове, К(a1)=0011, К(a3)=0110, К(a4)=1100, К(a6)=0101, К(a7)=1001, стараясь, насколько возможно, использовать соседние с as коды для состояний, находящихся в одном столбце таблицы 7.Кодирования для D-триггеров изображены в таблице 9.Таблица 9As a0 a1 a2 a3 a4 a5 a6 a7 a8 A9K{as} 0001 0011 0010 0110 1100 0100 0101 1001 1000 0000Далее коды состояний заносим в соответствующие столбцы прямой таблицы переходов (таблица 7) и формируем логические выражения для функций возбуждения.7.4 Получение логических выражений для функций возбуждения D-триггеровЛогические выражения для каждой функции возбуждения D-триггера получают по таблице как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.D1= a3x2va6va7x6va8x7D2= a2x1va3x2va4va5va7x6D3= a0x1va1x2va2D4= a0va5va6va8x7x8va9x9Аналогично составляются логические выражения для функций выходов.y1= a0x1va1x2va3x2y2= a0x1va2x1y3= a0x1va1x2va3x2x3va3x2y4= a1x2va4x4va5x5y5= a6y6= a1x2va4x4y7= a8x7y8=a9x9После выделения общих частей в логических выражениях и некоторого их упрощения получаем логические уравнения для построения функциональной схемы управляющего автомата.m=a1x2va4x4n=a0x1k=nva1x2va3x2p=a8x7q=a2x1r=a3x2D1= r v y5 v a7x6 v y7D2= q v r v a4 v a5 v a7x6D3= n v y6 v a2D4= a0 v a5 v y5 v a8x7x8 v a9x9Аналогично упрощаем логические выражения для функций выходов.y1= ky2= n v qy3= k v rx3y4= m v a5x5y5= a6y6= my7= py8=a9x9Цена комбинационной схемы по Квайну для автомата Мили, с использованием в качестве элементов памяти D-триггеров, равна С=59, причем в схеме предполагается использовать 4-входовой дешифратор.7.5 Кодирование на RS- триггерахОднако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Но при использовании RS-триггеров придется перекодировать состояния автомата, кодирование осуществим способом минимизирующим число переключений элементов памяти.Для этого сначала выпишем матрицу M - матрицу всех возможных переходов автомата. Состояниям автомата a0 и a1 присвоим коды: К(a0)=0000, К(a1)=0001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C1 коды с кодовым расстоянием "1" от кодов В2. Закодировав состояние a2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния a3 аналогично a2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами Вi и Di. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.00 k0=000001 k1=00011219 12 B2 ={0001}22 M2= 22 C1={0011,0101,1001}M= 23 23 D2={0011,0101,1001}34 W0011=139 W0101=145 W1001=156 k2=001167788088899923 B3={0011}M3= 34 C2={0010,0111,1011}39 D3={0010,0111,1011}W0010=1W0111=1W1011=1k3=001034 B4={0 010}M4= 45 C3={0110,1010}D4={0110,1010}W0110=1W1010=1k4=011045 B5={0110}M5= 56 C4={0100,0111,1110}75 D5={0100,0111,1110}W0100=1W0111=1W1110=1k5=011156 B6={0111}M6= 67 C5={0101,1111)}D6={0101,1111)}W0101=1W1111=1k6=010167 B7={0111,0101}M7= 75 C5={1111}78 C6={0100,1101}D7={1111,0100,1101}W1111=(1111-0111(2+(1111-0101(2=1+2=3W0100=(0100-0111(2+(0100-0101(2=2+1=3W1101=(1101-0111(2+(1101-0101(2=2+1=3k7=010078 B8={0000,0100}M8= 80 C0={1000}88 C7={1100}89 D8={1000,1100}W1100=(1100-0000(2+(1100-0100(2=2+1=3W1000=(1000-0000(2+(1000-0100(2=1+2=3k8=010019 B9={0000,0001,0010,1100}39 C0={1000}M9= 89 C1={1001} C3={1010}90 C8={1000,1101,1110}99 D9={1000,1001,1010,1101,1110}D\B 0000 0001 0010 1100 W1000 1 2 2 1 61001 2?????????????????????????????????‰?Кодирования для RS-триггеров изображены в таблице 10.Таблица 10As a0 a1 a2 a3 a4 a5 a6 a7 a8 a9K{as} 0000 0001 0011 0010 0110 0111 0101 0100 1100 10007.6 Получение логических выражений для функций возбуждения RS-триггеровДалее составляем прямую структурную таблицу переходов и выходов автомата Мили и по известному правилу формируем логические выражения для функций возбуждения.Таблица 11. Прямая структурная таблица переходов и выходов автомата Мили.Исходное состояниеКод am Состояние перехода asКод as Входной сигнал X(am,as) Выходные сигналы Y(am,as) Функции возбуждения триггеровRS Ta0 0000 a0a1 00000001 X1X1 -Y1(y1,y2,y3)S4T4a1 0001 a2a9 00111000 X2X2 Y6(y4,y6)Y9(y1,y3) S3S1R4 T3T1T4a2 0011 a2a3 00110010 X1X1 -Y2(y2)R4T4a3 0010 a4a4a9 011001101000 X2X3X2X3X2 -Y3(y3)Y9(y1,y3) S2S2S1R3 T2T2T1T3a4 0110 a5a5 01110111 X4X4 -Y6(y4,y6) S4S4 T4T4a5 0111 a6a6 01010101 X5X5 -Y4(y4) R3R3 T3T3a6 0101 a7 0100 1 Y5(y5) R4 T4a7 0100 a5a8 01111100 X6X6 -- R3R4S1 T3T4T1a8 1100 a0a8a9 000011001000 X7X8X7X7X8 -Y7(y7)- R1R2R2 T1T2T2a9 1000 a0a9 00001000 X9X9 -Y8(y8) R1 T1Так как мы изменили используемые элементы памяти, то у нас изменятся логические выражения для функций их возбуждения, а логические выражения для функций выходов не изменятся.S1= a1x2 v a3x2 v a7x6S2= a3x2S3= a1x2S4= a0x1 v a4R1= a8x7x8 v a9x9R2= a8x7R3= a3x2 v a5 v a7x6R4= a1x2 v a2x1 v a6 v a7x6После упрощения и выделения общих частей, получим:f= a1x2g= a3x2k= a7x6m= a8x7p= a3x2q= a1x2r= a0x1h= a2x1e= r v a1x2 v gn= q v a4x4S1= f v g v a7x6S2= pS3= qS4= r v a4R1= mx8 v a9x9R2= mR3= g v a5 v kR4= f v h v a6 v ky1= ey2= r v hy3= e v px3y4= n v a5x5y5= a6y6= ny7= a8x7y8=a9x9С использованием в качестве элементов памяти RS-триггеров, цена комбинационной схемы по Квайну для автомата Мили равна C=59 причем в схеме предполагается использовать 4-входовой дешифратор.7.7 Кодирование на T-триггерахВ качестве элементов памяти возможно использование не только D-триггеров и RS-триггеров, а также используются T-триггеры. При использовании T-триггеров используется такая же кодировка, как и для RS-триггеров. Кодирования для T-триггеров изображены в таблице 10.7.8 Получение логических выражений для функций возбуждения T-триггеровДалее составляем прямую структурную таблицу переходов и выходов автомата Мили (таблица 11) и по известному правилу формируем логические выражения для функций возбуждения.Так как мы изменили используемые элементы памяти, то у нас изменятся логические выражения для функций их возбуждения, а логические выражения для функций выходов не изменятся.T1= a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9T2= a3x2 v a8x7T3= a1x2 v a3x2 v a5 v a7x6T4= a0x1 v a4 v a1x2 v a2x1 v a6 v a7x6После упрощения и выделения общих частей, получим:f= a1x2g= a3x2k= a7x6m= a8x7p= a3x2q= a1x2r= a0x1h= a2x1e= r v a1x2 v gn= q v a4x4i= r v hT1= f v g v a7x6 v mx8 v a9x9T2= p v mT3= q v g v a5 v kT4= i v a4 v f v a6 v ky1= ey2= iy3= e v px3y4= n v a5x5y5= a6y6= ny7= a8x7y8=a9x9С использованием в качестве элементов памяти T-триггеров, цена комбинационной схемы по Квайну для автомата Мили равна C=61 причем в схеме предполагается использовать 4-входовой дешифратор.7.9 Кодирование на счетчикеДля кодирования состояний автомата на счётчике необходимо, чтобы разность кодов между соседними состояниями составляла единицу. Данная кодировка представлена в таблице 12.Таблица 12As a0 a1 a2 a3 a4 a5 a6 a7 a8 a9K{as} 0000 0001 0010 0011 0100 0101 0110 0111 1000 10017.10 Получение уравнений для счетчикаСоставляем прямую структурную таблицу переходов и выходов автомата Мили и по известному правилу формируем логические выражения для функций возбуждения.Таблица 13. Прямая структурная таблица переходов и выходов автомата Мили.Исходное состояниеКод am Состояние перехода asКод as Входной сигнал X(am,as) Выходные сигналы Y(am,as) Функции возбужденияa0 0000 a0a1 00000001 X1X1 -Y1(y1,y2,y3)E+1a1 0001 a2a9 00101001 X2X2 Y6(y4,y6)Y9(y1,y3) E+1D1D8 Ma2 0010 a2a3 00100011 X1X1 -Y2(y2)E+1a3 0011 a4a4a9 010001001001 X2X3X2X3X2 -Y3(y3)Y9(y1,y3) E+1E+1D1D8 Ma4 0100 a5a5 01010101 X4X4 -Y6(y4,y6) E+1E+1a5 0101 a6a6 01100110 X5X5 -Y4(y4) E+1E+1a6 0110 a7 0111 1 Y5(y5) E+1a7 0111 a5a8 01011000 X6X6 -- D1D4 ME+1a8 1000 a0a8a9 000010001001 X7X8X7X7X8 -Y7(y7)- ME+1a9 1001 a0a9 00001001 X9X9 -Y8(y8) MM – вход управления записью / счётом в счётчике;E+1 - вход управления прямым счётом;Работа счётчика производится в соответствии с таблицей 14.Таблица 14М E+1 Режим0111 0100 Запись в счётчикПрямой счётОбратный счётХранениеИз таблицы 13 получаются логические выражения для каждой функции возбуждения управляющего входа счётчика, а также для функций выходов как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.M = a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9E+1 = a0x1 v a1x2 v a2x1 v a3x2 v a4 v a5 v a6 v a7x6 v a8x7x8D1 = a1x2 v a3x2 v a7x6D4 = a7x6D8 = a1x2 v a3x2y1 = a0x1 v a1x2 v a3x2y2 = a0x1 v a2x1y3 = a0x1 v a1x2 v a3x2x3 v a3x2y4 = a1x2 v a4x4 v a5x5y5 = a6y6 = a1x2 v a4x4y7 = a8x7y8 =a9x9После выделения общих частей в логических выражениях и некоторого их упрощения получаются логические уравнения для построения функциональной схемы управляющего автомата.e=a1 v a3 d=x1(a0 v a2) f=a0x1h=x2e g=a1x2 v a4x4 p=a8x7r=f v h q=a7x6 n=h v qM = n v px8 v a9x9E+1 = d v x2e v a4 v a5 v a6 v a7x6 v px8D1 = nD4 = qD8 = hy1 = ry2 = dy3 = r v a3x2x3y4 = g v a5x5y5 = a6y6 = gy7 = a8x7y8 =a9x9Цена комбинационной схемы по Квайну составляет С=57.Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=10), а n наименьшее число ЭП (n=log2 16).Сравнивая относительно аппаратурных затрат варианты построения автомата Мили на RS, D, T- триггерах и на счетчике можно убедиться что цена логических выражений для функций возбуждения оказывается приблизительно равной: для RS цена - 59, для D цена – 59, для T цена 61, а для счетчика 57.8 Синтез МПА в соответствии с моделью Мура8.1 Построение графа автомата.На основе отмеченной ГСА построен граф автомата Мура (рисунок 5).Граф автомата Мура имеет 11 вершин, соответствующих состояниям автомата b0,b1,...,b10, каждое из которых определяет наборы выходных сигналов, управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.8.2 Построение структурной таблицы переходов.Из приведенного рисунка видно, что с увеличением количества состояний автомата наглядность графа теряется и больше удобств представляет табличный способ задания автомата.Таблица 15. Прямая структурная таблица переходов и выходов автомата Мура.Исходное состояние bm Выходные сигналы Кодbm Состояние перехода bs Кодbs Входной сигнал Функции возбуждения D-триггеровb0 -0001 b0b1 00010111 X1X1 D4D2D3D4b1 y1,y2,y30111 b2b12 11100011 X2X2 D1D2D3D3D4b2 y4,y61110 b3b4 10100110 X1X1 D1D3D2D3b3 -1010 b3b4 10100110 X1X1 D1D3D2D3b4 y20110 b5b6b7b8b12 11000101001000000011 X2X3X2X3X4X2X3X4X5X2X3X4X5X2 D1D2D2D4D3D3D4b5 y31100 b6b7b8 010100100000 X4X4X5X4X5 D2D4D3b6 y4,y60101 b7b8 00100000 X5X5 D3b7 y4 0010 b8 0000 1b8 y50000 b0b7b8b9b10b11 000100100000100101001000 X6X7X8X6X5X6X5X6X7X6X7X8X9X6X7X8X9 D4D3D1D4D2D1b9 y71001 b0b9b10b11 0001100101001000 X7X8X7X7X8X9X7X8X9 D4D1D4D2D1b10 -0100 b10b11 01001000 X9X9 D2D1b11 y8 1000 b0 0001 1 D4b12 y1,y30011 b10b11 01001000 X9X9 D2D18.3 Кодирование на D-триггерахВ таблице 15 представлена прямая структурная таблица переходов и выходов автомата Мура. Так как каждому состоянию автомата Мура соответствует свой набор выходных сигналов, то столбец выходных сигналов в таблице помещен следом за столбцом исходных состояний автомата. Проанализируем синтез автомата Мура на D-триггерах.При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремиться использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 13 состояний (b0, b1, ... , b12) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце bs таблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы. Таблица 16bs b0 b1 b2 b3 b4 b5 b6 B7{bm} b0b8b9b11 b0 b1 b2b3 b2b3 b4 b4b5 b4b5b6b8bs b8 b9 b10 b11 b12{bm} b4b5b6b7b8 b8b9 b8b9b10b12 b8b9b10b12 b1b4Коды состояний автомата определим по выше описанному методу кодирования состояний при использовании D-триггеров.Таблица 17b b0 b1 b2 b3 b4 b5 b6K(b) 0001 0111 1110 1010 0110 1100 0101b b7 b8 b9 b10 b11 b12K(b) 0010 0000 1001 0100 1000 00118.4 Получение логических выражений для функций возбуждения D-триггеров и функций выходов.Далее коды состояний заносим в соответствующие столбцы прямой таблицы переходов (таблица 15) и по известному правилу формируем логические выражения для функций возбуждения.D1= b1x2 v b2x1 v b3x1 v b4x2 v b8x6x7 v b8x6x7x8x9 v b9x7 v b10x9 v b12x9D2= b0x1 v b1x2 v b2x1 v b3x1 v b4x2(x3 v x3x4) v b5x4 v b8x6x7x8x9 v b9x7x8x9 v b10x9 vv b12x9D3= b0x1 v b1 v b2 v b3 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b8x6x4D4= 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 b12y2= b1 v b4y3= b1 v b5 v b12y4= b2 v b6 v b7y5= b8y6= b2 v b6y7= b9y8=b11Выделив общие части получаем:d=b2 v b6g=b0x1h=b1x2i=b4x2j=x4x5k=b4x2x3m=b8x6n=x7x8r=b2 v b3q=mvb9D1= h v x1r v k v m(x7 v nx9) v b9x7 v b10x9 v b12x9D2= 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 b11y4= d v b7y6= 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 и Di. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.00 k0=00000112 k1=00011 1223 12 B2 ={0001}24 M2= 23 C1={0011,0101,1001}M= 33 24 D2={0011,0101,1001}34 W0011=145 W0101=146 W1001=147 k2=0011484 12 23 B3={0011}56 M3= 33 C2={0010,0111,1011}57 34 D3={0010,0111,1011}58 W0111=167 W0010=168 W1011=178 k3=00108087 24 B4={0011,0010}88 34 C2={0111,1011} C3={0110,1010}89 45 D4={0111,1011, 0110,1010}8 10 M4= 46 W0111=38 11 47 W1011=390 48 W0110=399 4 12 W1010=39 10 k4=01109 1110 10 45 B5={0110}10 11 M5= 56 C4={0100,0111,1110}11 0 57 D5={0100,0111,1110}12 10 58 W0100=112 11 W0111=1W1110=1k5=010046 B6={0110,0100}M6= 56 C4={0111,1110}67 C5={0101,1100}68 D6={0111,1110,0101,1100}D\B 0110 0100 W0111 1 2 31110 1 2 30101 2 1 31100 2 1 3k6=010147 B7={0110,0100,0101}57 C4={0111,1110}M7= 67 C5={1100}78 C6={0111,1101}87 D7={0111,1110,1100,1101}D\B 0110 0100 0101 W0111 1 2 1 41110 1 2 3 61100 2 1 2 51101 3 2 1 6k7=011180 B8={0000,0110,0100,0101,0111}48 C0={1000}58 C4={1110}68 C5={1100}M8= 78 C6={1101}87 C7={1111}88 D8={0000,1110,1100,1101,1111}898 108 11D\B 0000 0110 0100 0101 0111 W1000 1 3 2 3 4 131110 3 1 2 3 2 111100 2 2 1 2 3 101101 3 3 2 1 2 111111 4 2 3 2 1 12k8=110090 B9={0000,1100}89 C0={1000}M9= 99 C8={1000,1101,1110}9 10 D9={1000,1101,1110}9 11 k9=10008 10 B10={1100,1000}9 10 C8={1101,1110}M10= 10 10 C9={1001,1010}10 11 D10={1101,1110,1001,1010}12 10D\B 1100 1000 W1101 1 2 31110 1 2 31001 2 1 31010 2 1 3k10=111011 0 B11={0000,1100,1000,1110}8 11 C0={1001,1010} C8={1101}M11= 9 11 C9={1001,1010}10 11 C10={1010}12 11 D11={1001,1010,1101}D\B 0000 1100 1000 1110 W1001 2 2 1 3 81010 2 2 1 1 61101 3 1 2 2 8k11=10101 12 B12={0001,0110,1110,1010}M12= 4 12 C1={1001} C4={1111}12 10 C10={1111}12 11 C11={1011}D12={1001,1111,1011}D\B 0001 0110 1110 1010 W1001 1 4 3 2 101111 3 2 1 2 81011 2 3 2 1 8k12=1011Кодирования для RS-триггеров изображены в таблице 18.Таблица 18b b0 b1 b2 b3 b4 b5 b6K(b) 0000 0001 0011 0010 0110 0100 0101b b7 b8 b9 b10 b11 b12K(b) 0111 1100 1000 1110 1010 10118.6 Получение логических выражений для функций возбуждения RS-триггеров.Далее составляем прямую структурную таблицу переходов и выходов автомата Мура (таблица 19) и по известному правилу формируем логические выражения для функций возбуждения.Таблица 19. Прямая структурная таблица переходов и выходов автомата Мура.Исходное состояние bm Выходные сигналы Кодbm Состояние перехода bs КодBs Входной сигнал Функции возбуждения D-триггеровb0 -0000 b0b1 00000001 X1X1S4b1 y1,y2,y30001 b2b12 00111011 X2X2 S3S1S3b2 y4,y60011 b3b4 00100110 X1X1 R4S2R4b3 -0010 b3b4 00100110 X1X1S2b4 y20110 b5b6b7b8b12 01000101011111001011 X2X3X2X3X4X2X3X4X5X2X3X4X5X2 R3R3S4S4S1R3S1R2S4b5 y30100 b6b7b8 010101111100 X4X4X5X4X5 S4S3S4S1b6 y4,y60101 b7b8 01111100 X5X5 S3S1R4b7 y4 0111 b8 1100 1 S1R3R4b8 y51100 b0b7b8b9b10b11 000001111100100011101010 X6X7X8X6X5X6X5X6X7X6X7X8X9X6X7X8X9 R1R2R1S3S4R2S3R2S3b9 y71000 b0b9b10b11 0000100011101010 X7X8X7X7X8X9X7X8X9 R1S2S3S3b10 -1110 b10b11 11101010 X9X9R2b11 y8 1010 b0 0000 1 R1R3b12 y1,y31011 b10b11 11101010 X9X9 R2S4R4Так как мы изменили используемые элементы памяти, то у нас изменятся логические выражения для функций их возбуждения, а логические выражения для функций выходов не изменятся.S1= b1x2 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b7S2= b2x1 v b3x1 v b9x7x8x9 v b12x9S3=b1 v b5x4x5 v b6x5 v b8x6x5 v b8x6x7x8 v b9x7x8S4= b0x1 v b4x2x3x4 v b4x2x3x4x5 v b4x2 v b5x4 v b5x4x5 v b8x6x5R1= b8x6x7x8 v b8x6x5 v b9x7x8 v b11R2= b4x2 v b8x6x7x8 ??????????‹??????????????????????????????????????Упростив и выделив общие части получаем:d=b4x2q=b4x2e=qx3r=x4x5f=b5rg=b6x5s=b8x6m=x7x8h=smi=b8x6x5j=b8x6x7x8k=b9x7x8n=x4x5p=b2 v b7S1= b1x2 v en v d v b5n v g v b7S2= x1(b2 v b3) v x9(k v b12)S3= b1 v f v b6x5 v i v j v kS4= b0x1 v e(x4 v r) v d v b5x4R1= h v i v b9m v b11R2= d v h v sx7 v x9(j v b10)R3= qx3 v e(x4 v n) v b7 v b11R4= g v p v b12y1= b1 v b12y2= b1 v b4y3= b1 v b5 v b12y4= p v b6y5= b8y6= b2 v b6y7= b9y8=b11С использованием в качестве элементов памяти RS-триггеров, цена комбинационной схемы по Квайну для автомата Мура равна С =114 причем в схеме предполагается использовать 4-входовой дешифратор.Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=13), а n наименьшее число ЭП (n=log2 16).Способ кодирование для счетчика так же не может быть использован, так как в данном графе содержится большое количество нестандартных переходов.Сравнивая относительно аппаратурных затрат варианты построения автомата Мура на RS и D-триггерах можно убедиться что цена логических выражений для функций возбуждения ЭП отличается не на много: для RS цена - 114, для D цена - 109.Сравнение вариантов построения управляющего автомата по модели Мили и модели Мура показывает, что модель Мура дает комбинационную схему большей сложности. Однако следует обратить внимание на то, что комбинационная схема, реализующая функции выходов автомата Мура, чрезвычайно проста (ее цена для схемы использующей D-триггеры, С=11).9 Построение функциональной схемы микропрограммного управляющего автоматаСравнивая построения автомата на основе модели Мура и Мили, видно, что построение автомата по модели Мили требует меньше аппаратурных затрат, чем построение автомата по модели Мура. Модель Мили на D-триггерах имеет цену по Квайну 59, на RS-триггерах цена также составляет 59, на T-триггерах цена составляет 61, а на счётчике цена составляет 57.Наиболее оптимальной по аппаратурным затратам и стоимости является модель Мили на счётчике, поэтому функциональная схема МПА будет строиться именно для этой модели.На рисунке 6 приведена функциональная схема проектируемого МПА, управляющего операцией умножения двоичных чисел с ПЗ в ДК с простой коррекцией. Функциональная схема построена в основном логическом базисе И, ИЛИ, НЕ в полном соответствии с приведенной для модели Мили системой логических уравнений для функций возбуждения элементов памяти.ЗаключениеВ ходе выполнения курсовой работы была разработана функциональная схема МПА, управляющего операцией умножения двоичных чисел в форме с плавающей запятой и характеристикой в дополнительном коде первым способом с простой коррекцией.При синтезе МПА была рассмотрена модель Мили и модель Мура. В результате проделанной работы оказалось, что наименьшие аппаратурные затраты даёт модель Мили с использованием счётчика в качестве элементов памяти.Библиографический списокКурс лекций по дисциплине “Дискретная математика”.Т.Р.Фадеева. Синтез Микропрограммного управляющего автомата. Методические указания к курсовой работе. Киров, 1989 год.Б.М.Каган. Электронные вычислительные машины и системы. М.: Энергоатомиздат, 1985.Курс лекций по дисциплине “Теория автоматов”.Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Минск: ВМ, 1980.Перечень сокращенийГСА - граф-схема алгоритма,УА - управляющий автомат,ОА - операционный автомат,ПРС - переполнение разрядной сетки,ФЗ - фиксированная запятая,ДК - дополнительный код,МПА - микропрограммный аппарат,МК - микрокоманда,МО - микрооперация.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2019