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

Содержание

Введение

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

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

1.2 Алгоритм умножения двоичных чисел вторым способом с простой коррекцией

1.3 Числовой пример умножения двоичных чисел по алгоритму

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

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

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

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

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

7. Кодирование состояний управляющего автомата

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

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

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

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

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

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

8.1 Прямая структурная таблица переходов автомата Мили при кодировании на D-триггерах

8.2 Прямая структурная таблица переходов автомата Мура при кодировании на D-триггерах

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

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

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

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

Заключение

Перечень используемых сокращений

Приложения

Введение

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

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

При этом стоит задача минимальных аппаратурных затрат в операционной части автомата при приемлемом быстродействии.

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

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

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

Процесс умножения состоит из последовательности операций сложения и сдвигов. Причём сложение производится в дополнительном коде (ДК).

На рисунке 1 представлена схема алгоритма умножения двоичных чисел вторым способом:

Рисунок 1

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

1.2 Алгоритм умножения двоичных чисел вторым способом с простой коррекцией

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

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

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

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

4. Сложить порядки сомножителей. При этом могут возникнуть следующие ситуации: переполнение разрядной сетки (ПРС),временное ПРС или потеря младших разрядов (ПМР). Если возникло ПРС (признаком ПРС является получение единицы переноса и единицы в старшем разряде результирующего порядка), то необходимо зафиксировать её появление и прекратить операцию. Временное ПРС может возникнуть, когда в старшем разряде, равном единице, образовалась единица переноса, но все разряды порядка, за исключением старшего, равны нулю. При этом нужно продолжить алгоритм умножения. Если возникла ситуация ПМР (признаком ПМР является отсутствие единицы переноса и ноль в старшем разряде результирующего порядка), то необходимо зафиксировать её появление и выдать нулевой результат. В противном случае переходим к пункту 5.

5. Анализ младшей цифры очередного разряда множителя: если цифра множителя «1», то суммировать множимое с накопленной суммой частичных произведений (ЧП). В результате суммирования может возникнуть ситуация временного ПРС в мантиссе, которая устраняется последующим сдвигом вправо.

Сдвиги в каждом такте умножения: множитель на один разряд вправо, множимое на один разряд влево.

6. После цикла умножения необходимо провести проверку на необходимость нормализации результата. Если произведение денормализовано, проведем нормализацию результата: сдвинем произведение на 1 разряд влево, вычтем “1” из порядка произведения. При этом, если ранее было зафиксировано временное ПРС, оно устраняется. Если после нормализации мантиссы произошло ПМР, нужно зафиксировать её появление и вывести результат равный «0»; в противном случае переходим к пункту 7.

Денормализация возможна лишь на один разряд, т.к. операнды поступают на входную шину уже нормализованными. Если результат нормализован, необходимо проверить, было ли зафиксировано временно ПРС. Если да, то установить признак ПРС и операцию необходимо прекратить.

7. Присваиваем знак модулю произведения из пункта 1 алгоритма. Если после нормализации результата зафиксирован признак ПМР, то в качестве знака результата необходимо выдать ноль.

Числовой пример умножения двоичных чисел по алгоритму

Рассмотрим алгоритм умножения на числовом примере.

Для численного примера возьмем числа, где под мантиссу отведено 8 разрядов, под порядок - 5 разрядов. Умножение чисел другой разрядности выполняется аналогично.

Умножение операндов вторым способом представлено в таблице 1.

Таблица 1

Множитель	Множимое	Сумматор	Пояснения
0,1001101	0,0000000 1001010	0,0000000 1001010	Сложение
			Сдвиг
0,0100110	0,0000001 0010100		Сдвиг
0,0010011	0,0000010 0101000	0,0000000 1001010	Сложение
		0,0000010 0101000	Сдвиг
		0,00000101110010
0,0001001	0,0000100 1010000	0,0000010 1110010	Сложение
		0,0000100 1010000	Сдвиг
		0,0000111 1000010
0,0000100	0,0001001 0100000		Сдвиг
0,0000010	0,0010010 1000000		Сдвиг
0,0000001	0,0100101 0000000	0,0000111 1000010	Сложение
		0,0100101 0000000	Сдвиг
		0,0101100 1000010

Полученное псевдопроизведение: 0,0101100 1000010

Произведём коррекцию :0,0101100 1000010

Вдк=0,0110110 0000000

0,1100010 1000010

(C*D)дк=1,11000101000010 , (C*D)пк=1,00111010111110 * 214

P = (-51)*74 = -3774 = -1110101111102

Складываем порядки:

0.0111

0.0111

0.1110

?Ситуация ПМР, которая не может быть устранена при денормализации произведения.

Пусть порядки двух операндов записаны в 4х-разрядной сетке

Рассмотрим простой пример (используя сложение в ДК): 2-12=-10

0,0010

1,0100

1,0110 получим неверный порядок: 0110 = -6;

Признаком ПМР является отсутствие единицы переноса и ноль в старшем разряде результирующего порядка.

?Ситуация ПРС.

Пусть характеристики записаны в 4х-разрядной сетке

Рассмотрим простой пример (используя сложение в МДК): 10-1=9;

00,1010

11,1111

10.1001 неверный результат, так как появилась единица переноса и запрещённая знаковая комбинация;

Признаком ПРС является получение единицы переноса и единицы в старшем разряде результирующей характеристики.

2. Обоснование и выбор функциональной схемы операционной части устройства. Определение списка микроопераций (МО) и логических условий (ЛУ)

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

? 48-разрядные сдвиговые регистры RG2 и RG3 для приема мантисс операндов и последующей работы с ними;

? 24-разрядный сдвиговый регистр RG1 для хранения мантиссы множителя;

? 8-разрядный регистр хранения RG4 и 8-разрядный счетчик CT2 для приема порядков операндов и последующей работы с ними;

? 48-разрядный сумматор SM1, содержащий вход переноса, для сложения мантисс операндов в дополнительном коде;

? 8-разрядный сумматор SM2, содержащий вход и выход переноса, для вычитания порядков операндов (сложения в дополнительном коде);

? триггер Т2, необходимый для фиксации единицы переноса с сумматора SM2;

? триггер Т1, необходимый для фиксации временного ПРС;

? совокупность 8-разрядных схем сложения по модулю два для управляемого инвертирования содержимого регистра хранения RG4;

? совокупность 8-разрядных схем сложения по модулю два для управляемого инвертирования содержимого счётчикаCT2;

