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

Введение

 

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

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

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

 

1

01110010

10011100100101110110110

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

 

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

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

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

 

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

 

А=-22

В=19

 

-22	1	00101	01010
19	0	00101	10011

 

→ множитель	← множимое	Сумма ЧП	комментарий
0,10011	0,0000001010	0,0000000000	сложение
		0,0000001010
		0,0000001010
0,01001	0,0000010100	0,0000001010	сложение
		0,0000010100
		0,0000011110
0,00100	0,0000101000	0,0000011110	сдвиги
0,00001	0,0010100000	0,0000011110	сложение
		0,0010100000
		0,0010111110
0.00000	0,0101000000	0,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
У2	y2, y3
У3	y1, y4, y5, y6
У4	y1, y6
У5	y4, y5, y6, y7
У6	y6, y7
У7	y10
У8	y3
У9	y8
У10 У11 У12	y9 y5, y6, y11 y12

 

Таблица 2.

Входной сигнал УА	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
Логическое условие ОА	X	P1	P2	P3	P4	P5	P7	P8	P9	P6	Z

 

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

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

 

 

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

 

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

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

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