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

 

Введение


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

Применение моделей в Теории автоматов не ограничивается какой-либо частной областью, а возможно для решения проблем практически в любой области исследования.

Предлагаемая курсовая работа является продолжением в цепочке курсовых работ и проектов по специальности 22.01. Основной целью данной курсовой работы является получение навыков синтеза микропрограммного управляющего автомата с жесткой логикой. Далее в курсе Схемотехника будет предложено разработать операционный автомат для одной или группы арифметических операций. Дальнейшее развитие курсовой проект получит в дисциплине Теория и проектирование ЦВМ.

Сравнительная оценка алгоритма

Длительность процесса умножения при любом алгоритме составляет n шагов


Tу = ntШ


где n - количество значащих цифр в каждом сомножителе;

tш - длительность одного шага умножения.

Один шаг умножения в общем случае состоит из двух микроопераций: сложения и сдвига кодов, имеющих длительность tсл и tсд соответственно. Однако длительность шагов неодинакова в различных алгоритмах. Так, в нашем случае tш =tсл, так как в этом алгоритме можно совместить во времени такты сдвига и сложения частичных произведений. Действительно, добавление очередного частичного произведения к накапливаемой сумме практически сводиться к передаче цифр из регистра множимого в сумматор, в котором затем образуются цифры новой суммы. Формирование следующего частичного произведения (сдвиг) сводиться к передаче этих же цифр в соседние старшие разряды в регистре множимого. Таким образом, нет никаких препятствий для объединения этих двух процессов. Но поскольку в машинах всегда tсл > tсд, то это приводит к следующему соотношению:

У = ntсл


Выигрыш в быстродействии при применении данного алгоритма умножения зависит от соотношения длительности тактов сложения и сдвигов. Если приять это соотношение равным tсл = (3 - 5) tсд, или для определенности tсл = 4tсд, то сравнительный выигрыш в быстродействии равен Eб = (DtШ/5tСД)*100% = 20%, однако аппаратурные затраты больше, чем при использовании других методов (примерно на 40%).

Таким образом, если при проектировании машины основное внимание обращается на её быстродействие, то лучшим выбором является второй способ умножения.


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


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



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


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


2.1Умножение чисел вторым способом


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


2.2Алгоритм умножения чисел в дополнительном коде с простой коррекцией


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

2.Перемножить модули сомножителей, представленных в дополнительном коде - получим псевдопроизведение.

.Выполнить коррекцию псевдопроизведения.

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

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

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

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


2.3Умножение чисел с плавающей запятой


Числа с ПЗ в ЭВМ представляются так, как представлено на рисунке 1.


10111001010011100100101110110110Рисунок 1 - Представление чисел с ПЗ


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

При умножении чисел с ПЗ в порядках может возникнуть ПРС.

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


2.4Численный пример


А=-22

В=19


-22100101010101900010110011

? множитель? множимое Сумма ЧПкомментарий0,100110,00000010100,0000000000сложение0,00000010100,00000010100,010010,00000101000,0000001010сложение0,00000101000,00000111100,001000,00001010000,0000011110сдвиги0,000010,00101000000,0000011110сложение0,00101000000,00101111100.000000,01010000000,0010111110

Сложение порядков в МДК 00,00101

,00101

,01010

,0010111110 - псевдопроизведение

,01101 +Вдк

,1001011110

(A*B)дк = 1,1001011110 (M=210)

Проверка (A*B)ПК = 1,0110100010

