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

ДОПУСКАЮ К ЗАЩИТЕ

Руководитель работы _______ О.А. Залетов

СИНТЕЗ МИКРОПРОГРАММНОГО

УПРАВЛЯЮЩЕГО АВТОМАТА

Пояснительная записка

курсовой работы

по теории автоматов

ТПЖА.220100.22.29 ПЗ

Разработал студент гр. ВМ-22 ( _______ ) Р.В. Гонта

Проверил преподаватель кафедры ЭВМ ( _______ ) О.А. Залетов

Нормоконтролер ( _______ ) В.Ю. Мельцов

Председатель комиссии ( _______ ) В.Д. Матвеев

Члены комиссии ( _______ ) В.Ю. Мельцов

Работа защищена с оценкой ( _______ )

1999

Содержание

Введение 1 Постановка задачи 2 Описание используемого алгоритма умножения 2.1 Алгоритм умножения чисел в форме с ПЗ с простой коррекцией 2.2 Алгоритм умножения первым способом 3 Ручной подсчет 4 Выбор и описание структурной схемы ОА 5 Реализация содержательной ГСА 6 Построение отмеченной ГСА 7 Синтез МПА в соответствии с моделью Мили 7.1 Построение графа автомата 7.2 Построение прямой структурной таблицы переходов и выходов 7.3 Кодирование на D-триггерах 7.4 Получение логических выражений для функций возбуждения D-триггеров и функций выходов 7.5 Кодирование на RS-триггерах 7.6 Получение логических выражений для функций возбуждения RS-триггеров 7.7 Кодирование на T-триггерах 7.8 Получение логических выражений для функций возбуждения T-триггеров 7.9 Кодирование на счетчике 7.10 Получение уравнений для счетчика 8 Синтез МПА в соответствии с моделью Мура 8.1 Построение графа автомата 8.2 Построение прямой структурной таблицы переходов и выходов 8.3 Кодирование на D-триггерах 8.4 Получение логических выражений для функций возбуждения D-триггеров и функций выходов 8.5 Кодирование на RS- триггерах 8.6 Получение логических выражений для функций возбуждения RS- триггеров и функций выходов 9 Построение функциональной схемы микропрограммного управляющего автомата Заключение Библиографический список Перечень сокращений

УДК 681.3

Реферат

Гонта Р.В. Синтез микропрограммного управляющего автомата. Курсовая работа / ВятГТУ, каф. ЭВМ, рук. О.А. Залетов – Киров, 1999. Гр. ч. 3 л. ф. А2

ОПЕРАЦИОННЫЙ АВТОМАТ, МИКРОПРОГРАММНЫЙ УПРАВЛЯЮЩИЙ АВТОМАТ , ГРАФ-СХЕМА АЛГОРИТМА, ГРАФ, ФУНКЦИОНАЛЬНАЯ СХЕМА, МОДЕЛЬ МИЛИ, МОДЕЛЬ МУРА

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

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

Введение

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

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

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

Функциональную схему устройства построить в основном логическом базисе. Операнды разрядностью 4 байта (тридцать два разряда) поступают по входной шине (ШИВх) в дополнительном коде (ДК), результат также в ДК выводится по выходной шине (ШИВых). В младших 24 разрядах операнда хранится мантисса со знаком, а в следующих 8 разрядах - характеристика.

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

Процесс умножения состоит из последовательности операций сложения и сдвигов.

2.1 Алгоритм умножения чисел в форме с ПЗ с простой коррекцией

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

2. Перемножить модули мантисс сомножителей по правилам с ФЗ:

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

Правила введения коррекции при умножении чисел в ДК:

- Если сомножители положительны, коррекции нет.

- Если один из сомножителей отрицателен, к псевдопроизведению надо прибавить ДК от модуля положительного сомножителя.

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

2.2. Перемножить модули сомножителей, представленных в ДК, одним из четырех способов получить псевдопроизведение.

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

4. Нормализовать мантиссу результата и выполнить округление если необходимо.

2.2 Алгоритм умножения первым способом

Умножение с младших разрядов множителя со сдвигом частных сумм вправо.

В каждом такте цикла умножения первым способом необходимо:

2.1 Сложить множимое с предыдущей частной суммой, если очередной разряд множителя равен 1, и результат (новую частную сумму) запомнить; в случае если очередной разряд множителя равен 0 суммирование не выполнять;

2.2 Уменьшить вдвое частную сумму, что равносильно сдвигу ее на один разряд вправо.

3 Ручной подсчет

Выполним ручной подсчет в соответствии с выше указанным алгоритмом.

В качестве множителя возьмём число 9, а в качестве множимого 13.

3.1 Сомножители положительные (A>0, B>0)

A = 9 = 1001₂, А_пк = 0,1001, А_дк = 0,1001

B = 13= 1101₂, В_пк = 0,1101, В_дк = 0,1101

3.1.1 Определим знак произведения: 0 + 0 = 0

3.1.2 Перемножим модули сомножителей:

Таблица 1

Множимое	Множитель	Сумматор	Пояснения
0,1101	0,1001	0,00000000 0, 11010000 0,11010000	Сложение
		0,01101000	Сдвиг
	0,0100	0,00110100	Сдвиг
	0,0010	0,00011010	Сдвиг
	0,0001	0,00011010 0,11010000 0,11101010	Сложение
		0,01110101	Сдвиг

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

