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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание:

Введение

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

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

2.1 Алгоритм умножения с ускорением 3его порядка 3им способом

2.2 Особенности умножения с ускорением 3его порядка

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

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

условий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список литературы

Приложение А. (обязательное).Функциональная схема операционного автомата

Приложение Б. (обязательное). Содержательная граф-схема алгоритма

Приложение В. (обязательное). Отмеченная граф-схема алгоритма

Приложение Г. (обязательное). Граф автомата Мили

Приложение Д. (обязательное). Граф автомата Мура

Приложение Е. (обязательное). Функциональная схема управляющего автомата



Введение

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

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

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

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

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

Функциональную схему устройства построить в основном логическом базисе. Разрядность операндов - четыре байта (тридцать два разряда).

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

2.1 Алгоритм умножения с ускорением 3-го порядка 3-им способом

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

2. Формируем до начала цикла умножения код 3М.

3. Анализируем 3 старших разряда множителя. В зависимости от того какая это триада(см. Таблица 1) производим сложение или вычитание М, 2М, 3М или 4М с суммой частичных произведений.

4. Сдвигаем множитель и регистр суммы частичных произведений на 3 разряда влево

5. Если множитель не равен 0 то возвращаемся к п.3, иначе завершаем цикл умножения.

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

2.2 Особенности алгоритма умножения с ускорением 3го порядка

При умножении с ускорением 3го порядка множитель разбивается на триады и представляется в восьмеричной двоично-кодированной системе счисления. При умножении с ускорением 3го порядка в качестве слагаемых выступают М, 2М, 3М, 4М, при этом удвоенное множимое получают сдвигом множимого на разряд влево, учетверенное - сдвигом множимого на 2 разряда влево, а утроенное как М+2М до начала самой операции и хранят в специальном регистре. Сдвиги же множимого на один или два разряда влево реализуют не микрооперацией сдвига в этом регистре, а «косой» передачей содержимого регистра множимого на сумматор (через мультиплексор).

8ая цифра	Кратность множимого	1ый и 2ой способы умножения	3ий и 4ый способы умножения
000	-	-	-
001	+М	+М	+М
010	+2М	+2М	+2М
011	+3М	+3М	+3М
100	+4М	+4М	-4М
101	+5М	-3М	-3М
110	+6М	-2М	-2М
111	+7М	-М	-М

Для триад >4 следует формировать дополнение до 8

101=1000-101= 0011= -3М

110=1000-110= 10 = -2М

111=1000-111= 01= -М

При умножении со старших разрядов формируют дополнение до 8 до триады 4

100=1000-100= 100 = -4М

При чем самая старшая триада должна начинаться с 0.Таким образом при умножении с ускорением 3его порядка в качестве слагаемых выступают: +М, +2М, +3М, +4М.

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

1. Знаки операндов: А>0, В>0. Умножить числа с ФЗ в прямом коде, ис-

пользуя умножение с ускорением 3его порядка третьим способом. Проверить результат операции. А-множитель, В-множимое.

А=157(10) =10011101(2)

В=214(10) =11010110(2)

Апк=0,010011101 М=29

Впк=0,011010110

Апк=0, 010 011 101

0,0101 0,0011 0,0010

1,1000 1 1

1,1101 0,0100 0,0011

011 1,1000

100

0,000 000 000 011 010 110 =М

0,000 000 000 110 101 100 =2М

0,000 000 001 010 000 010 =3М

0,000 000 001 101 011 000 =4М

1. 0+0 = 0

Множитель	Сумма ЧП	Комментарий
0,011 100 011	0,000 000 000 000 000 000 0,000 000 001 010 000 010 0,000 000 001 010 000 010	+3М
0,100 011 000	0,000 001 010 000 010 000 1,111 111 110 010 101 000 10,000 001 000 010 111 000	Сдвиги -4М
0,011 000 000	0,001 000 010 111 000 000 1,111 111 110 101 111 110 10,001 000 001 100 111 110	Сдвиги -3М

2.

А*В=001000001100111110(2)=33598(10)