A*B=-110100010(2) = -418


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

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

  • 24х разрядный сдвиговый регистр RG1 для приема и хранения множителя;
  • 47и разрядный сдвиговый регистр RG2 для приема и хранения множимого;
  • 47и разрядный сдвиговый регистр RG3 для записи и хранения частных сумм результата;
  • 8и разрядный регистр RG4 для приема и хранения порядков;
  • 46и разрядный сумматор SM1 для сложения частных сумм и множимого;
  • 9и разрядный сумматор SM2 для сложения порядков;
  • вычитающий 9и разрядный счетчик СТ1 для хранения порядков и работы с ними;
  • суммирующий 6и разрядный счетчик СТ2 для управления умножением;
  • совокупность 7 схем сложения по модулю два для получения инверсии содержимого регистра RG4;
  • совокупность 7 схем сложения по модулю два для получения инверсии содержимого счетчика СТ1;
  • RS-триггер для хранения признака ПРС;
  • схема сложения по модулю два для определения ПРС
  • схема сложения по модулю два для определения знака результата
  • схема сложения по модулю два для определения необходимости нормализации мантиссы
  • 23х разрядный элемент И для определения равенства сомножителей нулю;
  • мультиплексор MS для передачи информации на плечо B сумматора SM1;
  • усилитель-формирователь для выдачи результата на выходную шину.

Операнды разрядностью 4 байта поступают по входной шине в операционный автомат. Запись мантиссы множителя производится в регистр RG1, а также RG2 (в младшие разряды, в старшие заносятся 0) для анализа ее на ноль. Запись мантиссы множимого осуществляется только в RG2. Если один из сомножителей равен нулю, то производится выдача нуля на выходную шину. Порядки сомножителей записываются в RG4. Результат суммирования порядков находится в счетчике СТ1. В RG3 заносятся частные суммы. Перед выполнением умножения, если это необходимо, производится коррекция. После выполнения умножения по мере необходимости, производится нормализация полученного числа и, если нет ПРС, выдача его на выходную шину через усилитель-формирователь.

Для организации работы всего автомата необходимо из УА подать в ОА управляющие сигналы, реализующие следующие МО:


y0 - сброс RG3, Т1 и CT1, занесение мантиссы в RG1, СТ2:=001001;

y1 - занесение мантиссы в RG2 и порядка в RG4;

y2 - управление мультиплексором и подача единицы на вход CRP сумматора SM1;

y3 - занесение в RG3;

y4 - управление совокупностью схем сложения по модулю два (для перевода порядка в ДК);

y5 - подача единицы на вход CRP сумматора SM2 (для перевода порядка в ДК);

y6 - занесение в СТ1;

y7 - сдвиг RG3 на 23 разряда влево (после коррекции) и запись в старший разряд RG3 знака результата;

y8 - сдвиг RG1 вправо, RG2 влево, CT2:=CT2+1;

y9 - сдвиг RG3 влево, CT1:=CT1-1;

y10 - Т1:=1 - установка триггера ПРС;

y11 - сброс RG4 и управление совокупностью схем сложения по модулю два (для перевода результирующего порядка в ДК);

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


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


X - проверка наличия операндов на входной шине;

р1 - если р1=1, то сомножитель равен нулю;

р2 - знак множимого;

р3 - знак порядка в RG4;

р4 - знак множителя в RG1;

р5 - p5=1 - ПРС;

р6 - знак результата сложения порядков;

р7 -анализируемый разряд множителя;

р8 - р8=1 - условие завершения умножения;

р9 - отсутствует - необходимо нормализовать RG3;

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


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



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


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

Выполнение алгоритма начинается с проверки наличия операндов на ШИВх (блоки 1 и 4). При поступлении первого операнда происходит занесение его мантиссы в RG1 и младшие разряды RG2 (в старшие разряда заносятся 0), его порядка в RG4, а также обнуление RG3, занесение 01001 в CT2 и сброс триггера T1 и счетчика СТ1(блок 2). Затем производится анализ знака множимого (блок 5): если р2=1, то формируется и заносится в RG3 ДК от мантиссы множителя (блок 6), - анализ знака порядка в RG4 (блок 7): если р3=1, то в СТ1 заносится ДК от порядка, если нет - то ПК, - и занесение мантиссы множимого в младшие разряды RG2 (в старшие разряда заносятся 0), порядка множимого в RG4(блоки 8 и 9). Затем производится анализ знака множителя (блок 11): если р4=1, то формируется и заносится в RG3 ДК от мантиссы множимого (блок 12). После занесения каждого из сомножителей производится анализ p1. Если хотя бы в одном случае p1=1 (блоки 3 и 10), значит операнд равен нулю и необходимо перейти к блоку 26.