? совокупность 48-разрядных схем сложения по модулю два для управляемого инвертирования содержимого сдвиговых регистровRG1 и RG2;

? комбинационная схема для анализа переполнения разрядной сетки;

? схема исключающего ИЛИ (XOR) для определения знака результата;

? 6-разрядный инкрементный счётчик CT1 для суммирования тактов операции умножения мантисс ;

? 48-разрядный двухплечевой мультиплексорMS1, для передачи содержимого регистров RG1 или RG2 на совокупность 48-разрядных схем сложения по модулю 2;

Операнды разрядностью четыре байта (32 разряда) поступают по входной шине (ШиВх) в дополнительном коде (ДК) в операционный автомат. После поступления на ШиВх множителя мантисса операнда записывается в сдвиговые регистрыRG1и RG2, порядок в регистр хранения RG4под действием управляющего сигнала у0. Следующим тактом содержимое регистра RG4 подаётся на инвертор, если это необходимо, а затем на плечоASM2. После поступления операнда производится проверка его на ноль. Так как операнды по ШиВх поступают в операционный автомат в нормализованном виде, то следующий за старшим(то есть за знаковым) разряд в регистре RG2 должен быть равен единице. Проверка осуществляется с помощью осведомительного сигнала P1. Если произошло умножение на ноль (P1=0), происходит обнуление регистра результата и завершение операции.

После поступления на ШиВх второго операнда (множимого) его мантисса записывается в сдвиговый регистр RG2, порядок в регистр RG4 под действием управляющего сигнала y1.

Для экономии управляющих сигналов приёмом знаков управляют сигнал записи в регистры RG2 и RG1.

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

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

С помощью этой же комбинационной схемы, осуществляется проверка на возникновение ПМР.

Вычитание порядков происходит с использованием ДК.

Для управления инверсией порядков и управлением единицей переноса применён инвертор. Это позволяет избавиться от одного управляющего сигнала и ускорить быстродействие системы в целом.

Производится корректировка псевдопроизведения в соответствии с алгоритмом умножения. С использованием мультиплексора MS1производится передача мантисс для их инвертирования, а затем на плечо В SM1 и последующей записи в регистр RG3

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

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

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

Таблица 2

Управляющий сигнал	Микрооперации
y0	запись в регистры RG1, RG2, RG4, обнуление триггеров T1,T2;
y1	запись в регистры RG2 и RG4;
y2	запись в счетчик СТ2, запись в триггер T2;
y3	сдвиг регистра RG3 влево и вычитание единицы из CT2
y4	запись в RG3;
y5	сдвиги регистров RG2,RG1, CT1+1
y6	обнулениеRG3, CT2, T1, T2
y7	вычитание единицы из CT2
y8	разрешение выдачи результата на ШиВых
y9	управление единицей переноса сумматора SM1, разрешение инверсии содержимого RG1 или RG2
y10	управление мультиплексором MS1
y11	установка триггера T1 в единицу

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

Список осведомительных сигналов приведен в таблице 3 .

Таблица 3

X	проверка наличия операндов на ШиВх;
P1= RG2[22]	анализ операнда на ноль
P2	анализ знака множителя
P3 = RG2[47]	анализ знака множимого
P4 = RG1[0]	анализ младшего разряда RG1
P5	анализ конца операции
P6	проверка временного ПРС
Р7	проверка на ПМР
Р8=RG3[47]	анализ старшего разряда RG3
Р9	проверка на ПРС
Р10	анализ старшего разряда CT2
Z	проверка возможности выдачи результата на ШиВых

3. Разработка содержательной граф-схемы алгоритма (ГСА)

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

Выполнение алгоритма начинается с проверки наличия операндов на входной шине (ШиВх) (блок 1). При появлении на ШиВх первого операнда (множитель), его мантисса заносится в регистрRG1, а в его старший (знаковый) заносится ноль, порядок же заносится в регистр RG4. В этом же такте выполняется сброс триггеров Т1, обнуление регистра RG3 и счетчика СТ2 (блок2).

После этого происходит проверка множителя на ноль (блок 3) и, если это так, выполняется завершение работы микропрограммы.

В следующем такте порядок множителя записываются в счетчик СТ2 (блок 4).

Затем происходит проверка наличия второго операнда (множимого) на ШиВх. При появлении множимого на ШиВх, его мантисса записывается в младшие разрядыRG2 (с0 по 22), а в его старший (знаковый) заносится знак, а в старшие (с 23 разряда по 47 разряд) заносятся нули, порядок же заносится в регистр RG4 (блок 6).

После этого происходит проверка множимого на ноль (блок 7) и, если это так, выполняется завершение работы микропрограммы и обнуление регистра произведения RG3, счётчика CT2 (блок 27) Если же множимое не равно нулю, то происходит проверка знака множимого (блок7).

Производится коррекция будущего псевдопроизведения. Если множимое не равно нулю, производится проверка его знака (блок8). Затем производится проверка знака множителя, сигналом р2 (блоки 9 и 10). Затем производится коррекция псевдопроизведения в соответствии с алгоритмом (блоки 11-15). Одновременно производится вычисление порядка произведения.

Затем производится проверка на ПМР (блок 16) и в случае положительного результата производится завершение работы микропрограммы с одновременным обнулением регистра RG3, CT2 (блок 27).

Производится проверка на ПРС и в случае положительного результата происходит запись в триггер Т1 и завершение работы микропрограммы. В противном случае производится анализ младшего разряда множителя осведомительным сигналом р4, определяющим, сдвигать содержимое регистров (блок 20), или же выполнять сложение с содержимым регистра RG3 и выполнением последующего сдвига (блок 19). После производится проверка конца операции умножения осведомительным сигналом р5 (блок 21). В случае завершения цикла умножения (р5=1) производится анализ старшего разряда регистра произведения RG3 на нормализованность (блок 22).

В случае нормализованности содержимого RG3 производится проверка на временное ПРС (блок 23). В случае возникновения временного ПРС производится запись в триггер Т1 и завершение работы микропрограммы (блок 24). Если же содержимое регистра RG3 не нормализовано, происходит нормализация содержимого регистра путём сдвига его на 1 разряд влево (блок 25).

После нормализации содержимого регистра RG3 производится проверка на ПМР и при положительном исходе производится обнуление регистра произведения и завершение микрооперации (блок 27).

После этого производится анализ старшего разряда счётчика и вычитание из

CT2 единицы.