3.1.3 Коррекция не нужна, так как оба множителя положительные.

3.1.4 Присвоение произведению знака:

(A*B)_дк=0,01110101

(A*B)_пк=0,01110101

A*B = (9)*(13) = 117 = 1110101₂

3.2 Сомножители разных знаков (А<0, B>0)

A =-9=-1001₂, А_пк = 1,1001, А_дк = 1,0111

B =13= 1101₂, В_пк = 0,1101, В_дк = 0,1101

3.2.1 Определим знак произведения: 1 + 0 = 1

3.2.2 Перемножим модули сомножителей:

Таблица 2

Множимое	Множитель	Сумматор	Пояснения
0,1101	0,0111	0,00000000 0, 11010000 0,11010000	Сложение
		0,01101000	Сдвиг
	0,0011	0,01101000 0,11010000 1,00111000	Сложение
		0,10011100	Сдвиг
	0,0001	0,10011100 0,11010000 1,01101100	Сложение
		0,10110110	Сдвиг
	0,0000	0,01011011	Сдвиг

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

3.2.3 Произведём коррекцию (прибавим к псевдопроизведению В_дк):

0,01011011

В_дк= 0,001 1 0000

0,10001011

3.2.4 Присвоение произведению знака:

(A*B)_дк=1,10001011

(A*B)_пк=1,01110101

A*B = (-9)*(13) = -117 = -1110101₂

3.3 Сомножители разных знаков (А>0, B<0)

A = 9 = 1001₂, А_пк = 0,1001, А_дк = 0,1001

B =-13= -1101₂, В_пк = 1,1101, В_дк = 1,0011

3.3.1 Определим знак произведения: 0 + 1 = 1

3.3.2 Перемножим модули сомножителей:

Таблица 3

Множимое	Множитель	Сумматор	Пояснения
0,0011	0,1001	0,00000000 0, 00110000 0,00110000	Сложение
		0,00011000	Сдвиг
	0,0100	0,00001100	Сдвиг
	0,0010	0,00000110	Сдвиг
	0,0001	0,00000110 0, 0 011 00 00 0,00110110	Сложение
		0,00011011	Сдвиг

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

3.3.3 Произведём коррекцию (прибавим к псевдопроизведению A_дк):

0,00011011

А_дк= 0, 011 10000

0,10001011

3.3.4 Присвоение произведению знака:

(A*B)_дк=1,10001011

(A*B)_пк=1,01110101

A*B = (9)*(-13) = -117 = -1110101₂

3.4 Сомножители отрицательные (A<0, B<0)

A = -9= -1001₂, А_пк = 1,1001, А_дк = 1,0111

B =-13=-1101₂, В_пк = 1,1101, В_дк = 0,0011

3.4.1 Определим знак произведения: 1 + 1 = 0

3.4.2 Перемножим модули сомножителей:

Таблица 4

Множитель	Множитель	Сумматор	Пояснения
0,0011	0,0111	0,00000000 0, 0011 0000 0,00110000	Сложение
		0,00011000	Сдвиг
	0,0011	0,00011000 0,00110000 0,01001000	Сложение
		0,00100100	Сдвиг
	0,0001	0,00100100 0,00110000 0,01010100	Сложение
		0,00101010	Сдвиг
	0,0000	0,00010101	Сдвиг

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

3.4.3 Произведём коррекцию (прибавим к псевдопроизведению B_пк_,а затем A_пк):

0,00010101

В_пк= 0, 1101 0000

0,11100101

A_пк= 0, 1 00 1 0000

0,01110101

3.4.4 Присвоение произведению знака:

(A*B)_дк=0,01110101

(A*B)_пк=0,01110101

A*B = (-9)*(-13) = 117 = -1110101₂

4 Выбор и описание структурной схемы операционного автомата (ОА)

ОА должен содержать:

- регистры RG1, RG2 для приема мантисс операндов с ШИВх;

- регистр RG3 и счетчик CT1 для приема характеристик с ШИВх;

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

- комбинационные сумматоры SM;

- счетчик CT2 для подсчета тактов умножения;

- три сумматора по модулю 2 для получения обратного кода множимого и определения ПРС;

- триггер T1 для хранения знака результата;

- схему конъюнкции;

- триггер T2 для фиксации ПРС;

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