2. Знаки операндов: А<0, В>0. Умножить числа с ФЗ в прямом коде, используя умножение с ускорением 3его порядка третьим способом. Проверить результат операции. А-множитель, В-множимое.

A=-208(10) =-11010000(2)

В=197(10) =11000101(2)

Апк=1,011010000 М=29

Впк=0,011000101

0,000 000 000 011 000 101 =М

0,000 000 000 110 001 010 =2М

0,000 000 001 001 001 111 =3М

0,000 000 001 100 010 100 =4М

1+0=1

Множитель	Сумма ЧП	Комментарий
0,011 010 000	0,000 000 000 000 000 000 0,000 000 001 001 001 111 0,000 000 001 001 001 111	+3М
0,010 000 000	0,000 001 001 001 111 000 0,000 000 000 110 001 010 0,000 001 010 000 000 010	Сдвиги +2М
0,000 000 000	0,001 010 000 000 010 000	Сдвиги

А*В=-001010000000010000(2)=-40976(10)

3. 

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

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

При чтении операндов с ШИВх проводится проверка их на нуль, в целях ускорения процесса умножения, так как произведение в этом случае всегда будет равно нулю.

Так как используется ускорение 3-го порядка, то необходимо формировать +2М, +3М и +4М. Код 3М формируется до начала цикла умножения и хранится в регистре, с которого подается на мультиплексор. Так же мультиплексор используется для формирования удвоенного и учетверенного множимого посредством сдвига косой передачей.

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

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

32х разрядные регистры RG1(сдвиговый)и RG2 для приема числовой части операндов.

триггер Т для приёма знака множителя;

32х разрядный регистр RG3 для хранения утроенного множимого;

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

64-разрядный сумматор SМ для действий с числовой частью множимого и частной суммы;

33-разрядный мультиплексор MS для управления подачей информации на плечо В сумматора SM;

3х-разрядный счетчик СТ для организации цикла произведения;

дешифратор DC 4 на 16, позволяющий выявить все возможные четырёхразрядные комбинации в четырёх старших разрядах регистра множителя;

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

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

Перед началом цикла умножения обнуляется RG4. После поступления первого операнда на входную шину, биты с нулевого по тридцатый записываются в RG1 и RG2, тридцать первый бит записывается в RG1[31] и в триггер Т, в RG1[31] - ноль.

Далее осуществляется проверка первого операнда на 0. Для этого операнд подается на n-входовой элемент «ИЛИ». В случае если операнд нулевой то на выходе p0=0, значит выходим из цикла умножения.

После поступления второго операнда на входную шину, он записывается в RG1. Осуществляется проверка на 0.

На плечо B сумматора SM информация подается через мультиплексор MS либо множимое, либо удвоенное или утроенное или учетверенное множимое.

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

у1 - занесение числовой части операнда в RG1[0,30], запись знака в триггер Т, установка счетчика в '0000';

у2 - запись операнда в RG2;

y3 - запись в RG3;

y4 - управление на мультиплексоре;

y5 - сдвиг RG1, RG4 на 3 разряда влево, СТ:=СТ+1;

у6 - запись в RG4;

y7 - сброс;

y8 - управление выдачей на ШИВых;

y9 - управление на мультиплексоре.

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

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

р0 - проверка операндов на 0;

р1 -старший разряд счетчика 1;

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

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

Выполнение алгоритма начинается с проверки наличия операндов на ШИВх.

После поступления первого операнда на входную шину, c 0 по 30 разряд записывается в RG1 и RG2, 31 разряд - знак записывается в RG2[31] и в триггер Т, в RG1[31] заносится ноль, счетчик устанавливается равным «0000» (блок 2).

Если в RG1 все разряды нули (блок 3) то проверяем возможность выдачи по ШИВых и выдаем результат операции - ноль.

После поступления второго операнда на входную шину, он записывается в RG1.(блок 5), выполняется проверка на 0(блок 6). Если все разряды равны 0, то проверяем возможность выдачи по ШИВых и выдаем результат - 0.