Затем производится анализ знака порядка множимого в RG4 (блок 13): если р3=1, то к содержимому СТ1 прибавляется ДК от порядка в RG4, если нет - то ПК, - а также сдвиг RG3 влево на 23 разряда и занесение в его старший разряд знака результата (блоки 14 и 15). Производится проверка на ПРС (блок 16): если р5=1, то возникло ПРС и триггер Т1 необходимо установить в «1» подачей сигнала у10 (блок17).

Затем производится анализ младшего разряда множителя (блок 18):

  • если P7 - логическая единица, то выполняется суммирование частной суммы и множимого (блок 19);
  • если P7 - отсутствует, то никаких действий над частной суммой не производится.

После этого выполняются сдвиги регистров RG1 (вправо) и RG2 (влево) и увеличение счетчика СТ2 (блок 20), а затем проверка на окончание цикла умножения (блок 21): если р8=1, то цикл завершается, иначе переход к блоку 18. Далее идет проверка на необходимость нормализации полученного числа (блок 22): если р9=0, то необходимо нормализовать мантиссу результата, сдвинув влево RG3 и уменьшив СТ1 на 1 (блок 23) и перейти к блоку 24. Затем производится анализ знака получившегося порядка (блок 24): если р6=1, то необходимо сформировать ДК от содержимого счетчика СТ1. Затем после проверки возможности выдачи результата на ШИВых (блок 26) при z=1 производится выдача результата на ШИВых (блок 27).



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


Отмеченная граф-схема алгоритма представлена в Приложении В.

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

Каждой условной вершине содержательной граф схемы алгоритма ставится в соответствие один из входных сигналов управляющего автомата Х1…Хn, список которых приведен в таблице 2.


Таблица 1.

КСовокупность МОУ1у0, y1У2y2, y3У3y1, y4, y5, y6У4y1, y6У5y4, y5, y6, y7У6y6, y7У7y10У8y3У9y8У10 У11 У12y9 y5, y6, y11 y12

Таблица 2.

Входной сигнал УАX1X2X3X4X5X6X7X8X9X10X11Логическое условие ОАXP1P2P3P4P5P7P8P9P6Z

В приложении В приведена разметка граф схемы алгоритма для модели Мили символами а0…а9 и для модели Мура символами b0…b15. Для модели Мура введены два фиктивных состояния b2 и b14, реализующие режим ожидания.

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



6.Построение графов автомата для модели Мили и Мура


На основе отмеченной граф схемы алгоритма построены граф автомата Мили (Приложения Г) и граф автомата Мура (Приложение Д).

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

Граф автомата Мура имеет 16 вершин, соответствующих состояниям автомата b0…b15, каждое из которых определяет наборы выходных сигналов у1,у2…у13 управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.



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


Рассмотрим предложенные варианты структурной схемы управляющего автомата:

1.Классическая структура УА.

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

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

3.Структура УА на основе сдвигового регистра.

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

4.Структура на основе счетчика.

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

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

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

Для кодировки состояний модели Мура требуется 4 разряда (16 состояний), то есть при реализации структурной схемы потребуется дешифратор на 4 входа; для кодировки состояний модели Мили требуется 4 разряда (10 состояний), то есть потребуется дешифратор на 4 входа.


8.Кодирование внутренних состояний автомата Мили


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

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

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

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


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


Таблица 3. Кодирование состояний автомата Мили на 4 D-триггерах.

Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00010a0 a10010 0110~x1 x1- У0, y1D3 D2D3a10110a2 a2 a90100 0100 0000~x2x1x3 ~x2x1~x3 x2y2, y3 - -D2 D2 -a20100a3 a31100 1100x4 ~x4y1, y4, y5, y6 Y1, y6D1D2 D1D2a31100a4 a4 a91010 1010 0000~x2x5 ~x2~x5 x2y2, y3 - -D1D3 D1D3 -a41010a5 a50011 0011x4 ~x4y4, y5, y6, y7 Y6, y7D3D4 D3D4a50011a0 a6 a60010 0001 0001x6 ~x6x7 ~x6~x7y10 y3 -D3 D4 D4a60001a710011y8D1D4a71001a6 a6 a8 a80001 0001 1000 1000~x8x7 ~x8~x7 x8x9 x8~x9y3 - - y9D4 D4 D1 D1a81000a9 a90000 0000x10 ~x10y5, y6,y11 -- -a90000a0 a90010 0000x11 ~x11y12 -D3 -