После этого производится проверка возможности выдачи результата на выходную шину (блок 30). Затем происходит выдача результата на выходную шину (блок 31).

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

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

Каждой условной вершине содержательной ГСА ставится в соответствие один из входных сигналов управляющего автомата X1,…,X12, список которых приведен в таблице 5.

МК	Совокупность МО
Y1	y0, y1
Y2	y2
Y3	y2,у4,у9
Y4	y2,у4,у9,у10
Y5	y4
Y6	y5
Y7	y3
Y8	y11
Y9	y7
Y10	y8
Y11	у6

Входной сигнал УА	Логическое условие ОА
X1	X
X2	P1
X3	P2
X4	P3
X5	P4
X6	P5
X7	P6
X8	Р7
Х9	Р8
Х10	Р9
Х11	Р10
Х12	Z

В приложении В приведена разметка ГСА для модели Мили символами а0…а9 и для модели Мура символами b0…b17.

Таким образом, если строить автомат в соответствии с моделью Мили, то он будет иметь 10 состояний, а в соответствии с моделью Мура - 18 состояний.

Сравнение вариантов можно будет выполнить лишь на этапе построения функциональных схем УА, сравнив схемы по сложности и быстродействию.

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

На основе отмеченной ГСА построены граф автомата Мили и граф автомата Мура .

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

Граф автомата Мура представлен в Приложении Д. Он имеет 18 вершин, соответствующих состояниям автомата b0,b1…b17, каждое из которых определяет наборы выходных сигналов у0,у1…у11 управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.

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

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

1)Классическая структура управляющего автомата.

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

2) Модифицированная классическая структура на основе регистра и дешифратора.

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

3) Структура управляющего автомата на основе сдвигового регистра.

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

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

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

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

Особенности те же, что и у варианта 2 со счетчиком, используемым в качестве ЭП.

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

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

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

7. Кодирование состояний управляющего автомата

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

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

Для RS-триггеров, имеющих отдельные входы установки в «1» и «0» целесообразно использовать метод кодирования, минимизирующий число переключений элементов памяти, в сочетании с методом соседнего кодирования. Сигнал возбуждения подается на S-вход, если на переходе триггер требует смены состояния из «0» в «1»; сигнал возбуждения надо подавать на R-вход, если на переходе триггер требует смены состояния из «1» в «0».

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

Для кодирования состояний на D-триггерах необходимо составить инверсную таблицу переходов (таблица 6). В верхней строке данной таблицы находятся состояния, в которые осуществляется переход, во 2 строке - состояния, из которых осуществляется переход.

Состояния закодированы 4х разрядными двоичными числами.

Таблица 6

as	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
{am}	a0, a9	a0	a2, a1	a2	a3	а3,a4	a5	a6,а7	a7	a1, a3,а5,а7,а9
K(as)	0001	0011	0010	0101	0110	0100	1000	1001	1010	0000

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

Составление инверсной таблицы переходов (таблица 7) и кодирование каждого состояния 5-разрядным двоичным числом.

Таблица 7

bs

b0

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

{bm}

b0,b17

b0

b1

b2,b3

b3

b4

b4

b4

b4

b4

b9,b8,b7,b6

K(bs)

10000

00110

01001

00011

01010

01100

10001

10010

10100

11000

00100

b11

b12

b13

b14

b15

b16

b17

b10,b9,b8, b7,b6,b11

b11

b9, b11,b8,b7,b6

b1,b4,b6,b7, b8,b9,b12

b12,b11

b11, b12, b13, b14, b15, b16

b16

00001

00111

01000

00000

00101

00010

01011

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

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

Для этого составим матрицу всех существующих переходов автомата по графу модели Мили.



K(a0)=0000;K(a1)=0001;

1) ?=a2

B={1}

C1={1001;0101;0011}

D={1001;0101;0011}

K(a2)=0011;

2) ?=a9

B={0,1}

C1={1001,0101}

C0={0010,0100,1000}

D={1001,0101,0010,0100,1000}

W1001=¦0001-1001¦2+¦0000-1001¦2=1+2=3

W0101=¦0001-0101¦2+¦0000-0101¦2=1+2=3

W0010=¦0001-0010¦2+¦0000-0010¦2=2+1=3

W1001=¦0001-1001¦2+¦0000-1001¦2=1+2=3

K(a9)=1001;

3) ?=a3

B={2,9}

C2={1011,0111,0010}

C9={1101,1011,1000}

D={1011,0111,0010,1101,1000}

W1011=¦0011-1011¦2+¦1001-1011¦2=1+1=2

W0111=¦0011-0111¦2+¦1001-0111¦2=1+3=4

W0010=¦0011-0010¦2+¦1001-0010¦2=1+3=4

W1101=¦0011-1101¦2+¦1001-1101¦2=3+1=4

W1000=¦0011-1000¦2+¦1001-1000¦2=3+1=4

K(a3)=1011;

4) ?=a4

B={3}

C3={1111,1010}

D={1111,1010}

W1111=¦1011-1111¦2=1

W1010=¦1011-1010¦2=1

K(a4)=1010;

5) ?=a5

B={3,4,9}

C3={1111}

C4={0010,1000,1110}

C9={1000,1101}

D={1111,0010,1000,1110,1101}

W1111=¦1011-1111¦2+¦1010-1111¦2+¦1001-1111¦2=1+2+2=5

W0010=¦1011-0010¦2+¦1010-0010¦2+¦1001-0010¦2=2+1+3=6

W1000=¦1011-1000¦2+¦1010-1000¦2+¦1001-1000¦2=2+1+1=4

W1110=¦1011-1110¦2+¦1010-1110¦2+¦1001-1110¦2=2+1+2=6

W1101=¦1011-1101¦2+¦1010-1101¦2+¦1001-1101¦2=2+3+1=6

K(a5)=1000;

6) ?=a6

B={5}

C5={1100}

D={1100}

K(a6)=1100;

7) ?=a7

B={6,9}

C6={1101,1110,0100}

C9={1101}

D={1101,1110,0100}

W1101=¦1100-1101¦2+¦1001-1101¦2=1+1=2

W1110=¦1100-1110¦2+¦1001-1110¦2=1+3=4

W0100=¦1100-0100¦2+¦1001-0100¦2=1+3=4

K(a7)=1101;

8) ?=a8

B={7,9}

C7={0101,1111}

C9={0101,1111}

K(a8)=0101;

Результаты кодирования представлены в таблице 8.

Таблица 8