Операнды поступают в операционный автомат по 32-разрядной шине ШИВх. Перед началом умножения необходимо обнулить регистр частных сумм RG4, так как именно с него поступает информация на плечо A в SM, в счетчик CT2 необходимо занести “001001”, а триггер T1 сбросить. Операнды поступают в дополнительном коде. Сначала мантисса множителя записывается в RG1 и RG2, а его характеристика в RG3 и CT1. Мантисса первого операнда преобразуется в ДК с помощью схемы сложения по модулю 2 и сумматора и заносится в RG4. Затем записываются мантисса и характеристика множимого в RG2 и CT1 соответственно. После анализа знаков операндов произведем коррекцию, если это необходимо. Если знаковый разряд множимого (p2) равен 0, то обнуляем RG4. Если знаковый разряд множителя (p1) равен 1, то в RG4 заносим информацию с плеча S сумматора. После проведения коррекции начинается процесс получения псевдопроизведения. В процессе умножения происходят сдвиги регистров RG1 и RG4, а также увеличение счетчика CT2. Кроме того производится анализ младшего разряда RG1 (p4). Если он равен 1 тогда в RG4 заносим информацию с плеча S сумматора. Получение псевдопроизведения происходит до тех пор пока 5-й разряд в счетчике CT2 не окажется равным “1”. Далее производится анализ старшего разряда мантиссы результата. Если он равен “0” – требуется нормализация. Нормализация осуществляется путем сдвига RG4 влево и уменьшеня счетчика CT1. Характеристика произведения получается обычным сложением характеристик операндов, причем старший разряд характеристики у множителя подается инверсным на плечо сумматора A. Перед выдачей результата на ШИВых содержимое RG3, T1 и информация с плеча S сумматора SM2 подается на усилитель-формирователь.

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

y1 - запись в RG1,

запись в RG3,

сброс T1,

занесение “001001” в CT2;

y2 - запись в RG2,

запись в CT1,

разрешить запись в T1;

y3 - обнуление RG4;

y4 - запись в RG4;

y5 - CT2:=CT2+1,

сдвинуть вправо RG1:=0.R1(RG1),

сдвинуть вправо RG4:=0.R1(RG4);

y6 - SM_p=1 – подача “1” на вход переноса сумматора,

управление совокупностью схем сложения по модулю 2;

y7 - CT1:=CT1-1,

сдвиг влево RG4:=L1(RG4).0;

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

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

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

p1 - знак операнда в RG1;

p2 - знак операнда в RG2;

p3 - проверка на наличие нулевого операнда в RG2;

p4 - проверка очередной цифры множителя;

p5 - проверка условия выхода из цикла;

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

p7 - проверка условия ПРС;

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

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

5 Реализация содержательной ГСА

Содержательная граф-схема алгоритма представлена на рисунке 2. Выполнение алгоритма начинается с проверки наличия операндов на ШИВх (блоки 1 и 5). При поступлении первого операнда происходит его занесение в RG1, RG2, RG3 и CT1, а также обнуление RG4, занесение “001001” в CT2 и сброс триггеров T1 и T2 (блок 2). Затем в регистр RG4 поступает ДК от первого операнда (блок 4). При поступлении второго операнда происходит его занесение в RG2 и CT1 (блок 6). После каждого занесения производится анализ p3. Если хотя бы в одном случае p3=1 (блоки 3 и 7), значит операнд равен нулю и значит необходимо обнулить RG4, RG3, CT1, T1 (блок 19) и перейти к блоку 20. В противном случае продолжается процесс коррекции. Если p2=0 (блок 8) тогда обнуляется регистр RG4 (блок 9). Если p1=1 (блок 10) тогда получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 11).

Далее получается псевдопроизведение. Если p4=0 (блок 12), тогда получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 13). В любом случае выполняется блок сдвигов (блок 14): содержимое RG1 и RG4 сдвигаются вправо, CT2 увеличивается на “1“. Далее проверяется p5 (блок 15) - условие выхода из цикла. Если p5=1, цикл завершается, иначе переход к блоку 12.

Затем производится нормализация. Если p6=0 (блок 16), то выполняется блок сдвигов (блок 18): содержимое RG4 сдвигается влево, CT2 уменьшается на “1“.

При сложении характеристик одинакового знака возможно переполнение разрядной сетки (ПРС). Если p7=1 (блок 17), возникло ПРС и операция умножения завершается.

Затем результат при Z=1 (блок 21) будет передан по ШИВых (блок 22) в другие устройства.

6 Построение отмеченной ГСА

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

Таблица 5

MK	Совокупность МО
Y1	y1,y2,y3
Y2	y2
Y3	y3
Y4	y4
Y5	y5
Y6	y4,y6
Y7	y7
Y8	y8
Y9	y1,y3

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

Таблица 6

Входной сигнал УА	X1	X2	X3	X4	X5	X6	X7	X8	X9
Логическое условие ОА	X	p3	p2	p1	p4	p5	p6	p7	Z

Далее в полном соответствии с содержательной ГСА строим отмеченную ГСА (рисунок 3), условным вершинам которой приписывается один из входных сигналов УА (x1,...,x9), а операторным вершинам - одна из МК (в скобках указана совокупность МО для каждой МК). Выделение состояний управляющего МПА возможно в соответствии с моделью Мили или моделью Мура.

На рисунке 3 приведена разметка ГСА для модели Мили символами a₀,а₁,...,а₉ и для модели Мура - символами b₀,b₁,...,b₁₂. Таким образам, если строить управляющий МПА в соответствии с моделью Мили, то он будет иметь 10 состояний, а в соответствии с моделью Мура - 13 состояний.

Замечание. В двух вершинах ожидания (5 и 20) при разметке по Муру введены фиктивные состояния автомата b₃ и b₁₀.

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

7 Синтез МПА в соответствии с моделью Мили

7.1 Построение графа автомата

На основе отмеченной ГСА построен граф автомата Мили (рисунок 4). Граф автомата Мили имеет 10 вершин, соответствующих состояниям автомата а₀, а₁,...,а₉, дуги его отмечены входными сигналами, действующими на каждом переходе (числитель), и набором выходных сигналов, вырабатываемых УА на данном переходе (знаменатель).

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