Cоставляется инверсная таблицу переходов, и состояния автомата кодируются четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц. Инверсная таблица переходов для модели Мили представлена в таблице 4.


Таблица 4

aSа0a1a2a3a4а5a6A7a8a9ama0 a5 a9a0a1a2a3а4a5 a7A6a7a8 a9 a3 a1Коды0010011001001100101000110001100110000000

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

(a0) = 0010, К(a6) = 0001


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

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


D1=a2 v a3~x2 v a6 v a7x8=a0x1 v a1~x2x1 v a2=a0 v a3~x2 v a4 v a5x6 v a9x11=a4 v a5~x6 v a6 v a7~x8


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


y0=a0x1=a0x1 v a2=a1~x2x1x3 v a3~x2x5=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7=a2x4 v a4x4=a2x4 v a4x4 v a8x10= a2 v a4 v a8x10=a4=a6=a7x8~x9=a5x6=a8x1012=a9x11

a8x9x12


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


D1=a2 v m v a6 v l=y0 v n v a2=a0 v m v a4 v y10 v y12=a4 v a6 v r

=a0x1=y0 v a2=nx3 v mx5=y2 v x7r= a2x4 v a4x4=y4 v y11= a2 v y5=a4=a6=l~x9=a5x6=a8x10=a9x11

= a3~x2= a7x8= a1~x2x1= a5~x6= a7~x8

r=q v p


Цена комбинационной схемы по Квайну для автомата Мили на 4 D-триггерах С =66.

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

Для кодировки состояний автомата на RS-триггерах воспользуемся эвристическим алгоритмом кодирования, который минимизирует суммарное число изменений элементов памяти на всех переходах автомата.


01). Кодируем первые два состояния : К(0) = 0000

1 К(1) = 0001

9 2) Выбираем следующее незакодированное состояние u = 9

2 1 9

3 3 9

4 M= 8 9

9 9 0

5 9 9

M= 5 0 Составляем список уже закодированных соседних состояний

6 B = {1,0}

7 Список соседних кодов для них

6C(0) = {1000,0100,0010}

8 C(1) = {1001,0101,0011}

9 D= {1001,0101,0011}

0Выбираем код с минимальной функцией W

9 9W(1000) = W(0100) = W(0010) =W(1001) = W(0101) = W(0011) = 3;K(9) = 0010


) u = 2= 1 2

3= {1}, D = {1001, 0101, 0011} K (2) = 0011

) u = 3

3= 3 4

9= {2; 9} C(2) = {0111, 1011}(9) = {0110,1010}= {0111,0110,1011,1010} K(3) = 0110

) u = 4= 3 4

5= {3} D = {0100,0111,1110} K(4) = 0100

) u =5

5= 5 0

6= {4,0}(0) = {1000}(4) = {1100, 0101}= {1000, 1100, 0101}K (5) = 1000

) u=6

6= 6 7

6={5} D={1100,1010,1001}K(6)=1100


) u=7

7= 7 6

8= {6} D = {1101,1110}K(7) = 1101

) u = 8= 7 8