as	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
К(as)	0000	0001	0011	1011	1010	1000	1100	1101	0101	1001

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

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

Для этого составим матрицу всех существующих переходов автомата по графу модели Мура.



K(b0)=00000;

K(b1)=00001;

1) ?=b2

B={1}

C1={10001,01001,00101,00011}

D={10001,01001,00101,00011}

K(b2)=00011;

2) ?=b14

B={1}

C1={10001,01001,00101}

D={10001,01001,00101}

K(b14)=00101;

3) ?=b3

B={2}

C2={10011,01011,00111,00010}

D={10011,01011,00111,00010}

K(b3)=00010;

4) ?=b4

B={3,14}

C3={10010,01010,00110}

C14={10101,01101,00111,00100}

D={10010,01010,00110,10101,01101,0111,00100}

W10010=¦00010-10010¦2+¦00101-10010¦2=1+4=5

W01010=¦00010-01010¦2+¦00101-01010¦2=1+4=5

W00110=¦00010-00110¦2+¦00101-00110¦2=1+2=3

W10101=¦00010-10101¦2+¦00101-10101¦2=4+1=5

W01101=¦00010-01101¦2+¦00101-01101¦2=4+1=5

W00111=¦00010-00111¦2+¦00101-00111¦2=1+2=3

W00100=¦00010-00100¦2+¦00101-00100¦2=1+2=3

K(b4)=00110;

5) ?=b5

B={4}

C4={10110,01110,00100}

D={10110,01110,00100,00111}

K(b5)=10110;

6) ?=b7

B={4,14}

C4={01110,00100,00111}

C14={10101,01101,00111}

D={01110,10101,01101,00111,00100}

W01110=¦00110-01110¦2+¦00101-01110¦2=1+3=4

W10101=¦00110-00100¦2+¦00101-00100¦2=1+1=2

W10101=¦00110-10101¦2+¦00101-10101¦2=3+1=4

W01101=¦00110-01101¦2+¦00101-01101¦2=3+1=4

W00111=¦00110-00111¦2+¦00101-00111¦2=1+1=2

K(b7)=00100;

7) ?=b8

B={4,14}

C4={01110}

C14={10101,01101,00111}

D={01110,10101,01101,00111}

W01110=¦00110-01110¦2¦00101-01110¦2=1+3=4

W00111=¦00110-00111¦2¦00101-00111¦2=1+3=2

W10101=¦00110-10101¦2¦00101-10101¦2=1+3=4

W01101=¦00110-01101¦2¦00101-01101¦2=1+3=4

K(b8)=00111;

8) ?=b9

B={4,14}

C4={01110}

C14={10101,01101}

D={01110,10101,01101}

W01110=¦00110-01110¦2+¦00101-01110¦2=3+1=4

W10101=¦00110-10101¦2+¦00101-10101¦2=3+1=4

W01101=¦00110-01101¦2+¦00101-01101¦2=3+1=4

K(b9)=01110;

9) ?=b6

B={5,14}

C5={10100,10010,11110,10111}

C14={10101,01101}

D={10100,10010,11110,10111,10101,01101}

W10100=¦10110-10100¦2+¦00101-10100¦2=1+2=3

W10010=¦10110-10010¦2+¦00101-10010¦2=1+4=5

W11110=¦10110-11110¦2+¦00101-11110¦2=1+4=5

W10111=¦10110-10111¦2+¦00101-10111¦2=1+2=3

W10101=¦10110-10101¦2+¦00101-10101¦2=2+1=3

W01101=¦10110-01101¦2+¦00101-01101¦2=4+1=5

K(b6)=10100;

10) ?=b10

B={6,7,8,9}

C6={11100,10101,10000}

C7={01100}

C8={10111,01111,00011}

C9={11110,01010}



D={11100,10101,10000,01100,10111,01111,00011,11110,01010}

W11100=¦10100-11100¦2+¦00100-11100¦2+¦00111-11100¦2+¦01110-11100¦2=1+2+4+2=9

W10101=¦10100-10101¦2+¦00100-10101¦2+¦00111-10101¦2+¦01110-10101¦2=1+2+2+4=9

W10000=¦10100-10000¦2+¦00100-10000¦2+¦00111-10000¦2+¦01110-10000¦2=1+2+4+4=11

W01100=¦10100-01100¦2+¦00100-01100¦2+¦00111-01100¦2+¦01110-01100¦2=2+1+3+1=7

W10111=¦10100-10111¦2+¦00100-10111¦2+¦00111-10111¦2+¦01110-10111¦2=2+3+1+2=8

W01111=¦10100-01111¦2+¦00100-01111¦2+¦00111-01111¦2+¦01110-01111¦2=4+3+1+3=11

W00011=¦10100-00011¦2+¦00100-00011¦2+¦00111-00011¦2+¦01110-00011¦2=4+3+1+3=11

W11110=¦10100-11110¦2+¦00100-11110¦2+¦00111-11110¦2+¦01110-11110¦2=2+3+3+1=9

W01010=¦10100-01010¦2+¦00100-01010¦2+¦00111-01010¦2+¦01110-01010¦2=1+2+4+2=11

K(b10)=01100;

11) ?=b11

B{6,7,8,9,10}

C6={11100,10101,10000}

C7={-}

C8={10111,01111,00011}

C9={11110,01010}

C10={01101,01000}

D={11100,10101,10000,10111,01111,00011,11110,01010,01101}

W11100=¦10100-11100¦2+¦00100-11100¦2+¦00111-11100¦2+¦01110-11100¦2+¦01100-11100¦2=1+2+4+2+1=10

W10101=¦10100-10101¦2+¦00100-10101¦2+¦00111-10101¦2+¦01110-10101¦2+¦01100-10101¦2=1+2+2+4+3=12

W10000=¦10100-10000¦2+¦00100-10000¦2+¦00111-10000¦2+¦01110-10000¦2+¦01100-10000¦2=1+2+4+4+3=14

W10111=¦10100-10111¦2+¦00100-10111¦2+¦00111-10111¦2+¦01110-10111¦2+¦01100-10111¦2=2+3+1+3+4=13

W01111=¦10100-01111¦2+¦00100-01111¦2+¦00111-01111¦2+¦01110-01111¦2+¦01100-01111¦2=4+3+1+1+2=11

W00011=¦10100-00011¦2+¦00100-00011¦2+¦00111-00011¦2+¦01110-00011¦2+¦01100-00011¦2=4+3+1+2+4=13

