Синтез синхронного управляющего автомата типа Мили, Теория автоматического управления (ТАУ)

Выдержка из текста работы

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

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

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

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

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

Tу = nШ

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

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

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

TУ = nсл

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Присвоить модулю произведения знак из п.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

00,00101

00,01010

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

0,01101 +Вдк

0,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.

Входной сигнал УА

X10

X11

Логическое условие ОА

В приложении В приведена разметка граф схемы алгоритма для модели Мили символами а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-триггерах.

Исходное состояние am

Код am

Состояние перехода as

Код as

Входной сигнал

Выходной сигнал

Функции возбуждения

0010

0110

~x1

—

У0, y1

D2D3

0110

0100

0000

~x2x1x3

~x2x1~x3

y2, y3

—

0100

1100

~x4

y1, y4, y5, y6

Y1, y6

D1D2

1100

1010

0000

~x2x5

~x2~x5

y2, y3

—

D1D3

—

1010

0011

~x4

y4, y5, y6, y7

Y6, y7

D3D4

0011

0010

0001

~x6x7

~x6~x7

y10

—

0001

1001

D1D4

1001

0001

1000

~x8x7

~x8~x7

x8x9

x8~x9

—

1000

0000

x10

~x10

y5, y6,y11

—

0000

0010

0000

x11

~x11

y12

—

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

Таблица 4

aS	а0	a1	a2	a3	a4	а5	a6	A7	a8	a9
am	a0 a5 a9	a0	a1	a2	a3	а4	a5 a7	A6	a7	a8 a9 a3 a1
Коды	0010	0110	0100	1100	1010	0011	0001	1001	1000	0000

Наибольшее количество переходов в состояние 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

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

4) u = 3

M’= 3 4

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

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

6) u =5

M’= 5 0

B = {4,0}

C(0) = {1000}

C(4) = {1100, 0101}

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

7) u=6

M’= 6 7

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

8) u=7

M’= 7 6

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

9) u = 8

M’= 7 8

B= {7,9}

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

C(9) = {1010}

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

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

Исходное состояние am

Код am

Состояние перехода as

Код as

Входной сигнал

Выходной сигнал

Функции возбуждения

0000

0001

~x1

—

у0, y1

—

0001

0011

0010

~x2x1x3

~x2x1~x3

y2, y3

—

S3, R4

0011

0110

~x4

y1, y4, y5, y6

y1, y6

R4,S2

0110

0100

0010

~x2x5

~x2~x5

y2, y3

—

0100

1000

~x4

y4, y5, y6, y7

y6, y7

R2,S1

1000

0000

1100

~x6x7

~x6~x7

y10

—

1100

1101

1100

1010

~x8x7

~x8~x7

x8x9

x8~x9

—

R2,S3,R4

1010

0010

x10

~x10

y5, y6,y11

—

0010

0000

0010

x11

~x11

y12

—

Логические выражения для каждой функции возбуждения 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 Кодирование состояний модели МИЛИ на счётчике

Исходное состояние am

Код am

Состояние перехода as

Код as

Входной сигнал

Выходной сигнал

Функции возбуждения

0000

0001

~x1

—

у0, y1

—

Inc

0001

0010

1001

~x2x1x3

~x2x1~x3

y2, y3

—

Inc

D1D4S

0010

0011

~x4

y1, y4, y5, y6

y1, y6

Inc

0011

0100

1001

~x2x5

~x2~x5

y2, y3

—

Inc

D1D4S

0100

0101

~x4

y4, y5, y6, y7

y6, y7

Inc

0101

0000

0110

~x6x7

~x6~x7

y10

—

Inc

0110

0111

Inc

0111

0110

1000

~x8x7

~x8~x7

x8x9

x8~x9

—

D2D3S

Inc

1000

1001

x10

~x10

y5, y6,y11

—

Inc

1001

0000

1001

x11

~x11

y12