7.2 Построение структурной таблицы переходов и выходов

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

Исходное состояние	Код a_m	Состояние перехода a_s	Код a_s	Входной сигнал X(a_m,a_s)	Выходные сигналы Y(a_m,a_s)	Функции возбуждения D-триггеров
a0	0001	a0 a1	0001 0011	X1 X1	- Y1(y1,y2,y3)	D4 D3D4
a1	0011	a2 a9	0010 0000	X2 X2	Y6(y4,y6) Y9(y1,y3)	D3
a2	0010	a2 a3	0010 0110	X1 X1	- Y2(y2)	D3 D2D3
a3	0110	a4 a4 a9	1100 1100 0000	X2X3 X2X3 X2	- Y3(y3) Y9(y1,y3)	D1D2 D1D2
a4	1100	a5 a5	0100 0100	X4 X4	- Y6(y4,y6)	D2 D2
a5	0100	a6 a6	0101 0101	X5 X5	- Y4(y4)	D2D4 D2D4
a6	0101	a7	1001	1	Y5(y5)	D1D4
a7	1001	a5 a8	0100 1000	X6 X6	- -	D2 D1
a8	1000	a0 a8 a9	0001 1000 0000	X7X8 X7 X7X8	- Y7(y7) -	D4 D1
a9	0000	a0 a9	0001 0000	X9 X9	- Y8(y8)	D4

7.3 Кодирование на D-триггерах

При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремится использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 10 состояний (a₀,…, a₁₀) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце a_s таблицы 7, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу 8, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.

Таблица 8

A_s	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
{a_m}	A0a8a9	a0	a1a2	a2	a3	a4a7	a5	a6	a7a8	a1a3a8a9

Наибольшее количество переходов в состояние a9 - закодируем его кодом К(a9)=0000. Состояниям a0, a2, a5, a8 назначим коды с одной "1": K(a0) =0001, К(a2) =0010, К(a5)=0100, К(a8)=1000. Для кодирования других состояний будем использовать слова с двумя "1" в кодовом слове, К(a1)=0011, К(a3)=0110, К(a4)=1100, К(a6)=0101, К(a7)=1001, стараясь, насколько возможно, использовать соседние с a_s коды для состояний, находящихся в одном столбце таблицы 7.

Кодирования для D-триггеров изображены в таблице 9.

Таблица 9

A_s	a0	a1	a2	a3	a4	a5	a6	a7	a8	A9
K{a_s}	0001	0011	0010	0110	1100	0100	0101	1001	1000	0000

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

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

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

D1= a3x2va6va7x6va8x7

D2= a2x1va3x2va4va5va7x6

D3= a0x1va1x2va2

D4= a0va5va6va8x7x8va9x9

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

y1= a0x1va1x2va3x2

y2= a0x1va2x1

y3= a0x1va1x2va3x2x3va3x2

y4= a1x2va4x4va5x5

y5= a6

y6= a1x2va4x4

y7= a8x7

y8=a9x9

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

m=a1x2va4x4

n=a0x1

k=nva1x2va3x2

p=a8x7

q=a2x1

r=a3x2

D1= r v y5 v a7x6 v y7

D2= q v r v a4 v a5 v a7x6

D3= n v y6 v a2

D4= a0 v a5 v y5 v a8x7x8 v a9x9

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

y1= k

y2= n v q

y3= k v rx3

y4= m v a5x5

y5= a6

y6= m

y7= p

y8=a9x9

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

7.5 Кодирование на RS- триггерах

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

Для этого сначала выпишем матрицу M - матрицу всех возможных переходов автомата. Состояниям автомата a0 и a1 присвоим коды: К(a0)=0000, К(a1)=0001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C1 коды с кодовым расстоянием "1" от кодов В2. Закодировав состояние a2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния a3 аналогично a2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами В_i и D_i. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.

00 k₀=0000

01 k₁=0001

19 12 B2 ={0001}

22 M2= 22 C1={0011,0101,1001}

M= 23 23 D2={0011,0101,1001}

34 W₀₀₁₁=1

39 W₀₁₀₁=1

45 W₁₀₀₁=1

56 k₂=0011

23 B3={0011}

M3= 34 C2={0010,0111,1011}

39 D3={0010,0111,1011}

W₀₀₁₀=1

W₀₁₁₁=1

W₁₀₁₁=1

k₃=0010

34 B4={0 010}

M4= 45 C3={0110,1010}

D4={0110,1010}

W₀₁₁₀=1

W₁₀₁₀=1

k₄=0110

45 B5={0110}

M5= 56 C4={0100,0111,1110}

75 D5={0100,0111,1110}

W₀₁₀₀=1

W₀₁₁₁=1

W₁₁₁₀=1

k₅=0111

56 B6={0111}

M6= 67 C5={0101,1111)}

D6={0101,1111)}

W₀₁₀₁=1

W₁₁₁₁=1

k₆=0101

67 B7={0111,0101}

M7= 75 C5={1111}

78 C6={0100,1101}

D7={1111,0100,1101}