W11110=¦10100-11110¦2+¦00100-11110¦2+¦00111-11110¦2+¦01110-11110¦2+¦01100-11110¦2=2+3+3+1+2=11

W01010=¦10100-01010¦2+¦00100-01010¦2+¦00111-01010¦2+¦01110-01010¦2+¦01100-01010¦2=4+3+3+1+2=13

W01101=¦10100-01101¦2+¦00100-01101¦2+¦00111-01101¦2+¦01110-01101¦2+¦01100-01101¦2=3+2+3+2+1=11

W01000=¦10100-01000¦2+¦00100-01000¦2+¦00111-01000¦2+¦01110-01000¦2+¦01100-01000¦2=3+2+4+2+1=12

K(b11)=11100;

12) ?=b13

B={6,7,8,9}

C6={10101}

C7={-}

C8={10111,01111,00011}

C9={11110,01010}

D={10101,10111,01111,00011,11110,01010}

W10101=¦10100-10101¦2+¦00100-10101¦2+¦00111-10101¦2+¦01110-10101¦2=1+2+2+4=9

W00011=¦10100-00011¦2+¦00100-00011¦2+¦00111-00011¦2+¦01110-00011¦2=4+3+1+3=11

W10111=¦10100-10111¦2+¦00100-10111¦2+¦00111-10111¦2+¦01110-10111¦2=2+3+1+3=9

W01111=¦10100-01111¦2+¦00100-01111¦2+¦00111-01111¦2+¦01110-01111¦2=4+3+1+1=9

W11110=¦10100-11110¦2+¦00100-11110¦2+¦00111-11110¦2+¦01110-11110¦2=2+3+3+1=9

W01010=¦10100-01010¦2+¦00100-01010¦2+¦00111-01010¦2+¦01110-01010¦2=4+3+2+1=10

K(b13)=10101;

13) ?=b12

B={11,14}

C11={11101,11110,11000}

C14={01101}

D={11101,11110,11000,01101}

W11101=¦11100-11101¦2+¦00101-11101¦2=1+2=3

W11110=¦11100-11110¦2+¦00101-11110¦2=1+4=5

W11000=¦11100-11000¦2+¦00101-11000¦2=1+4=5

W01101=¦11100-01101¦2+¦00101-01101¦2=1+2=3

K(b12)=11101;

14) ?=b15

B={11,12}

C11={11110,11000}

C12={11111,11001,01101}

D={11110,11000,11111,11001,01101}

W11110=¦11100-11110¦2+¦11101-11110¦2=1+2=3

W11000=¦11100-11000¦2+¦11101-11000¦2=1+2=3

W11111=¦11100-11111¦2+¦11101-11111¦2=2+1=3

W11001=¦11100-11001¦2+¦11101-11001¦2=2+1=3

W01101=¦11100-01101¦2+¦11101-01101¦2=2+1=3

K(b15)=11110;

15) ?=b16

B={11,12,13,15}

C11={11000}

C12={11111,11001,01101}

C13={10111,10001}

C15={11010}



D={11000,11111,11001,01101,10111,10001,11010}

W11000=¦11100-11000¦2+¦11101-11000¦2+¦10101-11000¦2+¦11110-11000¦2=1+2+3+2=8

W10111=¦11100-10111¦2+¦11101-10111¦2+¦10101-10111¦2+¦11110-10111¦2=3+2+1+2=8

W10001=¦11100-10001¦2+¦11101-10001¦2+¦10101-10001¦2+¦11110-10001¦2=3+2+1+4=10

W11111=¦11100-11111¦2+¦11101-11111¦2+¦10101-11111¦2+¦11110-11111¦2=2+1+2+1=6

W11001=¦11100-11001¦2+¦11101-11001¦2+¦10101-11001¦2+¦11110-11001¦2=2+1+2+2=7

W01101=¦11100-01101¦2+¦11101-01101¦2+¦10101-01101¦2+¦11110-01101¦2=2+1+2+3=8

W11010=¦11100-11010¦2+¦11101-11010¦2+¦10101-11010¦2+¦11110-11010¦2=2+3+4+1=10

K(b16)=11111;

16) ?=b17

B={16,0}

C0={10000,01000}

C16={01111,10111,11011}

D={10000,01000,01111,10111,11011}

W10000=¦11111-10000¦2+¦00000-10000¦2=4+1=5

W01000=¦11111-01000¦2+¦00000-01000¦2=4+1=5

W01111=¦11111-01111¦2+¦00000-01111¦2=4+1=5

W10111=¦11111-10111¦2+¦00000-10111¦2=4+1=5

W11011=¦11111-11011¦2+¦00000-11011¦2=4+1=5

K(b17)=10000;

Результаты кодирования представлены в таблице 9.

Таблица 9

bs	b0	b1	b2	b3	b4	b5	b6	b7	b8
K(bs)	00000	00001	00011	00010	00110	10110	10100	00100	00111
bs	b9	b10	b11	b12	b13	b14	b15	b16	b17
K(bs)	01110	01100	11100	11101	10101	00101	11110	11111	10000

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

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

Таким образом, коды состояний автомата представлены в таблице 10.

Таблица 10

as	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
К(as)	0001	0010	0011	0100	0101	0110	0111	1000	1001	0000

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

8.1 Прямая структурная таблица переходов автомата Мили при кодировании на D-триггерах

Таблица 11

Исходное состояние am	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходной сигнал Y(am,as)	Функция возбуждения D-триггеров
a0	0001	a0 a1	0001 0011	x1	- y0,y1	D4 D3D4
a1	0011	a2 a9	0010 0000	x2	y2 y6	D3 -
a2	0010	a2 a3	0010 0101	x1	- y1	D3 D2D4
a3	0101	a4 a5 a5 a5 a9	0110 0100 0100 0100 0000	x2x4x3 x2x4x3 x2x4x3 x2x4x3 x2	y2,y4,y9 y2,y4,y9 y2,y4,y9 y2 y6	D2D3 D2 D2 D2 -
a4	0110	a5	0100	-	y2,y4,y9,y10	D2
a5	0100	a6 a6 a9 a9	1000 1000 0000 0000	x8x10x5 x8 x8x10	- y4 y6 y11	D1 D1 - -
a6	1000	a7	1001	-	y5	D1D4
a7	1001	a6 a6 a8 a9 a9 a9	1000 1000 1010 0000 0000 0000	x6x5 x5x6 x6x9 x6x9x7 x6x9x7x11 x6x9x7x11	y4 - y3 y11 - y7	D1 D1 D1D3 - - -
a8	1010	a9 a9 a9	0000 0000 0000	x8 x8x11 x8x11	y6 y7 -	- - -
a9	0000	a9 a0	0000 0001	x12 x12	- y8	- D4

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

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

