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

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

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

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

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

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

Tу = nШ

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

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

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

TУ = nсл

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Умножение чисел с плавающей запятой Числа с ПЗ в ЭВМ представляются так, как представлено на рисунке 1.

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

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

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

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

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

А=-22

В=19

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

00,101

00,1 010

0,10 111 110 — псевдопроизведение

0,1 101 +Вдк

0,1 001 011 110

(A*B)дк = 1,1 001 011 110 (M=210)

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

A*B=-11 010 0010(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:=1 001;

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, занесение «1 001» в 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.

Таблица 2.

В приложении В приведена разметка граф схемы алгоритма для модели Мили символами а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-триггеров лучше использовать соседнее кодирование, так как именно этот способ минимизирует число переключений ЭП.

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

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

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

Таблица 4

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

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

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

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

D1=a2 v a3~x2 v a6 v a7x8

D2=a0x1 v a1~x2x1 v a2

D3=a0 v a3~x2 v a4 v a5x6 v a9x11

D4=a4 v a5~x6 v a6 v a7~x8

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

y0=a0x1

y1=a0x1 v a2

y2=a1~x2x1x3 v a3~x2x5

y3=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7

y4=a2x4 v a4x4

y5=a2x4 v a4x4 v a8x10

y6= a2 v a4 v a8x10

y7=a4

y8=a6

y9=a7x8~x9

y10=a5x6

y11=a8x10

y12=a9x11

a8x9x12

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

D1=a2 v m v a6 v l

D2=y0 v n v a2

D3=a0 v m v a4 v y10 v y12

D4=a4 v a6 v r

y0=a0x1

y1=y0 v a2

y2=nx3 v mx5

y3=y2 v x7r

y4= a2x4 v a4x4

y5=y4 v y11

y6= a2 v y5

y7=a4

y8=a6

y9=l~x9

y10=a5x6

y11=a8x10

y12=a9x11

m= a3~x2

l= a7x8

n= a1~x2x1

q= a5~x6

p= a7~x8

r=q v p

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

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

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

0 1 К (1) = 0001

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

1 2 1 9

2 3 3 9

3 4 M'= 8 9

3 9 9 0

4 5 9 9

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

5 6 B = {1,0}

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

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

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

8 9 D= {1001,0101,0011}

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

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

3) u = 2

M'= 1 2

2 3

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

4) u = 3

2 3

M'= 3 4

3 9

B = {2; 9} C (2) = {0111, 1011}

C (9) = {0110,1010}

D = {0111,0110,1011,1010} K (3) = 0110

5) u = 4

M'= 3 4

4 5

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

6) u =5

4 5

M'= 5 0

5 6

B = {4,0}

C (0) = {1000}

C (4) = {1100, 0101}

D = {1000, 1100, 0101} K (5) = 1000

7) u=6

5 6

M'= 6 7

7 6

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

8) u=7

6 7

M'= 7 6

7 8

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

9) u = 8

M'= 7 8

8 9

B= {7,9}

C (7) = {1001,0101,1111}

C (9) = {1010}

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

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

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

S1=a4

S2=a2 v a5~x6

S3=a1 v a7x8

S4=a0x1 v a6

R1=a5x6 v a8

R2=a3x2 v a4 v a7x8

R3=a3~x2 v a9x11

R4=a1x2 v a2 v a7

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

y0=a0x1

y1=a0x1 v a2

y2=a1~x2x1x3 v a3~x2x5

y3=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7

y4=a2x4 v a4x4

y5=a2x4 v a4x4 v a8x10

y6= a2 v a4 v a8x10

y7=a4

y8=a6

y9=a7x8~x9

y10=a5x6

y11=a8x10

y12=a9x11

a8x9x12

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

S1=a4

S2=a2 v h

S3=a1 v g

S4=y0 v a6

R1=y10 v a8

R2=a3x2 v a4 v g

R3=t v y12

R4=a1x2 v a2 v a7

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

y0=a0x1

y1=y0 v a2

y2=a1~x2x1x3 v tx5

y3=y2 v x7(h v a7~x8)

y4=a2x4 v a4x4

y5=y4 v y11

y6= a2 v y5

y7=a4

y8=a6

y9=g~x9

y10=a5x6

y11=a8x10

y12=a9x11

h=a5~x6

g= a7x8

t= a3~x2

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

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

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

S= a1x2v a3x2 v a7~x8

R= a5x6 v a9x11

D1= a1x2v a3x2

D2= a7~x8

D3= a7~x8

D4= a1x2v a3x2

y0=a0x1

y1=a0x1 v a2

y2=a1~x2x1x3 v a3~x2x5

y3=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7

y4=a2x4 v a4x4

y5=a2x4 v a4x4 v a8x10

y6= a2 v a4 v a8x10

y7=a4

y8=a6

y9=a7x8~x9

y10=a5x6

y11=a8x10

y12=a9x11

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

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

S= f v g

R= y10 v y12

D1=f

D2=g

D3= g

D4= f

y0=a0x1

y1=y0 v a2

y2=kx3 v dx5

y3=y2 v p

y4=x4(a2 v a4)

y5=y4 v y11

y6= a2 v y5

y7=a4

y8=a6

y9=m~x9

y10=a5x6

y11=a8x10