W₁₁₁₁=ô1111-0111ô²+ô1111-0101ô²=1+2=3

W₀₁₀₀=ô0100-0111ô²+ô0100-0101ô²=2+1=3

W₁₁₀₁=ô1101-0111ô²+ô1101-0101ô²=2+1=3

k₇=0100

78 B8={0000,0100}

M8= 80 C0={1000}

88 C7={1100}

89 D8={1000,1100}

W₁₁₀₀=ô1100-0000ô²+ô1100-0100ô²=2+1=3

W₁₀₀₀=ô1000-0000ô²+ô1000-0100ô²=1+2=3

k₈=0100

19 B9={0000,0001,0010,1100}

39 C0={1000}

M9= 89 C1={1001} C3={1010}

90 C8={1000,1101,1110}

99 D9={1000,1001,1010,1101,1110}

D\B	0000	0001	0010	1100	W
1000	1	2	2	1	6
1001	2	1	3	2	8
1010	2	3	1	2	8
1101	3	2	4	1	10
1110	3	4	2	1	10

k₉=1000

Кодирования для RS-триггеров изображены в таблице 10.

Таблица 10

A_s	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
K{a_s}	0000	0001	0011	0010	0110	0111	0101	0100	1100	1000

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

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

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

Исходное состояние	Код a_m	Состояние перехода a_s	Код a_s	Входной сигнал X(a_m,a_s)	Выходные сигналы Y(a_m,a_s)	Функции возбуждения триггеров
Исходное состояние	Код a_m	Состояние перехода a_s	Код a_s	Входной сигнал X(a_m,a_s)	Выходные сигналы Y(a_m,a_s)	RS	T
a0	0000	a0 a1	0000 0001	X1 X1	- Y1(y1,y2,y3)	S4	T4
a1	0001	a2 a9	0011 1000	X2 X2	Y6(y4,y6) Y9(y1,y3)	S3 S1R4	T3 T1T4
a2	0011	a2 a3	0011 0010	X1 X1	- Y2(y2)	R4	T4
a3	0010	a4 a4 a9	0110 0110 1000	X2X3 X2X3 X2	- Y3(y3) Y9(y1,y3)	S2 S2 S1R3	T2 T2 T1T3
a4	0110	a5 a5	0111 0111	X4 X4	- Y6(y4,y6)	S4 S4	T4 T4
a5	0111	a6 a6	0101 0101	X5 X5	- Y4(y4)	R3 R3	T3 T3
a6	0101	a7	0100	1	Y5(y5)	R4	T4
a7	0100	a5 a8	0111 1100	X6 X6	- -	R3R4 S1	T3T4 T1
a8	1100	a0 a8 a9	0000 1100 1000	X7X8 X7 X7X8	- Y7(y7) -	R1R2 R2	T1T2 T2
a9	1000	a0 a9	0000 1000	X9 X9	- Y8(y8)	R1	T1

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

S1= a1x2 v a3x2 v a7x6

S2= a3x2

S3= a1x2

S4= a0x1 v a4

R1= a8x7x8 v a9x9

R2= a8x7

R3= a3x2 v a5 v a7x6

R4= a1x2 v a2x1 v a6 v a7x6

После упрощения и выделения общих частей, получим:

f= a1x2

g= a3x2

k= a7x6

m= a8x7

p= a3x2

q= a1x2

r= a0x1

h= a2x1

e= r v a1x2 v g

n= q v a4x4

S1= f v g v a7x6

S2= p

S3= q

S4= r v a4

R1= mx8 v a9x9

R2= m

R3= g v a5 v k

R4= f v h v a6 v k

y1= e

y2= r v h

y3= e v px3

y4= n v a5x5

y5= a6

y6= n

y7= a8x7

y8=a9x9

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

7.7 Кодирование на T-триггерах

В качестве элементов памяти возможно использование не только D-триггеров и RS-триггеров, а также используются T-триггеры. При использовании T-триггеров используется такая же кодировка, как и для RS-триггеров. Кодирования для T-триггеров изображены в таблице 10.

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

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

T1= a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9

T2= a3x2 v a8x7

T3= a1x2 v a3x2 v a5 v a7x6

T4= a0x1 v a4 v a1x2 v a2x1 v a6 v a7x6

После упрощения и выделения общих частей, получим:

f= a1x2

g= a3x2

k= a7x6

m= a8x7

p= a3x2

q= a1x2

r= a0x1

h= a2x1

e= r v a1x2 v g

n= q v a4x4

i= r v h

T1= f v g v a7x6 v mx8 v a9x9

T2= p v m

T3= q v g v a5 v k

T4= i v a4 v f v a6 v k

y1= e

y2= i

y3= e v px3

y4= n v a5x5

y5= a6

y6= n

y7= a8x7

y8=a9x9

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

7.9 Кодирование на счетчике

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

Таблица 12

A_s	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
K{a_s}	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

7.10 Получение уравнений для счетчика

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

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