D1=a5x8x10 v a6 v a7x6 v a7x6x9

D2=a2x1 v a3x2 v a4

D3=a0x1 v a1x2 v a2x1 v a3x2x4x3 v a7x6x9

D4=a0 v a2x1 v a6 v a9x12

y0=a0x1

y1=a0x1 v a2x1

y2=a1x2 v a3x2 v a4

y3=a7x6x9

y4=a3x2 v a4 v a5x8x10x5 v a7x6x5

y5=a6

y6=a1x2 v a3x2 v a5x8 v a8x8

y7=a7x6x9x7x11 v a8x8x11

y8=a9x12

y9=a3x2 v a4

y10=a4

y11=a5x8x10 va7x6x9x7

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

D1=h v a6 v j v k (4)

D2=e v g (2)

D3=c v d v a2x1 v fx4x3 v k (10)

D4=a0 v c v a6 v m (4)

y0=c (0) c=a0x1(2)

y1=c v e (2) d=a1x2(2)

y2=d v g(2) e=a2x1(2)

y3=k (0) f=a3x2 (2)

y4=g v hx5 v jx5 (7) h=a5x8x10(3)

y5=a6 (0) k=a7x6x9 (3)

y6=a1x2 v a3x2 v a8x8 v a5x8(12)l=a7x6x9 (3)

y7=lx7x11 v a8x8x11 (8) j=a7x6(2)

y8=m(0)

y9=g (0) m=a9x12(2)

y10=a4 (0)g=e v a4 (2)

y11=a5x8x10 vlx7 (7)

Цена комбинационной схемы по Квайну= 23+20+38=81

Начальная установка: входы дешифратора-4

количество инверсий-7

КС для управления записью-5

входы элементов памяти-7

ошибка-6

Общая цена комбинационной схемы по Квайну: 81+4+7+7+5+6=110

8.2 Прямая структурная таблица переходов автомата Мура при кодировании на D-триггерах

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

Таблица 12

Исходное состояние bm	Выходной сигнал Y(bm,bs)	Код bm	Состояние перехода bs	Код bs	Входной сигнал X(bm,bs)	Функция возбуждения D-триггеров
b0	-	10000	b0 b1	10000 00110	x1	D1 D3D4
b1	y0,y1	00110	b2 b14	10001 00000	x2 x2	D2D5 -
b2	y2	01001	b3	00011	1	D4D5
b3	-	00011	b3 b4	00011 01010	x1	D4D5 D2D4
b4	y1,у12	01010	b5 b7 b8 b9 b14	01100 10010 10100 11000 00000	x4x3 x2x4x3 x2x4x3 x2x4x3 x2	D2D3 D1D4 D1D3 D1D2 -
b5	y2,y4,y9	01100	b6	00000	1	D1D5
b6	y2,y4,y9,y10	10001	b10 b11 b13 b14	00100 00001 01000 00000	x8x10x5 x8x10x5 x8x10 x8	D3 D5 D2 -
b7	y2,y4,y9	10010	b10 b11 b13 b14	00100 00001 01000 00000	x8x10x5 x8x10x5 x8x10 x8	D3 D5 D2 -
b8	y2,y4,y9	10100	b10 b11 b13 b14	00000 00001	x8x10x5 x8x10x5 x8x10 x8	D3 D5 D2 -
b9	y2	11000	b10 b11 b13 b14	10100 00100 00010	x8x10x5 x8x10x5 x8x10 x8	D3 D5 D2 -
b10	y4	00100	b11	11000	1	D5
b11	y5	00001	b10 b11 b12 b13 b15 b16	01000 10000 00100	x6x5 x6x5 x6x9 x6x9x7 x6x9x7x11 x6x9x7x11	D3 D5 D3D4D5 D2 D3D5 D4
b12	y3	00111	b14 b15 b16	00000 00001	x8x11 x8x11	- D3D5 D4
b13	y11	01000	b16	10011	1	D4
b14	y6	00000	b16	00010	1	D4
b15	y7	00101	b16	00010	1	D4
b16	-	00010	b16 b17	00010 01011	x12 x12	D4 D2D4D5
b17	y8	01011	b0	00101	1	D1

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

D1=b0x1 v b4x2 v b5 v b17

D2=b1x2 v b3x1 v b4x2 v b6x8x10 v b7x8x10 v b8x8x10 v b9x8x10 v b11x6x9x7 v b16x12

D3=b0x1 v b4x2x3 v b6x8x10x5 v b7x8x10x5 v b8x8x10x5 v b9x8x10x5 v b11x6x5 v b11x6x9 v b11x6x9x7x11 v b12x8x11

D4=b0x1 v b2 v b3 v b4x2x4x3 v b11x6x9 v b11x6x9x7x11 v b12x8x11 v b13 v b14 v b15 v b16

D5=b1x2 v b2 v b3x1 v b5 v b6x8x10x5 v b7x8x10x5 v b8x8x10x5 v b9x8x10x5 v b10 v b11x6x5 v b11x6x9 v b11x6x9x7x11 v b12x8x11 v b16x12

Так как для автомата Мура:

y0=b1

y1=b1 v b4

y2=b2 v b5 v b6 v b7 v b8 v b9

y3=b12

y4=b5 v b6 v b7 v b8 v b10

y5=b11

y6=b14

y7=b15

y8=b17

y9=b5 v b6 v b7 v b8

y10=b6

y11=b13

у12=b4После минимизации (выделения общих частей) полученной системы логических выражений для функций возбуждения элементов памяти и функций выходов получаются следующие выражения:

D1=b0x1 v f v b5 v b17 (6)

D2=d v b3x1 v f v gx10 v hx10 v ex10 v ix10 v px7 v l (21)

D3=c v fx3 v sx5 v ax5 v ox5 v qx5 v nx5 v j v k v r (22)

D4=c v b2 v b3 v fx4x3 v j v px7x11 v mx11 v b13 v b14 v b15 v b16 (19)

D5=d v b2 v b3x1 v b5 v sx5 v ax5 v ox5 v qx5 v b10 v nx5 v j v k v r v l (26)

y0=b1 (0)c=b0x1 (2)

y1=b1 v b4 (0)d=b1x2(2)