9= {7,9}(7) = {1001,0101,1111}(9) = {1010}= {1001,0101,1111,1010}K(8) = 1010


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

Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00000a0 a10000 0001~x1 x1- у0, y1- S4a10001a2 a2 a90011 0011 0010~x2x1x3 ~x2x1~x3 x2y2, y3 - -S3 S3 S3, R4a20011a3 a30110 0110x4 ~x4y1, y4, y5, y6 y1, y6R4,S2 R4,S2a30110a4 a4 a90100 0100 0010~x2x5 ~x2~x5 x2y2, y3 - -R3 R3 R2a40100a5 a51000 1000x4 ~x4y4, y5, y6, y7 y6, y7R2,S1 R2,S1a51000a0 a6 a60000 1100 1100x6 ~x6x7 ~x6~x7y10 y3 -R1 S2 S2a61100a711011y8S4a71101a6 a6 a8 a81100 1100 1010 1010~x8x7 ~x8~x7 x8x9 x8~x9y3 - - y9R4 R4 R2,S3,R4 R2,S3,R4a81010a9 a90010 0010x10 ~x10y5, y6,y11 -R1 R1a90010a0 a90000 0010x11 ~x11y12 -R3 -

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


S1=a4=a2 v a5~x6=a1 v a7x8=a0x1 v a6=a5x6 v a8=a3x2 v a4 v a7x8=a3~x2 v a9x114=a1x2 v a2 v a7


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


y0=a0x1=a0x1 v a2=a1~x2x1x3 v a3~x2x5=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7=a2x4 v a4x4=a2x4 v a4x4 v a8x10= a2 v a4 v a8x10=a4=a6=a7x8~x9=a5x6=a8x1012=a9x11

a8x9x12


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

S1=a4=a2 v h=a1 v g=y0 v a6=y10 v a8=a3x2 v a4 v g=t v y12=a1x2 v a2 v a7


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


y0=a0x1=y0 v a2=a1~x2x1x3 v tx5=y2 v x7(h v a7~x8)=a2x4 v a4x4=y4 v y11= a2 v y5=a4=a6=g~x9=a5x6=a8x10=a9x11=a5~x6= a7x8= a3~x2


Цена комбинационной схемы по Квайну для автомата Мили на 4 RS-триггерах С =71.


.3 Кодирование состояний модели МИЛИ на счётчике


Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00000a0 a10000 0001~x1 x1- у0, y1- Inca10001a2 a2 a90010 0010 1001~x2x1x3 ~x2x1~x3 x2y2, y3 - -Inc Inc D1D4Sa20010a3 a30011 0011x4 ~x4y1, y4, y5, y6 y1, y6Inc Inca30011a4 a4 a90100 0100 1001~x2x5 ~x2~x5 x2y2, y3 - -Inc Inc D1D4Sa40100a5 a50101 0101x4 ~x4y4, y5, y6, y7 y6, y7Inc Inca50101a0 a6 a60000 0110 0110x6 ~x6x7 ~x6~x7y10 y3 -R Inc Inca60110a701111y8Inca70111a6 a6 a8 a80110 0110 1000 1000~x8x7 ~x8~x7 x8x9 x8~x9y3 - - y9D2D3S D2D3S Inc Inca81000a9 a91001 1001x10 ~x10y5, y6,y11 -Inc Inca91001a0 a90000 1001x11 ~x11y12 -R -

Inc= a0 x1 v a1~x2x1 v a2 v a3~x2v a4v a5~x6v a6 v a7 x8v a8= a1x2v a3x2 v a7~x8

R= a5x6 v a9x11= a1x2v a3x2= a7~x8= a7~x8= a1x2v a3x2

y0=a0x1=a0x1 v a2=a1~x2x1x3 v a3~x2x5=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7=a2x4 v a4x4=a2x4 v a4x4 v a8x10= a2 v a4 v a8x10=a4=a6=a7x8~x9=a5x6=a8x1012=a9x11


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


Inc= y0 v k v a2 v d v a4v t v a6 v m v a8= f v g

R= y10 v y12=f=g= g= f

=a0x1=y0 v a2=kx3 v dx5=y2 v p=x4(a2 v a4)=y4 v y11= a2 v y5=a4=a6=m~x9=a5x6=a8x10=a9x11

= a1~x2x1= x2(a1va3)= a7~x8= a3~x2= a5~x6= a7 x8= x7(t v g)


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



9. Кодирование состояний для модели Мура


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


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

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