Исходное состояние	Код a_m	Состояние перехода a_s	Код a_s	Входной сигнал X(a_m,a_s)	Выходные сигналы Y(a_m,a_s)	Функции возбуждения
a0	0000	a0 a1	0000 0001	X1 X1	- Y1(y1,y2,y3)	E+1
a1	0001	a2 a9	0010 1001	X2 X2	Y6(y4,y6) Y9(y1,y3)	E+1 D1D8 M
a2	0010	a2 a3	0010 0011	X1 X1	- Y2(y2)	E+1
a3	0011	a4 a4 a9	0100 0100 1001	X2X3 X2X3 X2	- Y3(y3) Y9(y1,y3)	E+1 E+1 D1D8 M
a4	0100	a5 a5	0101 0101	X4 X4	- Y6(y4,y6)	E+1 E+1
a5	0101	a6 a6	0110 0110	X5 X5	- Y4(y4)	E+1 E+1
a6	0110	a7	0111	1	Y5(y5)	E+1
a7	0111	a5 a8	0101 1000	X6 X6	- -	D1D4 M E+1
a8	1000	a0 a8 a9	0000 1000 1001	X7X8 X7 X7X8	- Y7(y7) -	M E+1
a9	1001	a0 a9	0000 1001	X9 X9	- Y8(y8)	M

M – вход управления записью / счётом в счётчике;

E+1 - вход управления прямым счётом;

Работа счётчика производится в соответствии с таблицей 14.

Таблица 14

М	E+1	Режим
0 1 1 1	0 1 0 0	Запись в счётчик Прямой счёт Обратный счёт Хранение

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

M = a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9

E+1 = a0x1 v a1x2 v a2x1 v a3x2 v a4 v a5 v a6 v a7x6 v a8x7x8

D1 = a1x2 v a3x2 v a7x6

D4 = a7x6

D8 = a1x2 v a3x2

y1 = a0x1 v a1x2 v a3x2

y2 = a0x1 v a2x1

y3 = a0x1 v a1x2 v a3x2x3 v a3x2

y4 = a1x2 v a4x4 v a5x5

y5 = a6

y6 = a1x2 v a4x4

y7 = a8x7

y8 =a9x9

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

e=a1 v a3 d=x1(a0 v a2) f=a0x1

h=x2e g=a1x2 v a4x4 p=a8x7

r=f v h q=a7x6 n=h v q

M = n v px8 v a9x9

E+1 = d v x2e v a4 v a5 v a6 v a7x6 v px8

D1 = n

D4 = q

D8 = h

y1 = r

y2 = d

y3 = r v a3x2x3

y4 = g v a5x5

y5 = a6

y6 = g

y7 = a8x7

y8 =a9x9

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

Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=10), а n наименьшее число ЭП (n=log₂16).

Сравнивая относительно аппаратурных затрат варианты построения автомата Мили на RS, D, T- триггерах и на счетчике можно убедиться что цена логических выражений для функций возбуждения оказывается приблизительно равной: для RS цена - 59, для D цена – 59, для T цена 61, а для счетчика 57.

8 Синтез МПА в соответствии с моделью Мура

8.1 Построение графа автомата.

На основе отмеченной ГСА построен граф автомата Мура (рисунок 5).Граф автомата Мура имеет 11 вершин, соответствующих состояниям автомата b₀,b₁,...,b₁₀, каждое из которых определяет наборы выходных сигналов, управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.

8.2 Построение структурной таблицы переходов.

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

Исходное состояние b_m	Выходные сигналы	Код b_m	Состояние перехода b_s	Код b_s	Входной сигнал	Функции возбуждения D-триггеров
b0	-	0001	b0 b1	0001 0111	X1 X1	D4 D2D3D4
b1	y1,y2,y3	0111	b2 b12	1110 0011	X2 X2	D1D2D3 D3D4
b2	y4,y6	1110	b3 b4	1010 0110	X1 X1	D1D3 D2D3
b3	-	1010	b3 b4	1010 0110	X1 X1	D1D3 D2D3
b4	y2	0110	b5 b6 b7 b8 b12	1100 0101 0010 0000 0011	X2X3 X2X3X4 X2X3X4X5 X2X3X4X5 X2	D1D2 D2D4 D3 D3D4
b5	y3	1100	b6 b7 b8	0101 0010 0000	X4 X4X5 X4X5	D2D4 D3
b6	y4,y6	0101	b7 b8	0010 0000	X5 X5	D3
b7	y4	0010	b8	0000	1
b8	y5	0000	b0 b7 b8 b9 b10 b11	0001 0010 0000 1001 0100 1000	X6X7X8 X6X5 X6X5 X6X7 X6X7X8X9 X6X7X8X9	D4 D3 D1D4 D2 D1
b9	y7	1001	b0 b9 b10 b11	0001 1001 0100 1000	X7X8 X7 X7X8X9 X7X8X9	D4 D1D4 D2 D1
b10	-	0100	b10 b11	0100 1000	X9 X9	D2 D1
b11	y8	1000	b0	0001	1	D4
b12	y1,y3	0011	b10 b11	0100 1000	X9 X9	D2 D1

8.3 Кодирование на D-триггерах

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

При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремиться использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 13 состояний (b₀, b₁, ... , b₁₂) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце b_s таблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.

Таблица 16

b_s	b0	b1	b2	b3	b4		b5	b6		B7
{b_m}	b0b8b9b11	b0	b1	b2b3	b2b3		b4	b4b5		b4b5b6b8
b_s	b8	b9	b10			b11			b12
{b_m}	b4b5b6b7b8	b8b9	b8b9b10b12			b8b9b10b12			b1b4