Для начала цикла умножения в RG3 записывается утроенное множимое, путем сложения на SM множимого(блок 5) и удвоенного множимого(блок 7). Обнуляется RG4(блок 8). После чего, в цикле, в зависимости от анализируемой тетрады множителя выполняется сложение или вычитание удвоенного, утроенного, учетверенного или просто множимого с частной суммой из RG4 и в этом же такте запись результата в RG4(блоки 9-11).

Если в старшем разряде счетчика появилась 1(блок 10), выходим из цикла умножения, иначе выполняем сдвиги в регистрах RG1 и RG4 на три разряда, а так же увеличиваем счетчик на единицу(блок 11) и возвращаемся в анализу старшей тетрады в RG1.

Если есть возможность выдачи по ШИВых, то выдаем числовую часть результата из RG4 и знак при помощи схемы сложения по модулю 2(блок 13).

Содержательная ГСА приведена в приложении Б.

5. 

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

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

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

Микрокоманды	Микрокоманды
Y1	y1,y2,y7
Y2	y1,y6
Y3	y3, у4
Y4	у7
Y5	y4,y6,y9
Y6	y5
Y7	y8

X1	X2	X3	X4
X	P0	P1	Z

В приложении В приведена разметка граф схемы алгоритма для модели Мили символами а0…а5 и для модели Мура символами b0…b9.

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

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

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

Граф автомата Мили имеет 6 вершин, соответствующих состояниям автомата а0,a1,a2,a3,a4,а5, дуги его отмечены входными сигналами, действующими на каждом переходе, и набором выходных сигналов, вырабатываемых управляющим автоматом на данном переходе.

Граф автомата Мура имеет 10 вершин, соответствующих состояниям автомата b0,b1,b2,b3,b4,b5,b6,b7,b8,b9, каждое из которых определяет наборы выходных сигналов Y1,Y2…Y7 управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.

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

Рассмотрим некоторые варианты возможных структурных схем УА:

· классическая структура УА пригодна для реализации любого УА, но она не является минимальной с точки зрения цены КС;

· модифицированная классическая структура на основе регистра и дешифратора, использование которого понижает цену схемы классического варианта;

· структура УА на основе сдвигового регистра с выбором унитарного кодирования внутренних состояний целесообразно использовать только в тех случаях, когда число разрядов кода ненамного меньше числа внутренних состояний, иначе возникнут значительные затраты на память автомата, которые поглотят выигрыш от уменьшения цены КС;

· структура на основе счетчика выгодна, когда граф проектируемого автомата имеет большое количество последовательных (стандартных) переходов и незначительное число нестандартных;

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

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

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

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

8. 

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

В управляющем автомате в качестве элемента памяти могут использоваться D-триггер, RS-триггер, Т-триггер. Поэтому кодировку состояний рассмотрим для всех случаев.

При использовании D-триггеров в качестве элементов памяти для получения смены состояний на каждом переходе сигналы возбуждения должны быть поданы на те триггеры, которые в коде состояния перехода содержат `1'. Отсюда основное требование к выбору кодов состояний : чем больше переходов в какое-либо состояние, тем меньше `1' должен содержать код этого состояния. Здесь удобно строить инверсные таблицы переходов. Этот способ кодирования позволит получить комбинационную схему меньшей сложности.

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

При использовании Т-триггеров сигналы возбуждения подают на те триггеры, которые изменяют своё состояние на переходе (0->1, 1->0).

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

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

При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремится использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 6 состояний (a0 ,…, a5) минимально необходимо 3 элемента памяти. Из множества 3-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, тем меньше в коде этого состояния следует использовать "1". Для этого построим Таблицу 3.

Таблица 3

а0	а1	а2	а3	а4	а5
а0,а1,а2,а5	а0	а1	а2	а3,a5	а4
000	010	011	100	001	101

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

Таблица 4

а0	а1	а2	а3	а4	а5
000	010	011	100	001	101

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

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



Таблица 5