y12=a9x11

k= a1~x2x1

f= x2(a1va3)

g= a7~x8

d= a3~x2

t= a5~x6

m= a7 x8

p= x7(t v g)

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

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

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. Прямая структурная таблица переходов и выходов автомата Мура.

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×8~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×8~x9 v b11 x8x9x10 v b12×10 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×8~x9 v b11 x8x9x10 v b11x8x9~x10~x11 v b12×10 v b12~x10~x11 v b13~x11v b14~x11

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

y0=b1

y1= b1 v b4 v b5

y2= b3 v b6

y3= b3 v b6 v b10

y4= b4 v b7

y5= b4 v b7 v b13

y6= b4 v b5 v b7 v b8 v b13

y7= b7 v b8

y8=b11

y8=b12

y10=b9

y11=b13

y12=b12

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

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

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

0 1 К (1) = 0001

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

1 3 1 2

1 4 2 2

1 5 M'= 2 3

1 14 2 4

1 15 2 5

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

2 3 B = {1}

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

2 5 D= {1001,0101,0011}

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

3 5 W=1 K (2) = 0011

4 6 3) u = 3

4 7 1 3

4 8 M'= 2 3

4 14 3 4

4 15 3 5

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

5 7 W = 3 K (3) = 0010

5 8 4) u = 4

5 14 1 4

5 15 2 4

6 7 3 4

6 8 M'= 4 6

7 9 4 7

7 10 4 8

7 11 4 14

8 9 4 15

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

8 11 W = 5 K (4) = 0111

9 0 5) u = 5

10 11 1 5

11 10 2 5

11 11 3 5

11 12 M'= 5 6

11 13 5 7

11 14 5 8

11 15 5 14

12 13 5 15

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

12 15 W = 5 K (5) = 1011

13 14 6) u = 6

13 15 4 6

14 15 M'= 5 6

15 0 6 7

6 8

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

W = 2 K (6) = 1111

7) u = 7

4 7

5 7

M'= 6 7

7 9

7 10

7 11

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

W = 5 K (7) = 1101

8) u = 8

4 8

5 8

M'= 6 8

8 9

8 10

8 11

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

W = 5 K (8) = 1110

9) u = 9

7 9

M'= 8 9

9 0

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

W = 4 K (9) = 1100

10) u = 10

7 10

M'= 8 10

10 11

11 10

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

W = 4 K (10) = 0101

11) u = 11

7 11

8 11

10 11

11 10

M'= 11 11

11 12

11 13

11 14

11 15

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

W = 6 K (11) = 0100

12) u =12

11 12

M'= 12 13

12 14

12 15

B = {11} D = (0110)

W = 1 K (12) = 0110

13) u =13

11 13

M'= 12 13

13 14

13 15

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

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

={1000,1010}

W = 5 K (13) = 1000

14) u =14

1 14

4 14

5 14

M'= 11 14

12 14

13 14

14 15

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

W = 13 K (14) = 1001

15) u=15

K (15)=1010

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

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

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

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

S1=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~x10×11) v b13×11 v b14×11

S4=b0 x1 v b3 v b8~x6x7 v b11(~x8x7 v x8x9~x10~x11) v b12~x10~x11v b13~x11

R1=b7~x6 v b8~x6 v b15

R2=b4 x2 v b11 x8x9 v b12

R3= b4(~x2~x5x4 v x2~x11)v b5(~x2~x5x4 v x2~x11)v b6 x4 v b8 v b12(x10 v ~x10~x11)

R4=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×11

y0=b1

y1= b1 v b4 v b5

y2= b3 v b6

y3= b3 v b6 v b10

y4= b4 v b7

y5= b4 v b7 v b13

y6= b4 v b5 v b7 v b8 v b13

y7= b7 v b8

y8=b11

y8=b12

y10=b9

y11=b13

y12=b12

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

S1=b1(~x2k v x2) v b2k v b3~x4 v b4 v b9 v p v b12

S2=b1~x2t v b2t v b3 x4 v b5~x2 v b9

S3=b1(~x2x1v x2x11) v b11(x8~x9 v d) v b13×11 v b14×11

S4=b0 x1 v b3 v b8~x6x7 v b11(~x8x7 v d) v b12~x10~x11v b13~x11

R1=b7~x6 v b8~x6 v b15

R2=b4 x2 v p v b12

R3= r (b4v b5) v b6 x4 v b8 v b12(x10 v ~x10~x11)

R4=qy1 v b2 x1x3 v b6~x4 v b7(x6 v ~x6~x7) v b10 v b14×11

y0=b1

y1= b1 v b4 v b5

y2= b3 v b6

y3= b3 v b6 v b10

y4= b4 v b7

y5= b4 v b7 v b13

y6= b4 v b5 v b7 v b8 v b13

y7= b7 v b8

y8=b11

y8=b12

y10=b9

y11=b13

y12=b12

k= x1~x3~x4

t= x1~x3x4

q=~x2x1x3 v x2x11

r=~x2~x5x4 v x2~x11

d= x8x9~x10×11

p= b11 x8x9

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

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

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

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

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

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

Заключение

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

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

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

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

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

Приложение А

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

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

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

Приложение В

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

Приложение Г

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

Приложение Е

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

Приложение Ж

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