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

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

Министерство образования и науки РФ

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

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

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

Пояснительная записка к курсовой работе

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

Киров, 2011

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

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

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

. Алгоритм умножения двоичных чисел III сп. в ДК с простой коррекцией

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

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

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

. Перед циклом умножения произвести коррекцию.

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

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

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

. Произвести анализ цифры очередного разряда множителя.

. Произвести суммирование множимого с суммой частичных произведений (ЧП), если цифра множителя «1», иначе перейти к п.7 алгоритма.

. Произвести сдвиг множителя и суммы ЧП на один разряд влево.

. Присвоить модулю произведения знак из п.1 данного алгоритма.

3. Численные примеры

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

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

1. Представим числа отрицательными.

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= -36 = 100100₂, В_пк = 1,100100, В_дк = 1,011100.

Таблица 1.

Получили результат: 0,011110111100

= (-55)*(-36) = 1980 = 11110111100₂

.Представим числа таким образом: А<0, B>0

= -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 2.

Получили результат: 0,100001000100

(A*B)_дк=1,100001000100 , (A*B)_пк=1,011110111100

P = (-55)*36 = -1980 = -11110111100₂

.Представим числа положительными:

= 55 = 110111₂, А_пк = 0,110111, А_дк = 0,110111= 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 3.

Получили результат: 0,011110111100

Коррекция не нужна, получаем результат:

=55*36 = 1980 = 11110111100₂

. Выбор и описание структурной схемы операционного автомата

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

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

регистр RG3 для записи и хранения результата и частных сумм,

комбинационный сумматор SM,

счетчик СТ для подсчета тактов умножения,

схему дизъюнкции,

схема "сложение по модулю 2" для реализации инверсии;

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

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

Операнды поступают в операционный автомат по 32-разрядной шине ШИВх и записываются в соответствующие регистры. Мантисса множителя записывается в RG1, а мантисса множимого в RG2. Операнды поступают в дополнительном коде. Сначала анализируются знаки операндов. Знак результата определяется с помощью схемы “сложения по модулю 2” и подается на усилитель-формирователь. Зная знаки операндов, произведем коррекцию, если это необходимо. Для этого в зависимости от p₃ и p₁ на плечо A сумматора поступает информация с выхода триггера RG3 или на плечо В с выхода RG2. На плечо B поступает информация либо с прямых, либо с инверсных выходов триггера RG2. Множимое, в зависимости от очередной цифры множителя, либо суммируется с предыдущей частной суммой, либо суммирование не происходит. Цикл сложения выполняется до тех пор пока в шестом разряде счетчика СТ не окажется "1". Перед выдачей результата на ШИВых содержимое RG3 и подается на усилитель-формирователь.

Таким образом, для выполнения операции умножения из управляющего автомата (УА) в операционный автомат необходимо подать управляющие сигналы, реализующие следующие микрооперации:- запись в RG1, запись в СТ, запись в Т;- сдвиг RG1 влево RG1:=L1(RG1).0, сдвиг RG3 влево

:=L1(RG3).0, СТ: = СТ+1;

- запись в RG2;- инверсия выхода RG2 и SM_p=1 - подача “1” на вход переноса сумматора;- сброс RG3;- запись в RG3;- обнуление счётчика;- управление выдачей информации на ШИВых;- очистка RG1; - очистка RG2.

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

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

Р1- знак операнда RG1;

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

Р3 - знак операнда RG2,

Р4=1, выполнения цикла сложения завершено;=0, один из операндов равен “0”;

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

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

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

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

Выполнение алгоритма начинается с проверки наличия множителя на ШИВх. Он заносится в RG1, RG2, логическим условием P5 проверяется осведомительный сигнал, если он равен “1”, то поступил не нулевой операнд, иначе алгоритм заканчивается и результат умножения равен “0”. Далее с инверсных выходов RG2 множитель подаётся на плечо В сумматора SM, где получается ДК, а затем заносится в RG3. Далее происходит проверка наличия множимого на ШИвх и занесение его в RG2 с последующей проверкой на “0” и подачей на плечо В сумматора SM. Также в счетчик тактов заносится 1, знак произведения определяется путём сложения по модулю 2 знаков множителя и множимого.