Исходное состояние am	Код am	Состояние перехода аs	Код as	Входной сигнал Х(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения D-триггеров
a0	000	a0	000	~x1	-	-
		a1	010	x1	y1y2y7	D2
a1	010	a0	000	~x2x4	y8	-
		a2	011	x1x2	y1y6y9	D1D2
a2	011	a0	000	~x2x4	y8	-
		a3	100	x2	y3y4	D3
a3	100	a4	001	1	y7	D1
a4	001	a5	101	1	y4y6	D1D3
a5	101	a0	000	x3x4	y8	-
		a4	001	~x3	y5	D1

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

D1=a1x1x2 v a3 v a4 v a5~x3

D2=a0x1 v a1x1x2

D3=a2x2 v a4

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

y1=a0x1 v a1x1x2

y2=a0x1

y3=a2x2

y4=a2x2 v a4

y5=a5~x3

y6=a1x1x2 v a4

y7=a0x1 v a3

y8=a1~x2x4 v a2~x2x4 v a5x3x4=~x2x4(a1 v a2) v a5x3x4

y9=a1x1x2

Выделяем общие части:

c=a1x1x2 (3) d=a0x1 (2) e=a5~x3 (2) f=a2x2 (2)

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

D1=c v a3 v a4 v e (4)

D2=d v c (2)

D3=f v a4 (2)

y1=d v c (2)

y2=d

y3=f

y4=f v a4 (2)

y5=e

y6=c v a4 (2)

y7=d v a3 (2)

y8=(a1 v a2)~x2x4 v a5x3x4 (10)

y9=c (35)

Инверторы (~x2,~x3) (2)

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

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

Для этого сначала выпишем матрицу M - матрицу всех возможных переходов автомата. Состояниям автомата a0 и a1 присвоим коды: К(a0)=000, К(a1)=001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы с 1-м состоянием. В множество В выпишем коды уже закодированных состояний, а в множество C коды с кодовым расстоянием "1" от кодов в В и т.д. Для определения наиболее выгодного кода будем определять функцию W, т.е. находить суммы кодовых расстояний между множествами Вi и Di. Код с наименьшей суммой является наиболее оптимальным.

1). a2

B={0,1} C10={010,100} W100=1+2=3

C11={011,101} W010=1+2=3

D12={100,010,011,101} W011=2+1=3

W101=2+1=3



Выбираем любой:

K(a2)=010

2). a3

B={2} C12={110,011} W110=1

D13=={110,011} W011=1

Выбираем любой:

K(a3)=110

3). a4

B={3} C13={100,010,111} W100=1

D14={100} W111=1

Выбираем любой:

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

K(a4)=100

4). a5

B={4} C14={101,110,000} W101=1

D15={101,110 } W110=1

Выбираем любой:



K(a5)=101

а0	а1	а2	а3	а4	а5
000	001	010	110	100	101

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

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