y2=b2 v b5 v b6 v b7 v b8 v b9 (6)f=b4x2 (2)

y3=b12 (0)g=b6x8 (2)

y4=b5 v b6 v b7 v b8 v b10 (5)h=b7x8 (2)

y5=b11 (0)e=b8x8 (2)

y6=b14 (0)i=b9x8 (2)

y7=b15 (0)j=b11x6x9 (3)

y8=b17 (0)k=b11x6x9x7x11 (5)

y9=b5 v b6 v b7 v b8 (4) l=b16x12 (2)

y10=b6 (0)m=b12x8 (2)

y11=b13 (0)n=b11x6 (2)

у12=b4(0) p=b11x6x9 (3)

s=gx10 (2)

a=hx10 (2)

o=ex10 (2)

q=ix10 (2)

Цена комбинационной схемы по Квайну= 41+ 21+ 22+ 19+ 26+ 6+ 15=150;

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

Таблица 13

Исходное состояние am	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходной сигнал Y(am,as)	Функция возбуждения RS-триггеров
a0	0000	a0 a1	0000 0001	x1 x1	- y0,y1	- S4
a1	0001	a2 a9	0011 1001	x2 x2	y2 y6	S3 S1
a2	0011	a2 a3	0011 1011	x1 x1	- y1	- S1
a3	1011	a4 a5 a5 a5 a9	1010 1000 1000 1000 1001	x2x4x3 x2x4x3 x2x4x3 x2x4x3 x2	y2,y4,y9 y2,y4,y9 y2,y4,y9 y2 y6	R4 R3R4 R3R4 R3R4 R3
a4	1010	a5	1000	1	y2y4y9y10	R3
a5	1000	a6 a6 a9 a9	1100 1100 1001 1001	x8x10x5 x8x10x5 x8 x8x10	- y4 y6 y11	S2 S2 S4 S4
a6	1100	a7	1101	1	y5	S4
a7	1101	a6 a6 a8 a9 a9 a9	1100 1100 0101 1001 1001 1001	x6x5 x6x5 x6x9 x6x9x7x11 x6x9x7x11 x6x9x7	y4 - y3 - y7 y11	R4 R4 R1 R2 R2 R2
a8	0101	a9 a9 a9	1001 1001 1001	x8 x8x11 x8x11	y6 y7 -	S1R2 S1R2 S1R2
a9	1001	a9 a0	1001 0000	x12 x12	- y8	- R1R4

Формируются логические выражения для функций возбуждения RS-триггеров:

S1=a1x2 v a2x1 v a8

S2=a5x8x10

S3=a1x2

S4=a0x1 v a5x8 v a5x8x10 v a6

R1=a7x6x9 v a9x12

R2=a7x6x9 v a8

R3=a3 v a4

R4=a3x2 v a7x6 v a9x12

y0=a0x1

y1=a0x1 v a2x1

y2=a1x2 v a3x2 v a4

y3=a7x6x9

y4=a3x2 v a4 v a5x8x10x5 v a7x6x5

y5=a6

y6=a1x2 v a3x2 v a8x8 v a5x8

y7=a7x6x9x7x11 v a8x11

y8=a9x12

y9=a3x2 v a4

y10=a4

y11=a5x8x10 va7x6x9x7

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

S1=e v f v a8 (3)

S2=j (0)

S3=d (0)

S4=c v m v k v a6 (4)

R1=p v n (2)

R2=l v a8 (2)

R3=a3 v a4 (2)

R4=g v q v n (3)

y0=c (0) c=a0x1 (2)

y1=c v f (2) d=a1x2 (2)

y2=d v h (2) e=a1 (2)

y3=p (3) f=a2x1 (2)

y4=h v jx5 v qx5 (7) g=a3x2 (2)

y5=a6(0) j=a5x8x10 (3)

y6=a3x2 v e v a8x8 v m (8) q=a7x6 (2)

y7=lx7x11 v a8x8x11 (8) l=a7x6x9 (2)

y8=n (0) n=a9x12 (2)

y9=h (0) p=a7x6x9 (2)

y10=a4 (0) h=g v a4 (2)

y11=kvlx7 (4) m=a5x8 (2)

k=a5x8x10 (3)

Цена комбинационной схемы по Квайну: С=18+25+38=77;

Начальная установка: входы дешифратора-4

количество инверсий-7

КС для управления записью-8

количество входов элементов памяти-8

ошибка-6

Общая цена комбинационной схемы по Квайну: 77+8+8+7+4+6=110

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

Таблица 14

Исходное состояние bm	Выходной сигнал Y(bm,bs)	Код bm	Состояние перехода bs	Код bs	Входной сигнал X(bm,bs)	Функция возбуждения RS-триггеров
b0	-	00000	b0 b1	00000 00001	x1 x1	- S5
b1	y0,y1	00001	b2 b14	00011 00101	x2 x2	S4 S3
b2	y2	00011	b3	00010	1	R5
b3	-	00010	b3 b4	00010 00110	x1 x1	- S3
b4	y1,у12	00110	b5 b7 b8 b9 b14	10110 00100 00111 01110 00101	x4x3 x2x4x3 x2x4x3 x2x4x3 x2	S1 S4 S5 S2 R4S5
b5	y2,y4,y9	10110	b6	10100	1	S4
b6	y2,y4,y9,y10	10100	b10 b11 b13 b14	01100 11100 10101 00101	x8x10x5 x8x10x5 x8x10 x8	R1S2 S2 S5 R1S5
b7	y2,y4,y9	00100	b10 b11 b13 b14	01100 11100 10101 00101	x8x10x5 x8x10x5 x8x10 x8	R1S2 S2 S5 R1S5
b8	y2,y4,y9	00111	b10 b11 b13 b14	01100 11100 10101 00101	x8x10x5 x8x10x5 x8x10 x8	R1S2 S2 S5 R1S5
b9	y2,y4,y9	01110	b10 b11 b13 b14	01100 11100 10101 00101	x8x10x5 x8x10x5 x8x10 x8	R1S2 S2 S5 R1S5
b10	y2	01100	b11	11100	1	S1
b11	y5	11100	b10 b11 b12 b13 b15 b16	01100 11100 11101 10101 11110 11111	x6x5 x6x5 x6x9 x6x9x7 x6x9x7x11 x6x9x7x11	R1 - S5 R2S5 S4 S4S5
b12	y3	11101	b14 b15 b16	01100 11110 11111	x8x11 x8x11	S1S2 S4R5 S4
b13	y11	10101	b16	11111	1	S2S4
b14	y6	00101	b16	11111	1	S1S2S4
b15	y7	11110	b16	11111	1	S5
b16	-	11111	b16 b17	11111 10000	x12 x12	- R2R3R4R5
b17	y8	10000	b0	00000	1	R1