Коды состояний автомата определим по выше описанному методу кодирования состояний при использовании D-триггеров.

Таблица 17

b	b0	b1	b2	b3	b4	b5	b6
K(b)	0001	0111	1110	1010	0110	1100	0101
b	b7	b8	b9	b10	b11	b12
K(b)	0010	0000	1001	0100	1000	0011

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

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

D1= b1x2 v b2x1 v b3x1 v b4x2 v b8x6x7 v b8x6x7x8x9 v b9x7 v b10x9 v b12x9

D2= b0x1 v b1x2 v b2x1 v b3x1 v b4x2(x3 v x3x4) v b5x4 v b8x6x7x8x9 v b9x7x8x9 v b10x9 v

v b12x9

D3= b0x1 v b1 v b2 v b3 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b8x6x4

D4= b0 v b1x2 v b4x2x3x4 v b4x2 v b5x4 v b8x6(x7x8 v x7) v b9(x7x8 v x7) v b11

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

y1= b1 v b12

y2= b1 v b4

y3= b1 v b5 v b12

y4= b2 v b6 v b7

y5= b8

y6= b2 v b6

y7= b9

y8=b11

Выделив общие части получаем:

d=b2 v b6

g=b0x1

h=b1x2

i=b4x2

j=x4x5

k=b4x2x3

m=b8x6

n=x7x8

r=b2 v b3

q=mvb9

D1= h v x1r v k v m(x7 v nx9) v b9x7 v b10x9 v b12x9

D2= g v h v x1r v i(x3 v x3x4) v b5x4 v nx9q v x9(b10 v b12)

D3= g v b1 v r v j(k v b5) v x5(b6 v b8x6)

D4= b0 v x2(b1 v b4) v x4(k v b5) v (x7x8 v x7)q v b11

y4= d v b7

y6= d

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

8.5 Кодирование на RS-триггерах

Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Для этого сначала выпишем матрицу М - матрицу всех возможных переходов автомата. Состояниям автомата b0 и b1 присвоим коды: К(b0)=0000, К(b1)=0001. Далее из матрицы М составим подматрицу М2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C0 и C1 коды с кодовым расстоянием "1" от кодов В2. Для матрицы М2 не имеет значения какой из кодов выбрать, пусть кодом b2 будет 0011. Закодировав состояние b2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния b3 аналогично b2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами В_i и D_i. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.

00 k₀=0000

12 k₁=0001

1 12

23 12 B2 ={0001}

24 M2= 23 C1={0011,0101,1001}

M= 33 24 D2={0011,0101,1001}

34 W₀₀₁₁=1

45 W₀₁₀₁=1

46 W₁₀₀₁=1

47 k₂=0011

4 12 23 B3={0011}

56 M3= 33 C2={0010,0111,1011}

57 34 D3={0010,0111,1011}

58 W₀₁₁₁=1

67 W₀₀₁₀=1

68 W₁₀₁₁=1

78 k₃=0010

87 24 B4={0011,0010}

88 34 C2={0111,1011} C3={0110,1010}

89 45 D4={0111,1011, 0110,1010}

8 10 M4= 46 W₀₁₁₁=3

8 11 47 W₁₀₁₁=3

90 48 W₀₁₁₀=3

99 4 12 W₁₀₁₀=3

9 10 k₄=0110

9 11

10 10 45 B5={0110}

10 11 M5= 56 C4={0100,0111,1110}

11 0 57 D5={0100,0111,1110}

12 10 58 W₀₁₀₀=1

12 11 W₀₁₁₁=1

W₁₁₁₀=1

k₅=0100

46 B6={0110,0100}

M6= 56 C4={0111,1110}

67 C5={0101,1100}

68 D6={0111,1110,0101,1100}

D\B	0110	0100	W
0111	1	2	3
1110	1	2	3
0101	2	1	3
1100	2	1	3

k₆=0101

47 B7={0110,0100,0101}

57 C4={0111,1110}

M7= 67 C5={1100}

78 C6={0111,1101}

87 D7={0111,1110,1100,1101}

D\B	0110	0100	0101	W
0111	1	2	1	4
1110	1	2	3	6
1100	2	1	2	5
1101	3	2	1	6

k₇=0111

80 B8={0000,0110,0100,0101,0111}

48 C0={1000}

58 C4={1110}

68 C5={1100}

M8= 78 C6={1101}

87 C7={1111}

88 D8={0000,1110,1100,1101,1111}

8 10

8 11

D\B	0000	0110	0100	0101	0111	W
1000	1	3	2	3	4	13
1110	3	1	2	3	2	11
1100	2	2	1	2	3	10
1101	3	3	2	1	2	11
1111	4	2	3	2	1	12

k₈=1100

90 B9={0000,1100}

89 C0={1000}

M9= 99 C8={1000,1101,1110}

9 10 D9={1000,1101,1110}

9 11 k₉=1000

8 10 B10={1100,1000}

9 10 C8={1101,1110}

M10= 10 10 C9={1001,1010}

10 11 D10={1101,1110,1001,1010}

12 10

D\B	1100	1000	W
1101	1	2	3
1110	1	2	3
1001	2	1	3
1010	2	1	3