Далее, следуя алгоритму, логическим условием P3 проверяется знак множимого, если он равен “1”, то логическим условием Р1 проверяется знак множителя и в зависимости от его знака на плечо А сумматора SM поступают данные, записанные в RG3 или происходит проверка очередной цифры множителя. Если ли знак множимого равен “0”, то RG3 очищается и происходит проверка знака множителя логическим условием Р1. Далее проверяется очередная цифра множителя логическим условием Р2, если он равен “1”, то производим такт сложения суммы ЧП с множимым, иначе переходим к проверке логического условия P4. Если он равен “0”, то следует произвести сдвиги суммы ЧП и множителя, т.е. RG3 и RG1, в счётчик СТ прибавляется 1, в противном случае такт является последним и производится проверка на возможность выдачи результата на ШИВых, завершение алгоритма.

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

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

Таблица 4.

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

Таблица 5.

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

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

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

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

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

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

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

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

При использовании D-триггеров в качестве ЭП для получения смены состояний на каждом переходе (a_m -> a_s) сигналы возбуждения должны быть поданы на те триггеры, которые в коде состояния перехода a_s содержат "1". Отсюда основное требование к выбору кодов состояний: чем больше переходов в какое-либо состояние, тем меньше "1" должен содержать код этого состояния. Для кодирования 9 состояний (a₀ ,…, a₈) необходимо 4 элемента памяти.

Таблица 6.

Наибольшее количество переходов в состояние a₈ - закодируем его кодом К(a₈) = 0000. Для остальных состояний первой строки табл.6 назначим коды с одной "1" и более: K(a₀) = 0001, K(a₁) = 0010, К(a₂) = 0011, К(a₃) = 0100, K(a₄) = 0101, K(a₅) = 0110, K(a₆) = 1000, K(a₇) = 1001. Таким образом, таблица кодирования для D-триггеров такова:

Таблица 7.

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

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

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

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

D0 = a0~x1 V a1x6 V a2~x1 V a3x6~x4 V a3x6x4 V a6 V a8x7= a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2= a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2= a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3

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

y0 = a0x1  = a6 = a0x1 V a2x1  = a1x6 V a4x2 = a0x1 V a3x6~x4 V a3~x6 = a1x6 V a4x2 V a5x3 V a7~x5x3

y11 = a8x7

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

c = a0x1 (2) l = a5x3 (2)= a0 V a2 (2) m = a7~x5x3 (3)= a1x6 (2) n = a3~x6 (2)= a8x7 (2)= a3x6 (2)= a7~x5 (2)= a2x1 (2)= a4x2 (2)= a2~x1 (2)= a0~x1 V a1x6 V a2~x1 V a3x6~x4 V a3x6x4 V a6 V a8x7 = ~x1d V e V g V a6 V f (7)= a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2 = c V e V k V a4 (4)= a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2 = i V g V a4 (3)= a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3 = a5 V a6 V h (3) = c (0) = a6 (0) = a0x1 V a2x1 = x1d (2) = e V j (2) = c V g~x4 V n (5) = e V j V l V m (4)= f (0)

Инверсия: (~x1~x5~x6) (3)

Полная цена по Квайну: 58(КС)+8(ЭП)+4(DC)+0(НУ)=70

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

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

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

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

1). =a₂

 B={1}       С₁={0011,0101,1001} W₀₀₁₁=1

D₂={0011,0101,1001} W₀₁₀₁=1₁₀₀₁=1

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

K(a₂)=0011

2). =a₃

 B={2}₂={0010,0111,1011} W₀₀₁₀=1₃={0010,0111,1011} W₀₁₁₁=1₁₀₁₁=1

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