Формируются логические выражения для функций возбуждения RS-триггеров:

S1=b4x2x4x3 v b10 v b12x8 v b14

S2=b4x2x4x3 v b6x8x10 v b7x8x10 v b8x8x10 v b9x8x10 v b12x8 v b13 v b14

S3=b1x2 v b3x1

S4=b1x2 v b4x2x4x3 v b5 v b11x6x9x7 v b12x8 v b13 v b14

S5=b0x1 v b4x2x4x3 v b4x2 v b6x8x10 v b6x8 v b7x8x10 v b7x8 v b8x8x10 v b8x8 v b9x8x10 v b9x8 v b11x6x9 v b11x6x9x7x11 v b12x8x11 v b15

R1=b6x8x10x5 v b6x8 v b7x8x10x5 v b7x8 v b8x8x10x5 v b8x8 v b9x8x10x5 v b9x8 v b11x6x5 v b17

R2=b11x6x9x7 v b16x12

R3=b16x12

R4=b4x2 v b16x12

R5=b2 v b4x2 v b16x12

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

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

Таблица 15

Исходное состояние am	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходной сигнал Y(am,as)	Функция возбуждения
a0	0001	a0 a1	0001 0010	x1 x1	- y0,y1	- E+1
a1	0010	a2 a9	0011 0000	x2 x2	y2 y6	E+1 R
a2	0011	a2 a3	0011 0100	x1 x1	- y1	- E+1
a3	0100	a4 a5 a5 a5 a9	0101 0110 0110 0110 0000	x2x4x3 x2x4x3 x2x4x3 x2x4x3 x2	y2,y4,y9 y2y4y9 y2y4y9 y2 y6	E+1 EWR D2D3 EWR D2D3 EWR D2D3 R
a4	0101	a5	0110	1	y2,y4,y9,y10	E+1
a5	0110	a6 a6 a9 a9	0111 0111 0000 0000	x8x10x5 x8x10x5 x8 x8x10	- y4 y6 y11	E+1 E+1 R R
a6	0111	a7	1000	1	y5	E+1
a7	1000	a6 a6 a8 a9 a9 a9	0111 0111 1001 0000 0000 0000	x6x5 x6x5 x6x9 x6x9x7 x6x9x7x11 x6x9x7x11	y4 - y3 y11 - y7	E-1 E-1 E+1 R R R
a8	1001	a9 a9 a9	0000 0000 0000	x8 x8x11 x8x11	y6 y7 -	R R R
a9	0000	a9 a0	0000 0001	x12 x12	- y8	- E+1

Формируются логические выражения для функций возбуждения счетчика:

E+1=a0x1 v a1x2 v a2x1 v a3x2x3x4 v a4 v a6 v a5x8x10 v a7x6x9 v a9x12

E-1=a7x6

R=a1x2 v a3x2 v a5x8 v a5x8x10 v a7x6x9 v a8

D2=a3x2

D3=a3x2

y0=a0x1

y1=a0x1 v a2x1

y2=a1x2 v a3x2 v a4

y3=a7x6x9

y4=a3x2 v a4 v a5x8x10x5 v a7x6x5

y5=a6

y6=a1x2 v a3x2 v a8x8 v a5x8

y7=a7x6x9x7x11 v a8x8x11

y8=a9x12

y9=a3x2 v a4

y10=a4

y11=a5x8x10 va7x6x9x7

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

E+1=c v d v e v a3x2x4x3 v a4 v a6 v j v r v n (13)

E-1=m(0)

R=s v p v h v k v l v a8 (6)

EWR=D2=D3=f (0)

y0=c (0) c=a0x1 (2)

y1=c v e (2) d=a1x2 (2)

y2=d v g (2) s=a1x2 (2)

y3=n (0) e=a2x1(2)

y4=g v jx5 v mx5 (7) f=a3x2 (2)

y5=a6 (0) h=a3x2 (2)

y6=h v s v a8x8 v l (6)l=a5x8 (2)

y7=px7x11 v a8x8x11 (8) j=a5x8x10 (3)

y8=r (0) n=a7x6x9 (3)

y9=g (0) p=a7x6x9 (3)

y10=a4 (0) m=a7x6 (2)

y11=k v px7 (4) r=a9x12 (2)

g=fva4 (2)

k=a5x8x10 (3)

Цена комбинационной схемы по Квайну: С=32+29+19=80;

Начальная установка: входы дешифратора-4

количество инверсий-7

входы счётчика-8

КС для управления записью-2

ошибка-6

Общая цена комбинационной схемы по Квайну: 80+8+4+7+2+6=107

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

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

Из трёх вариантов реализации автомата по модели Мили на D-триггерах, RS-триггерах и счетчике наименьшей сложностью комбинационной схемы обладает управляющий автомат, который использует в качестве элементов памяти счётчик (цена по Квайну = 107). Поэтому построение функциональной схемы будет выполняться в соответствии с моделью Мили, использующей в качестве элементов памяти счётчик.

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

Заключение

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

Перечень используемых сокращений

микропрограммный автомат двоичный код

ГСА - граф-схема алгоритма;

ФСА - функциональная схема алгоритма;

УА - управляющий автомат;

ОА -операционный автомат;

ПРС - переполнение разрядной сетки;

ПМР - потеря младших разрядов;

ПЗ - плавающая запятая;

ПК - прямой код;

ДК - дополнительный код;

ОК - обратный код;

ЛУ - логическое условие;

МПА - микропрограммный автомат;

МК - микрокоманда;

МО - микрооперация;

ШиВх - входная шина;

ШиВых - выходная шина;

Список используемой литературы

1. В.Ю. Мельцов, Т.Р.Фадеева. Синтез микропрограммных управляющих автоматов. Учебное пособие. Киров, 2010 год.

2. Курс лекций по дисциплине “Теория автоматов”.

3. Курс лекций по дисциплине “Информатика”.

4. Курс лекций по дисциплине “Дискретная математика”.

Приложение А

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

(обязательное)

Приложение Б

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

(обязательное)

Приложение В

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

(обязательное)

Приложение Г

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

Приложение Д

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

Приложение Е

Структурная схема управляющего автомата

(обязательное)

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