Наибольшее количество переходов в состояние b15, b14, b11, b4, b5, b7. Закодируем K(b15)=0000, а оставшимся из них - кодами с одной "1": K(b14) = 0001, К(b11) = 0010, К(b4) = 0100, К(b5) = 1000. Для кодирования других состояний будем использовать слова с большим количеством "1" в кодовом слове, стараясь, насколько возможно, использовать соседние с bs коды для состояний, находящихся в одном столбце таблицы 5.

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

микропрограммный автомат алгоритм умножение число


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

Исходное состояние bmВыходные сигналыКод bmСостояние перехода bsКод bsВходной сигналФункции возбуждения триггеровb0-0110b11111x1D1D2D3D4b1y0y11111b2 b3 b4 b5 b14 b151101 0111 0100 1000 0001 0000~x2x1 ~x2x1x3 ~x2x1~x3x4 ~x2x1~x3~x4 x2~x11 x2x11D1D2D4 D2D3D4 D2 D1 D4 -b2-1101b2 b3 b4 b51101 0111 0100 1000~x1 x1x3 x1~x3x4 x1~x3~x4D1D2D4 D2D3D4 D2 D1b3y2y30111b4 b50100 1000x4 ~x4D2 D1b4y1y4y5y60100b6 b7 b8 b14 b150101 1100 1010 0001 0000~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11D2D4 D1D2 D1D3 D4 -b5y1y61000b6 b7 b8 b14 b150101 1100 1010 0001 0000~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11D2D4 D1D2 D1D3 D4 -b6y2y30101b7 b81100 1010x4 ~x4D1D2 D1D3b7y4y5y6y71100b9 b10 b111110 1001 0010x6 ~x6x7 ~x6~x7D1D2D3 D1D4 D3b8y6y71010b9 b10 b111110 1001 0010x6 ~x6x7 ~x6~x7D1D2D3 D1D4 D3b9y101110b001101D2D3b10Y31001b1100101D3b11Y80010b10 b11 b12 b13 b14 b151001 0010 1011 0011 0001 0000~x8x7 ~x8~x7 x8~x9 x8x9x10 x8x9~x10~x11 x8x9~x10x11D1D4 D3 D1D3D4 D3D4 D4 -b12Y91011b13 b14 b150011 0001 0000x10 ~x10~x11 ~x10x11D3D4 D4 -b13y5y6y110011b14 b150001 0000~x11 x11D4 -b14-0001b14 b150001 0000~x11 x11D4 -b15y120000b001101D2D3

D1= b0 x1 v b1~x2x1 v b1~x2x1~x3~x4 v b2~x1 v b2 x1~x3~x4 v b3~x4 v b4~x2~x5 v b5~x2~x5 v b6 v b7x6 v b7~x6x7 v b8x6 v b8~x6x7 v b11~x8x7 v b11 x8~x9


D2= b0 x1 v b1~x2x1 v b1~x2x1x3 v b1~x2x1~x3x4 v b2~x1 v b2 x1~x3x4 v b3 x4 v b4~x2x5

v b4~x2~x5x4 v b5~x2x5 v b5~x2~x5x4 v b6 x4 v b7 x6 v b8 x6 v b9 v b15


D3= b0 x1 v b1~x2x1x3 v b2 x1x3 v b4~x2~x5~x4 v b5~x2~x5~x4 v b6~x4 v b7 x6 v b8 x6

v b8~x6~x7 v b9 v b10 v b11~x8~x7 v b11 x8~x9 v b11 x8x9x10 v b12 x10 v b15


D4= b0 x1 v b1~x2x1 v b1~x2x1x3 v b1 x2~x11 v b2~x1 v b2 x1x3 v b4~x2x5 v b4 x2~x11 v b5~x2x5 v b5 x2~x11 v b7~x6x7 v b8~x6x7 v b11~x8x7 v b11 x8~x9 v b11 x8x9x10 v b11x8x9~x10~x11 v b12 x10 v b12~x10~x11 v b13~x11v b14~x11


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