K(a₃)=0010

). =a₄

 B={3}₃={0110,1010}           W₀₁₁₀=1₄={0110,1010} W₁₀₁₀=1

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

K(a₄)=0110

). =a₅

B={4}₄={1110,0111,0100}

W₁₁₁₀=1

W₀₁₀₀=1

W₀₁₁₁=1

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

K(a₅)=0100

5). =a₆

B={5}₅={0101,1100}₀₁₀₁=1

D₆={0101,1100}

W₁₁₀₀=1

Выбираем любой: K(a₆)=1100

6). =a₇B={6}₆={1101,1110,1000}₁₁₀₁=2 ₇={1101,1110,1000}₁₁₁₀=2₁₀₀₀=2

Выбираем:         K(a₇)=1000

). =a₈

B={0,1,3,7}         C₀={Ø} ₁₀₀₁=7

C₁={1001} W₁₀₁₀=7₃={1010} W₁₁₀₀=9₇={1001,1100,1010}

D₈={1001,1010,1100}

Выбираем:         K(a₇)=1001

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

Таблица 8.

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

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

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

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

S0 = a0x1 V a3~x6 V a7x5= a1x6= a3x6~x4 V a3x6x4 V a7~x5~x3 V a7~x5x3= a1~x6 V a3~x6 V a5x3 V a5~x3= a2x1 V a8x7= a3~x6 V a4~x2 V a4x2

R2 = a6= a8x7

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

l = a2x1 (2) r = a3x6 (2) x = a7~x5 (2)= a0x1 (2) s = a7x5 (2)= a3~x6 (2) t = a1~x6 (2)= a1x6 (2) u = a3x6~x4 (3)= a8x7 (2) v = a5x3 (3)= a4x2 (2) w = a7~x5x3 (3)= m V n V s (3)= o (0)= r V x (2)= t V n V a5 (3)= l V p (2)= n V a4 (2)= a6 (0)= p (0) = m (0) = a6 (0) = m V l (2) = o V q (2) = m V u V n (3) = o V q V v V w (4)= p (0)

Инверсии: (~x6~x4~x5) (3)

Полная цена по Квайну: С = 55(КC)+12(ЭП)+4(ДЦ)+4(НУ) = 75

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

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

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

Таблица 10.

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

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

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

+1 = a0x1 V a1x6 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2 V a5x3 V a5~x3 V a6 V a7x5 - 1 = a7~x5~x3 V a7~x5x3= a8y11EWR = a1~x6 V a3~x6

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

1 = a4x2 (2) 7 = a8x7 (2) 13 = a5x3 (2)

= a0x1 (2) 8 = 6x3 (2) 14 = a7~x5 (2)

= a3x6 (2) 9 = a1~x6 (2) 15 = 9 V 4 (2)

= a3~x6 (2) 10 = a7x5 (2)

= a1x6 (2) 11 = a2x1 (2)

= a1 V a3 (2) 12 = 3~x4 (2)

+1 = 2 V 5 V 3 V a4 V a5 V a6 V 10 (7)

1 = 14 (0)= 7 (0)EWR = 15 (0) = 2 (0) = a6 (0) = 2 V 11 (2)  = 5 V 1 (2) = 2 V 12 V 4 (3) = 5 V 1 V 13 V 8 (4)= 7 (0)

Инверсии: (~x4~x6~x5) (3)

Полная цена по Квайну: С = 51(КС)+9(ЭП)+4(ДЦ)+0(НУ)=0.

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

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

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

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

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

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

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

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

Таблица 13.

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

Таблица 14.

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

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

= b1x6 V b1~x6~x7 V b2x1 V b3x1 V b4x6~x4 V b4x6x4x2 V b5~x7 V b6x2 V b9x5~x7 V b10~x7= b0~x1 V b1~x6x7 V b2x1 V b3x1 V b4~x6 V b4x6~x4 V b5x7 V b9x5x7 V b10x7 V b11= b0x1 V b1x6 V b4~x6 V b4x6~x4 V b4x6x4~x2x3 V b6~x2x3 V b7x3 V b9~x5x3= b0~x1 V b0x1 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11

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