k₁₀=1110

11 0 B11={0000,1100,1000,1110}

8 11 C0={1001,1010} C8={1101}

M11= 9 11 C9={1001,1010}

10 11 C10={1010}

12 11 D11={1001,1010,1101}

D\B	0000	1100	1000	1110	W
1001	2	2	1	3	8
1010	2	2	1	1	6
1101	3	1	2	2	8

k₁₁=1010

1 12 B12={0001,0110,1110,1010}

M12= 4 12 C1={1001} C4={1111}

12 10 C10={1111}

12 11 C11={1011}

D12={1001,1111,1011}

D\B	0001	0110	1110	1010	W
1001	1	4	3	2	10
1111	3	2	1	2	8
1011	2	3	2	1	8

k₁₂=1011

Кодирования для RS-триггеров изображены в таблице 18.

Таблица 18

b	b0	b1	b2	b3	b4	b5	b6
K(b)	0000	0001	0011	0010	0110	0100	0101
b	b7	b8	b9	b10	b11	b12
K(b)	0111	1100	1000	1110	1010	1011

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

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

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

Исходное состояние b_m	Выходные сигналы	Код b_m	Состояние перехода b_s	Код B_s	Входной сигнал	Функции возбуждения D-триггеров
b0	-	0000	b0 b1	0000 0001	X1 X1	S4
b1	y1,y2,y3	0001	b2 b12	0011 1011	X2 X2	S3 S1S3
b2	y4,y6	0011	b3 b4	0010 0110	X1 X1	R4 S2R4
b3	-	0010	b3 b4	0010 0110	X1 X1	S2
b4	y2	0110	b5 b6 b7 b8 b12	0100 0101 0111 1100 1011	X2X3 X2X3X4 X2X3X4X5 X2X3X4X5 X2	R3 R3S4 S4 S1R3 S1R2S4
b5	y3	0100	b6 b7 b8	0101 0111 1100	X4 X4X5 X4X5	S4 S3S4 S1
b6	y4,y6	0101	b7 b8	0111 1100	X5 X5	S3 S1R4
b7	y4	0111	b8	1100	1	S1R3R4
b8	y5	1100	b0 b7 b8 b9 b10 b11	0000 0111 1100 1000 1110 1010	X6X7X8 X6X5 X6X5 X6X7 X6X7X8X9 X6X7X8X9	R1R2 R1S3S4 R2 S3 R2S3
b9	y7	1000	b0 b9 b10 b11	0000 1000 1110 1010	X7X8 X7 X7X8X9 X7X8X9	R1 S2S3 S3
b10	-	1110	b10 b11	1110 1010	X9 X9	R2
b11	y8	1010	b0	0000	1	R1R3
b12	y1,y3	1011	b10 b11	1110 1010	X9 X9	R2S4 R4

S1= b1x2 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b7

S2= b2x1 v b3x1 v b9x7x8x9 v b12x9

S3=b1 v b5x4x5 v b6x5 v b8x6x5 v b8x6x7x8 v b9x7x8

S4= b0x1 v b4x2x3x4 v b4x2x3x4x5 v b4x2 v b5x4 v b5x4x5 v b8x6x5

R1= b8x6x7x8 v b8x6x5 v b9x7x8 v b11

R2= b4x2 v b8x6x7x8 v b8x6x7 v b8x6x7x8x9 v b10x9

R3= b4x2x3 v b4x2x3x4 v b4x2x3x4x5 v b7 b11

R4= b6x5 v b2 v b7 vb12

Упростив и выделив общие части получаем:

d=b4x2

q=b4x2

e=qx3

r=x4x5

f=b5r

g=b6x5

s=b8x6

m=x7x8

h=sm

i=b8x6x5

j=b8x6x7x8

k=b9x7x8

n=x4x5

p=b2 v b7

S1= b1x2 v en v d v b5n v g v b7

S2= x1(b2 v b3) v x9(k v b12)

S3= b1 v f v b6x5 v i v j v k

S4= b0x1 v e(x4 v r) v d v b5x4

R1= h v i v b9m v b11

R2= d v h v sx7 v x9(j v b10)

R3= qx3 v e(x4 v n) v b7 v b11

R4= g v p v b12

y1= b1 v b12

y2= b1 v b4

y3= b1 v b5 v b12

y4= p v b6

y5= b8

y6= b2 v b6

y7= b9

y8=b11

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

Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=13), а n наименьшее число ЭП (n=log₂16).

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

Сравнивая относительно аппаратурных затрат варианты построения автомата Мура на RS и D-триггерах можно убедиться что цена логических выражений для функций возбуждения ЭП отличается не на много: для RS цена - 114, для D цена - 109.

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

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

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

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

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

Заключение

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

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

Библиографический список

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

2. Т.Р.Фадеева. Синтез Микропрограммного управляющего автомата. Методические указания к курсовой работе. Киров, 1989 год.

3. Б.М.Каган. Электронные вычислительные машины и системы. М.: Энергоатомиздат, 1985.

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

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Минск: ВМ, 1980.

Перечень сокращений

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

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

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

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

ФЗ - фиксированная запятая,

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

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

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

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

Дата добавления: 2019-07-15; просмотров: 257; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!