—

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения триггеров
b0	—	0110	b1	1111	x1	D1D2D3D4
b1	y0y1	1111	b2 b3 b4 b5 b14 b15	1101 0111 0100 1000 0001 0000	~x2x1 ~x2x1x3 ~x2x1~x3x4 ~x2x1~x3~x4 x2~x11 x2x11	D1D2D4 D2D3D4 D2 D1 D4 —
b2	—	1101	b2 b3 b4 b5	1101 0111 0100 1000	~x1 x1x3 x1~x3x4 x1~x3~x4	D1D2D4 D2D3D4 D2 D1
b3	y2y3	0111	b4 b5	0100 1000	x4 ~x4	D2 D1
b4	y1y4y5y6	0100	b6 b7 b8 b14 b15	0101 1100 1010 0001 0000	~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11	D2D4 D1D2 D1D3 D4 —
b5	y1y6	1000	b6 b7 b8 b14 b15	0101 1100 1010 0001 0000	~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11	D2D4 D1D2 D1D3 D4 —
b6	y2y3	0101	b7 b8	1100 1010	x4 ~x4	D1D2 D1D3
b7	y4y5y6y7	1100	b9 b10 b11	1110 1001 0010	x6 ~x6x7 ~x6~x7	D1D2D3 D1D4 D3
b8	y6y7	1010	b9 b10 b11	1110 1001 0010	x6 ~x6x7 ~x6~x7	D1D2D3 D1D4 D3
b9	y10	1110	b0	0110	1	D2D3
b10	Y3	1001	b11	0010	1	D3
b11	Y8	0010	b10 b11 b12 b13 b14 b15	1001 0010 1011 0011 0001 0000	~x8x7 ~x8~x7 x8~x9 x8x9x10 x8x9~x10~x11 x8x9~x10x11	D1D4 D3 D1D3D4 D3D4 D4 —
b12	Y9	1011	b13 b14 b15	0011 0001 0000	x10 ~x10~x11 ~x10x11	D3D4 D4 —
b13	y5y6y11	0011	b14 b15	0001 0000	~x11 x11	D4 —
b14	—	0001	b14 b15	0001 0000	~x11 x11	D4 —
b15	y12	0000	b0	0110	1	D2D3

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

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

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

W = 2 K(6) = 1111

7) u = 7

M’= 6 7

7 10

7 11

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

W = 5 K(7) = 1101

8) u = 8

M’= 6 8

8 10

8 11

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

W = 5 K(8) = 1110

9) u = 9

M’= 8 9

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения триггеров
b0	—	0000	b1	0001	x1	S4
b1	y0y1	0001	b2 b3 b4 b5 b14 b15	0011 0010 0111 1011 1001 1010	~x2x1 ~x2x1x3 ~x2x1~x3x4 ~x2x1~x3~x4 x2~x11 x2x11	S3 S3R4 S2S3 S1S3 S1 S1S3R4
b2	—	0011	b2 b3 b4 b5	0011 0010 0111 1011	~x1 x1x3 x1~x3x4 x1~x3~x4	— R4 S2 S1
b3	y2y3	0010	b4 b5	0111 1011	x4 ~x4	S2S4 S1S4
b4	y1y4y5y6	0111	b6 b7 b8 b14 b15	1111 1101 1110 1001 1010	~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11	S1 S1R3 S1R4 S1R2R3 S1R2R4
b5	y1y6	1011	b6 b7 b8 b14 b15	1111 1101 1110 1001 1010	~x2x5 ~x2~x5x4 ~x2~x5~x4 x2~x11 x2x11	S2 S2R3 S2R4 R3 R4
b6	y2y3	1111	b7 b8	1101 1110	x4 ~x4	R3 R4
b7	y4y5y6y7	1101	b9 b10 b11	1100 0101 0100	x6 ~x6x7 ~x6~x7	R4 R1 R1R4
b8	y6y7	1110	b9 b10 b11	11000101 0100	x6 ~x6x7 ~x6~x7	R3 R1R3S4 R1R3
b9	y10	1100	b0	0000	1	S1S2
b10	y3	0101	b11	0100	1	R4
b11	y8	0100	b10 b11 b12 b13 b14 b15	0101 0100 0110 1000 1001 1010	~x8x7 ~x8~x7 x8~x9 x8x9x10 x8x9~x10~x11 x8x9~x10x11	S4 — S3 S1R2 S1R2S4 S1R2S3
b12	y9	0110	b13 b14 b15	1000 1001 1010	x10 ~x10~x11 ~x10x11	S1R2R3 S1R2R3S4 S1R2
b13	y5y6y11	1000	b14 b15	1001 1010	~x11 x11	S4 S3
b14	—	1001	b14 b15	1001 1010	~x11 x11	— S3R4
b15	y12	1010	b0	0000	1	R1R3

Из таблицы получим логические выражения для каждой функции возбуждения 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~x10x11) v b13 x11 v b14 x11

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 x11

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 x11 v b14 x11

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 x11

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~x10x11

p= b11 x8x9

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

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

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

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

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

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

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

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

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

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

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