Исходное состояние am	Код am	Состояние перехода аs	Код as	Входной сигнал Х(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения RS-триггеров
a0	000	a0	000	~x1	-	-
		a1	001	x1	y1y2y7	S1
a1	001	a0	000	~x2x4	y8	R1
		a2	010	x2x1	y1y6y9	S2R1
a2	010	a0	000	~x2x4	y8	R2
		a3	110	x2	y3y4	S3
a3	110	a4	100	1	y7	R2
a4	100	a5	101	1	y4y6	S1

S1=a0x1 v a4

S2=a1x1x2

S3=a2x2

R1=a1~x2x4 v a1x2x1 v a5x3x4 v a5~x3

R2=a2~x2x4 v a3

R3=a5x3x4

y1=a0x1 v a1x1x2

y2=a0x1

y3=a2x2

y4=a2x2 v a4

y5=a5~x3

y6=a1x1x2 v a4

y7=a0x1 v a3

y8=a1~x2x4 v a2~x2x4 v a5x3x4

y9=a1x1x2

Выделяем общие части:

c=a1x1x2 (3)

d=a0x1 (2) e=a5~x3 (2)

f=a2x2 (2) g=~x2x4 (2)

h=a5x3x4 (3)

S1=d v a4 (2)

S2=c

S3=f

R1=a1g v c v h v e(6)

R2=a2g v a3 (4)

R3=h

y1=d v c(2)

y2=d

y3=f

y4=f v a4 (2)

y5=e

y6=c v a4 (2)

y7=d v a3 (2)

y8=a1g v a2g v h=g(a1 v a2) v h (6)

y9=c (40)



Инверторы (~x2,~x3) (2)

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

Исходное состояние am	Код am	Состояние перехода аs	Код as	Входной сигнал Х(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения T-триггеров
a0	000	a0	000	~x1	-	-
		a1	001	x1	y1y2y7	Т1
a1	001	a0	000	~x2x4	y8	Т1
		a2	010	x2x1	y1y6y9	Т1Т2
a2	010	a0	000	~x2x4	y8	Т2
		a3	110	x2	y3y4	Т3
a3	110	a4	100	1	y7	Т2
a4	100	a5	101	1	y4y6	Т1
a5	101	a0	000	x3x4	y8	Т1Т3
		a4	100	~x3	y5	Т1

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

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

T1=a0x1 v a1~x2x4 v a1x1x2 v a4 v a5x3x4 v a5~x3

T2=a1x1x2 v a2~x2x4 v a3

T3=a2x2 v a5x3x4

y1=a0x1 v a1x1x2

y2=a0x1

y3=a2x2

y4=a2x2 v a4

y5=a5~x3

y6=a1x1x2 v a4

y7=a0x1 v a3

y8=a1~x2x4 v a2~x2x4 v a5x3x4

y9=a1x1x2

Выделяем общие части:

c=a1x1x2 (3)

d=a0x1 (2) e=a5~x3 (2)

f=a2x2 (2) g=~x2x4 (2)

h=a5x3x4 (3)

T1=d v a1g v c v a4 v h v e (8)

T2=c v a2g v a3 (5)

T3=f v h (2)

y1=d v c (2)

y2=d

y3=f

y4=f v a4 (2)

y5=e

y6=c v a4 (2)

y7=d v a3 (2)

y8=g(a1 v a2) v h (6)

y9=c (43)

Инверторы (~x2,~x3) (2)

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



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

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

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

Таблица 8

a0	a1	a2	a3	a4	a5
000	001	010	011	100	101

Исходное состояние am	Код am	Состояние перехода аs	Код as	Входной сигнал Х(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения RS-триггеров
a0	000	a0	000	~x1	-	-
		a1	001	x1	y1y2y7	INC
a1	001	a0	000	~x2x4	y8	R
		a2	010	x2x1	y1y6y9	INC
a2	010	a0	000	~x2x4	y8	R
		a3	011	x2	y3y4	INC
a3	011	a4	100	1	y7	INC
a4	100	a5	101	1	y4y6	INC
a5	101	a0	000	x3x4	y8	R
		a4	100	~x3	y5	DEC

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

INC=a0x1 v a1x1x2 v a2x2 v a3 v a4

DEC=a5~x3

R=a1~x2x4 v a2~x2x4 v a5x3x4

y1=a0x1 v a1x1x2

y2=a0x1

y3=a2x2

y4=a2x2 v a4

y5=a5~x3

y6=a1x1x2 v a4

y7=a0x1 v a3

y8=a1~x2x4 v a2~x2x4 v a5x3x4

y9=a1x1x2

Выделяем общие части:

c=a1x1x2 (3)

d=a0x1 (2) e=a5~x3 (2)

f=a2x2 (2) g=~x2x4 (2)

h=a5x3x4 (3)

INC= d v c v f v a3 v a4 (5)

DEC=e

R=y8

y1=d v c (2)

y2=d

y3=f

y4=f v a4 (2)

y5=e

y6=c v a4 (2)

y7=d v a3 (2)

y8=g(a1 v a2) v h (6)

y9=c (33)



Инверторы (~x2,~x3) (2)

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

9. 

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

9.1 Кодирование модели автомата Мура для D-триггеров

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

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

Построим обратную таблицу переходов.

Таблица 10

b0	b1	b2	b3	b4	b5	b6	b7	b8	b9
b0,b9	b0	b1,b2	b1,b2	b3	b4	b5,b7	b6	b1,b3,b6,b8	b1,b3,b6,b8

b0	b1	b2	b3	b4	b5	b6	b7	b8	b9
0011	0101	0010	0100	0110	1001	1000	1010	0001	0000

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

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

Исходное состояние bm	Выходные сигналы Y(bm,bs)	Код bm	Состояние перехода bs	Код bs	Входной сигнал Х(bm,bs)	Функции возбуждения D-триггеров
b0	-	0011	b0	0011	~x1	D1D2
			b1	0101	x1	D1D3
b1	y1y2y7	0101	b2	0010	x2~x1	D2
			b3	0100	x2x1	D3
			b8	0001	~x2~x4	D1
			b9	0000	~x2~x4	-
b2	-	0010	b2	0010	~x1	D2
			b3	0100	x1	D3
b3	y1y6y9	0100	b4	0110	x2	D2D3
			b8	0001	~x2~x4	D1
			b9	0000	~x2x4	-
b4	y3y4	0110	b5	1001	1	D1D4
b5	y7	1001	b6	1000	1	D4
b6	y4y6	1000	b7	1010	~x3	D2D4
			b8	0001	x3~x4	D1
			b9	0000	x3x4	-
b7	y5	1010	b6	1000	1	D4
b8		0001	b8	0001	~x4	D1
			b9	0000	x4	-
b9	y8	0000	b0	0011	1	D1D2

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

D1=b0~x1 v b0x1 v b1~x2~x4 v b3~x2~x4 v b4 v b6x3~x4 v b8~x4 v b9=

=b0 v ~x2~x4(b1 v b3) v ~x4(b6x3 v b8) v b4 v b9=

=b0 v ~x4(~x2(b1 v b3) v b6x3 v b8) v b4 v b9)

D2=b0~x1 v b1x2~x1 v b2~x1 v b3x2 v b6~x3 v b9 =

=~x1(b0 v b1x2 v b2) v b3x2 v b6~x3 v b9

D3=b0x1 v b1x1x2 v b2x1 v b3x2=x1(b0 v b1x2 v b2) v b3x2

D4=b4 v b5 v b6~x3 v b7

y1=b1 v b3

y2=b1

y3=b4

y4=b4 v b6

y5=b7

y6=b3 v b6

y7=b1 v b5

y8=b9

y9=b3

Выделяем общие части:

с=b6~x3 (2)

d=b0 v b1x2 v b2 (5)

e=b3x2 (2)

f=b1 v b3 (2)

D1=b0 v ~x4(~x2f v b6x3 v b8) v b4 v b9 (13)

D2=~x1d v e v c v b9 (6)

D3=x1d v e (4)

D4=b4 v b5 v c v b7 (4)

y1=f

y2=b1

y3=b4

y4=b4 v b6 (2)

y5=b7

y6=b3 v b6 (2)

y7=b1 v b5 (2)

y8=b9

y9=b3 (44)

Инверторы (~x1,~x2,~x3,~x4) (2)

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

10. 

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

Сравнивая построения автомата на основе модели Мура и Мили, видно, что построение автомата по модели Мили требует меньше аппаратурных затрат, чем построение автомата по модели Мура. Модель Мили на D-триггерах имеет цену по Квайну 52, на RS-триггерах - 60, на T-триггерах - 63 а на счётчике 51.

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

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



Заключение

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

При синтезе МПА была рассмотрена модель Мили и модель Мура. В результате проделанной работы оказалось, что наименьшие аппаратурные затраты даёт модель Мили с использованием счетчика в качестве элемента памяти.



Приложение А (обязательное). Функциональная схема операционного автомата



Приложение Б (обязательное). Содержательна граф-схема алгоритма



Приложение В (обязательное). Отмеченная граф-схема алгоритма.



Приложение Г (обязательное). Граф автомата Мили.

Приложение Д (обязательное). Граф автомата Мура.



Приложение E(обязательное). Функциональная схема операционного автомата

Размещено на Allbest.ru