y0 = b1 = b9

y2 = b1 V b4

y3 = b7

y4 = b1 V b5 V b6

y5 = b7 V b8

y11 = b11

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

c = b1x6 (2)= b1~x6 (2)= b2x1 (2)= b4x6~x4 (3)= b3x1 (2)= b4~x6 (2)= e V g V f (3)= k V l (2)= b4x6x4x2 (4)= b6x2 (2)= b9x5 (2)= b5 V m V b10 V d (4)= b1x6 V b1~x6~x7 V b2x1 V b3x1 V b4x6~x4 V b4x6x4x2 V b5~x7 V b6x2 V b9x5~x7 V b10~x7 =

= c V i V j V ~x7(b5 V m V b10 V d) = c V i V j V ~x7n (6)= b0~x1 V b1~x6x7 V b2x1 V b3x1 V b4~x6 V b4x6~x4 V b5x7 V b9x5x7 V b10x7 V b11 = b0~x1 V I V h V x7(b5 V m V b10 V d) V b11 = b0~x1 V I V h V x7n (8)= b0x1 V b1x6 V b4~x6 V b4x6~x4 V b4x6x4~x2x3 V b6~x2x3 V b7x3 V b9~x5x3 = b0x1 V c V h V f V ~x2x3 (b4x6x4 V b6) V x3(b7 V b9~x5) (22)= b0 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11 = b0 V ~x1(b2 V b3) V j (6)= b1 (0)= b8 (0)

y2 = b1 V b4 (2)

y3 = b2 V b6 (2)

y4 = b1 V b5 (2)

y5 = b2 V b6 V b7 (3)

y6 = b8 (0)

Инверсии: (~x1~x2~x4~x5~x6~x7) (6)

Полная цена по Квайну: С = 87(КС)+8(ЭП)+0(НУ)+4(ДЦ) = 99

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

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

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

Таблица 15.

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

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

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

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

R0 = b2~x1 V b2x1 V b7x3 V b7~x3 V b11= b4x6~x4 V b4x6x4x2 V b4x6x4~x2x3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7= b11= b11= b0x1 V b4~x6 V b4x6x4x2 V b6x2 V b9x5~x7 V b9x5x7= b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3= b1~x6~x7 V b1~x6x7 V b2x1 V b3x1= b1~x6~x7 V b1~x6x7 V b4x6x4~x2x3 V b4x6x4~x2~x3 V b5~x7 V b5x7 V b6~x2x3 V b6~x2~x3 V b7x3 V b7~x3= b1 = b8

y2 = b1 V b4

y3 = b2 V b6

y4 = b1 V b5

y5 = b2 V b6 V b7

y6 = b8

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

o = b4x6x4x2 (4)= b4x6x4~x2 (4)= b1~x6 (2)= b2 V b7 V b11 (3)= b4x6~x4 V o V px3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7 (21)= b11 (0)= b11 (0)= b0x1 V b4~x6 V o V b6x2 V b9x5 (13)= b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3 (14)= q V b2x1 V b3x1 (7)= q V p V b5 V b6~x2 V b7 (7)= b1 (0)= b8 (0)

y2 = b1 V b4 (2)

y3 = b2 V b6 (2)

y4 = b1 V b5 (2)

y5 = b2 V b6 V b7 (3)

y6 = b8 (0)

Инверсии: (~x2~x3~x4~x5~x6) (5)

Полная цена по Квайну: С = 89(КС)+12(ЭП)+4(НУ)+4(ДЦ) = 109

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

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

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

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

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

Рис. 5. Функциональная схема управляющего микропрограммного автомата

Список использованных сокращений:

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

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

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

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

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

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

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

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

ЭП - элемент памяти

КС - комбинационная схема

~ - знак инверсии (инвертируется то, перед чем стоит этот знак)

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

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

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

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