РефератыИнформатикаСиСинтез микропрограммного управляющего автомата

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

Министерство общего и профессионального образования РФ


Вятский государственный технический университет


Факультет автоматики и вычислительной техники


Кафедра электронных вычислительных машин


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


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


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


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


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


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


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


ТПЖА.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 Описание используемого алгоритма умножения


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


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 = 10012
, Апк
= 0,1001, Адк
= 0,1001


B = 13= 11012
, Впк
= 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 = 11101012


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


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


B =13= 11012
, Впк
= 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 = -11101012


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


A =9 = 10012
, Апк
= 0,1001, Адк
= 0,1001


B =-13= -11012
, Впк
= 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 = -11101012


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


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


B =-13=-11012
, Впк
= 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 = -11101012


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 - SMp
=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 приведена разметка ГСА для модели Мили символами a0
,а1
,...,а9
и для модели Мура - символами b0
,b1
,...,b12
. Таким образам, если строить управляющий МПА в соответствии с моделью Мили, то он будет иметь 10 состояний, а в соответствии с моделью Мура - 13 состояний.


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


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


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


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


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


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


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


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


























































































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

Код am


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

Код as


Входной сигнал X(am
,as
)
Выходные сигналы Y(am
,as
)

Функции


возбуждения


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 состояний (a0
,…, a10
) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце as
таблицы 7, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу 8, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.


Таблица 8


























As
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9
{am
}
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, стараясь, насколько возможно, использовать соседние с as
коды для состояний, находящихся в одном столбце таблицы 7.


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


Таблица 9


























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

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


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


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


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
и Di
. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.






00 k0
=0000


01 k1
=0001


12


19 12 B2 ={0001}


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


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


34 W0011
=1


39 W0101
=1


45 W1001
=1


56 k2
=0011


67


78


80


88


89


99



23 B3={0011}


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


39 D3={0010,0111,1011}


W0010
=1


W0111
=1


W1011
=1


k3
=0010






34 B4={0 010}


M4= 45 C3={0110,1010}


D4={0110,1010}


W0110
=1


W1010
=1


k4
=0110


45 B5={0110}


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


75 D5={0100,0111,1110}


W0100
=1


W0111
=1


W1110
=1


k5
=0111



56 B6={0111}


M6= 67 C5={0101,1111)}


D6={0101,1111)}


W0101
=1


W1111
=1


k6
=0101






67 B7={0111,0101}


M7= 75 C5={1111}


78 C6={0100,1101}


D7={1111,0100,1101}


W1111
=ô1111-0111ô2
+ô1111-0101ô2
=1+2=3


W0100
=ô0100-0111ô2
+ô0100-0101ô2
=2+1=3


W1101
=ô1101-0111ô2
+ô1101-0101ô2
=2+1=3


k7
=0100


78 B8={0000,0100}


M8= 80 C0={1000}


88 C7={1100}


89 D8={1000,1100}


W1100
=ô1100-0000ô2
+ô1100-0100ô2
=2+1=3


W1000
=ô1000-0000ô2
+ô1000-0100ô2
=1+2=3


k8
=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}












































DB 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

k9
=1000


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


Таблица 10


























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

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


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


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







































































































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

Код am


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

Код as


Входной сигнал X(am
,as
)
Выходные сигналы Y(am
,as
)
Функции возбуждения триггеров
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


























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

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


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


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


























































































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

Код am


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

Код as


Входной сигнал X(am
,as
)
Выходные сигналы Y(am
,as
)
Функции возбуждения
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 получаются логические выражения для каждой функции возбуждения управляющего входа счётчика,а также для функций выходов как конъюнкции соответствующих исходных состояний am
и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.


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=log2
16).


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


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


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


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


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


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


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

















































































































Исходное состояние bm
Выходные сигналы

Код


bm


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

Код


bs


Входной сигнал Функции возбуждения 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 состояний (b0
, b1
, ... , b1
2
) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце bs
таблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.


Таблица 16




































bs
b0 b1 b2 b3 b4 b5 b6 B7
{bm
}
b0b8b9b11 b0 b1 b2b3 b2b3 b4 b4b5 b4b5b6b8
bs
b8 b9 b10 b11 b12
{bm
}
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
и Di
. Код с наименьшей суммой и является наиболееоптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.






00 k0
=0000


01


12 k1
=0001


1 12


23 12 B2 ={0001}


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


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


34 W0011
=1


45 W0101
=1


46 W1001
=1


47 k2
=0011


48


4 12 23 B3={0011}


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


57 34 D3={0010,0111,1011}


58 W0111
=1


67 W0010
=1


68 W1011
=1


78 k3
=0010


80


87 24 B4={0011,0010}


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


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


8 10 M4= 46 W0111
=3


8 11 47 W1011
=3


90 48 W0110
=3


99 4 12 W1010
=3


9 10 k4
=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 W0100
=1


12 11W0111
=1


W1110
=1


k5
=0100


46 B6={0110,0100}


M6= 56 C4={0111,1110}


67 C5={0101,1100}


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



























DB 0110 0100 W
0111 1 2 3
1110 1 2 3
0101 2 1 3
1100 2 1 3

k6
=0101






47 B7={0110,0100,0101}


57 C4={0111,1110}


M7= 67 C5={1100}


78 C6={0111,1101}


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
































DB 0110 0100 0101 W
0111 1 2 1 4
1110 1 2 3 6
1100 2 1 2 5
1101 3 2 1 6

k7
=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}


89


8 10


8 11


















































DB 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

k8
=1100






90 B9={0000,1100}


89 C0={1000}


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


9 10 D9={1000,1101,1110}


9 11 k9
=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



























DB 1100 1000 W
1101 1 2 3
1110 1 2 3
1001 2 1 3
1010 2 1 3

k10
=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}






























DB 0000 1100 1000 1110 W
1001 2 2 1 3 8
1010 2 2 1 1 6
1101 3 1 2 2 8

k11
=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}






























DB 0001 0110 1110 1010 W
1001 1 4 3 2 10
1111 3 2 1 2 8
1011 2 3 2 1 8

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


















































































































Исходное состояние bm
Выходные сигналы

Код


bm


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

Код


Bs


Входной сигнал Функции возбуждения 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=log2
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.


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


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


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


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


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


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


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


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


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


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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Синтез микропрограммного управляющего автомата

Слов:8160
Символов:96210
Размер:187.91 Кб.