y0=b1= b1 v b4 v b5= b3 v b6= b3 v b6 v b10= b4 v b7= b4 v b7 v b13= b4 v b5 v b7 v b8 v b13= b7 v b8=b11=b12=b911=b13

y12=b12


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


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


01). Кодируем первые два состояния : К(0) = 0000

1 К(1) = 0001

2 2) Выбираем следующее незакодированное состояние u = 2

3 1 2

4 2 2

5 M= 2 3

14 2 4

15 2 5

2 Составляем список уже закодированных соседних состояний

3 B = {1}

4Список всех соседних кодов для них

5D= {1001,0101,0011}

4Выбираем код с минимальной функцией W

5W=1K(2) = 0011

6 3) u = 3

7 1 3

8 M= 2 3

14 3 4

15 3 5

6 B = {1,2}, D = {1001,0101,0010,1011,0111}

7W = 3K(3) = 0010

8 4) u = 4

14 1 4

15 2 4

7 3 4

8 M= 4 6

9 4 7

10 4 8

11 4 14

9 4 15

10 B = {1, 2, 3} D = {1001, 0101, 1011, 0111, 1010, 0110}

11W = 5K(4) = 0111

0 5) u = 5

11 1 5

10 2 5

11 3 5

12 M= 5 6

13 5 7

14 5 8

15 5 14

13 5 15

14 B = {1,2,3} D = {1001,0101,1011,1010,0110}

15 W = 5 K(5) = 1011

14 6) u = 6

15 4 6

15 M= 5 6

0 6 7

8

B = {4,5} D = {1111,1001,1010,0101,0110}

W = 2 K(6) = 1111

) u = 7

7

7

M= 6 7

9

10

11

B = {4,5,6} D ={0101,0110,1001,1010,1110,1101}

W = 5K(7) = 1101

) u = 8

8

8

M= 6 8

9

10

11

B = {4,5,6} D = {0101,0110,1001,1010,1110}

W = 5K(8) = 1110

) u = 9

9

M= 8 9

0

B = {7,8,0} D = {1100,0101,1001,0110,1010,1000,0100}

W = 4K(9) = 1100

) u = 10

10

M= 8 10

11

10

B = {7, 8} D = {0101,1001,0110,1010}

W = 4K(10) = 0101

) u = 11

11

11

11

10

M= 11 11

12

13

14

15

B = {7,8,10} D = {1001,0110,1010,0100}

W = 6K(11) = 0100

) u =12

12

M= 12 13

14

15

B = {11} D = (0110)

W = 1K(12) = 0110

) u =13

13

M= 12 13

14

15

B = {11,12} D = {0}


Поэтому строим множество



где - множество кодов, у которых кодовое расстояние с уже закодированными кодами равно 2, т.е.


={1000,1010}

W = 5K(13) = 1000

) u =14

14

14

14

M= 11 14

14

14

15

B = {1,4,5,11,12,13} D = {1001,1010}

W = 13K(14) = 1001

15) u=15

K(15)=1010


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

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


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

Исходное состояние bmВыходные сигналыКод bmСостояние перехода bsКод bsВходной сигналФункции возбуждения триггеровb0-0000b10001x1S4b1y0y10001b2 b3 b4 b5 b14 b150011 0010 0111 1011 1001 1010~x2x1 ~x2x1x3 ~x2x1~x3x4 ~x2x1~x3~x4 x2~x11 x2x11S3 S3R4 S2S3 S1S3 S1 S1S3R4b2-0011b2 b3 b4 b50011 0010 0111 1011~x1 x1x3 x1~x3x4 x1~x3~x4- R4 S2 S1b3y2y30010b4 b50111 1011x4 ~x4S2S4 S1S4b4y1y4y5y60111b6 b7 b8 b14 b151111 1101 1110 1001 1010~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11S1 S1R3 S1R4 S1R2R3 S1R2R4b5y1y61011b6 b7 b8 b14 b151111 1101 1110 1001 1010~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11S2 S2R3 S2R4 R3 R4b6y2y31111b7 b81101 1110x4 ~x4R3 R4b7y4y5y6y71101b9 b10 b111100 0101 0100x6 ~x6x7 ~x6~x7R4 R1 R1R4b8y6y71110b9 b10 b1111000101 0100x6 ~x6x7 ~x6~x7R3 R1R3S4 R1R3b9y101100b000001S1S2b10y30101b1101001R4b11y80100b10 b11 b12 b13 b14 b150101 0100 0110 1000 1001 1010~x8x7 ~x8~x7 x8~x9 x8x9x10 x8x9~x10~x11 x8x9~x10x11S4 - S3 S1R2 S1R2S4 S1R2S3b12y90110b13 b14 b151000 1001 1010x10 ~x10~x11 ~x10x11S1R2R3 S1R2R3S4 S1R2b13y5y6y111000b14 b151001 1010~x11 x11S4 S3b14-1001b14 b151001 1010~x11 x11- S3R4b15y121010b000001R1R3

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

=b1(~x2x1~x3~x4 v x2) v b2 x1~x3~x4 v b3~x4 v b4 v b9 v b11x8x9 v b12

S2=b1~x2x1~x3x4 v b2 x1~x3x4 v b3 x4 v b5~x2 v b9

S3=b1(~x2x1v x2x11) v b11(x8~x9 v x8x9~x10x11) v b13 x11 v b14 x11=b0 x1 v b3 v b8~x6x7 v b11(~x8x7 v x8x9~x10~x11) v b12~x10~x11v b13~x11=b7~x6 v b8~x6 v b15=b4 x2 v b11 x8x9 v b12= b4(~x2~x5x4 v x2~x11)v b5(~x2~x5x4 v x2~x11)v b6 x4 v b8 v b12( x10 v ~x10~x11)=b1(~x2x1x3 v x2x11) v b2 x1x3 v b4(~x2~x5~x4 v x2x11) v b5(~x2~x5~x4 v x2x11) v b6~x4 v b7( x6 v ~x6~x7) v b10 v b14 x11

=b1= b1 v b4 v b5= b3 v b6= b3 v b6 v b10= b4 v b7= b4 v b7 v b13= b4 v b5 v b7 v b8 v b13= b7 v b8=b11=b12=b911=b13

y12=b12


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

=b1(~x2k v x2) v b2k v b3~x4 v b4 v b9 v p v b12=b1~x2t v b2t v b3 x4 v b5~x2 v b9

S3=b1(~x2x1v x2x11) v b11(x8~x9 v d) v b13 x11 v b14 x11=b0 x1 v b3 v b8~x6x7 v b11(~x8x7 v d) v b12~x10~x11v b13~x11=b7~x6 v b8~x6 v b15=b4 x2 v p v b12= r(b4v b5)v b6 x4 v b8 v b12( x10 v ~x10~x11)=qy1 v b2 x1x3 v b6~x4 v b7( x6 v ~x6~x7) v b10 v b14 x11=b1= b1 v b4 v b5= b3 v b6= b3 v b6 v b10= b4 v b7= b4 v b7 v b13= b4 v b5 v b7 v b8 v b13= b7 v b8=b11=b12=b9=b13=b12= x1~x3~x4= x1~x3x4=~x2x1x3 v x2x11=~x2~x5x4 v x2~x11= x8x9~x10x11

p= b11 x8x9


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



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


Функциональная схема управляющего МПА представлена в Приложении Ж.

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

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

Функциональная схема построена в основном логическом базисе И-ИЛИ-НЕ в полном соответствии с приведенной для модели Мили системой логических уравнений для функций возбуждения счетчика и функций выходов. В схему поступают сигналы синхронизации с и начальной установки b.



Заключение


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

При проектировании ЭВМ, можно поставить две различные задачи:

·повышение быстродействия устройства;

·уменьшение аппаратурных затрат.

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

Приложение А


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


Приложение Б.


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






Приложение В


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


Приложение Г


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



Приложение Е


Граф автомата модели МУРА


Приложение Ж


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



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

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