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

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

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

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

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

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

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

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

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

Киров, 2011

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A = -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001

B = -36 = 100100₂, В_пк = 1,100100, В_дк = 1,011100.

Таблица 1.

Множитель	Множимое	Сумматор	Пояснения
1,001001	1,011100	0,000000000000 0,000001001000
		0,000001001000	Коррекция
		0,000000110111 0,000000100100 0,000001001011
1,010010		0,000101101100	Сдвиг
1,100100		0,001011011000	Сдвиг
		0,000000011100	Сложение
		0,001011110100
1,001000		0,01011110100	Сдвиг
1,010000		0,10111101000	Сдвиг
1,100000		0,011110100000	Сдвиг
		0,000000011100	Сложение
		0,011110111100

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

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

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

A = -55 = 110111₂, А_пк = 1,110111, А_дк = 1,001001

B = 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 2.

Множитель	Множимое	Сумматор	Пояснения
1,001001	0,100100	0,000000111000 0,000000000000 0,000000111000	Коррекция
1,010010		0,000001110000	Сдвиг
1,100100		0,000011100000	Сдвиг
		0,000000100100	Сложение
		0,000100000100
1,001000		0,001000001000	Сдвиг
1,010000		0,010000010000	Сдвиг
1,100000		0,100000100000	Сдвиг
		0,000000100100	Сложение
		0,100001000100

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

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

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

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

A = 55 = 110111₂, А_пк = 0,110111, А_дк = 0,110111

B = 36 = 100100₂, В_пк = 0,100100, В_дк = 0,100100.

Таблица 3.

Множитель	Множимое	Сумматор	Пояснения
0,110111	0,100100	0,000000000000
		0,000000100100	Сложение
		0,000000100100
0,101110		0,000001001000	Сдвиг
		0,000000100100	Сложение
		0,000001101100
0,011100		0,000011011000	Сдвиг
0,111000		0,000110110000	Сдвиг
		0,000000100100	Сложение
		0,000111010100
0,110000		0,001110101000	Сдвиг
		0,000000100100	Сложение
		0,001111001100
0,100000		0,011110011000	Сдвиг
		0,000000100100	Сложение
		0,011110111100

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

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

P =55*36 = 1980 = 11110111100₂

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

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

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

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

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

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

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

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

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

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

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

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

y0 - запись в RG1, запись в СТ, запись в Т;

y1 - сдвиг RG1 влево RG1:=L1(RG1).0, сдвиг RG3 влево

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

y2 - запись в RG2;

y3 - инверсия выхода RG2 и SM_p=1 - подача “1” на вход переноса сумматора;

y4 - сброс RG3;

y5 - запись в RG3;

y8 - обнуление счётчика;

y11 - управление выдачей информации на ШИВых;

y12 - очистка RG1;

y13 - очистка RG2.

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

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

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

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

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

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

P5=0, один из операндов равен “0”;

Р6 - знак произведения;

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

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

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

Содержательная граф-схема алгоритма представлена на рис. 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, в противном случае такт является последним и производится проверка на возможность выдачи результата на ШИВых, завершение алгоритма.

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

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

Таблица 4.

MK	Совокупность МО
Y1	y0,y2,y4
Y2	y3,y5
Y3	y2
Y4	y4
Y5	y5
Y6	y1
Y7	y11

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

Таблица 5.

Входной сигнал УА	X1	X2	X3	X4	X5	X6	X7
Логическое условие ОА	X	P1	P2	P3	P4	P5	Z

Далее в полном соответствии с содержательной ГСА строим отмеченную ГСА( рис. 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.

as	a0	a1	a2	a3	a4	a5	a6	a7	а8
{am}	a8,a0	a0	a2,a1	a2	a3	a4	a7	a6	a1,a3,a7,a8

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

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

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

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

Исходное состояние am	Код am	Состояние перехода as	Код as	Входной сигнал X(am, as)	Выходные сигналы Y(am,as)	Функция возбуждения D-триггеров
a0	0001	a0 a1	0001 0010	~X1 X1	- y0y2y4	D0 D1
a1	0010	a2 a8	0011 0000	X6 ~X6	y3y5 -	D0D1 -
a2	0011	a2 a3	0011 0100	~X1 X1	- y2	D0D1 D2
a3	0100	a4 a4 a8	0101 0101 0000	X6~X4 X6X4 ~X6	y4 - y4	D0D2 D0D2 -
a4	0101	a5 a5	0110 0110	~X2 X2	- y3y5	D1D2 D1D2
a5	0110	a6 a6	1000 1000	X3 ~X3	y5 -	D3 D3
a6	1000	a7	1001	1	y1	D0D3
a7	1001	a6 a6 a8	1000 1000 0000	~X5~X3 ~X5X3 X5	- y5 -	D3 D3 -
а8	0000	a0 a8	0001 0000	X7 ~X7	y11 -	D0 -

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

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

D0 = a0~x1 V a1x6 V a2~x1 V a3x6~x4 V a3x6x4 V a6 V a8x7

D1 = a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2

D2 = a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2

D3 = a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3

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

y0 = a0x1

y1 = a6

y2 = a0x1 V a2x1

y3 = a1x6 V a4x2

y4 = a0x1 V a3x6~x4 V a3~x6

y5 = a1x6 V a4x2 V a5x3 V a7~x5x3

y11 = a8x7

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

c = a0x1 (2) l = a5x3 (2)

d = a0 V a2 (2) m = a7~x5x3 (3)

e = a1x6 (2) n = a3~x6 (2)

f = a8x7 (2)

g = a3x6 (2)

h = a7~x5 (2)

i = a2x1 (2)

j = a4x2 (2)

k = a2~x1 (2)

D0 = 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)

D1 = a0x1 V a1x6 V a2~x1 V a4~x2 V a4x2 = c V e V k V a4 (4)

D2 = a2x1 V a3x6~x4 V a3x6x4 V a4~x2 V a4x2 = i V g V a4 (3)

D3 = a5x3 V a5~x3 V a6 V a7~x5~x3 V a7~x5x3 = a5 V a6 V h (3)

y0 = c (0)

y1 = a6 (0)

y2 = a0x1 V a2x1 = x1d (2)

y3 = e V j (2)

y4 = c V g~x4 V n (5)

y5 = e V j V l V m (4)

y11 = 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

W₁₀₀₁=1

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

K(a₂)=0011

2). ?=a₃

B={2}

C₂={0010,0111,1011} W₀₀₁₀=1

D₃={0010,0111,1011} W₀₁₁₁=1

W₁₀₁₁=1

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

K(a₃)=0010

3). ?=a₄

B={3}

C₃={0110,1010} W₀₁₁₀=1

D₄={0110,1010} W₁₀₁₀=1

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

K(a₄)=0110

4). ?=a₅

B={4}

C₄={1110,0111,0100}

W₁₁₁₀=1

D₅={1110,0100,0111}

W₀₁₀₀=1

W₀₁₁₁=1

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

K(a₅)=0100

5). ?=a₆

B={5}

C₅={0101,1100}

W₀₁₀₁=1

D₆={0101,1100}

W₁₁₀₀=1

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

6). ?=a₇B={6}

C₆={1101,1110,1000}

W₁₁₀₁=2

D₇={1101,1110,1000}

W₁₁₁₀=2

W₁₀₀₀=2

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

7). ?=a₈

B={0,1,3,7} C₀={Ш}

W₁₀₀₁=7

C₁={1001} W₁₀₁₀=7

C₃={1010} W₁₁₀₀=9

C₇={1001,1100,1010}

D₈={1001,1010,1100}

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

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

Таблица 8.

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

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

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

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

Исходное состояние	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения RS-триггеров
a0	0000	a0 a1	0000 0001	~X1 X1	- y0y2y4	- S0
a1	0001	a2 a8	0011 1001	X6 ~X6	y3y5 -	S1 S3
a2	0011	a2 a3	0011 0010	~X1 X1	- y2	- R0
a3	0010	a4 a4 a8	0110 0110 1001	X6~X4 X6X4 ~X6	y4 - y4	S2 S2 S0R1S3
a4	0110	a5 a5	0100 0100	~X2 X2	- y3y5	R1 R1
a5	0100	a6 a6	1100 1100	X3 ~X3	y5 -	S3 S3
a6	1100	a7	1000	1	y1	R2
a7	1000	a6 a6 a8	1100 1100 1001	~X5~X3 ~X5X3 X5	- y5 -	S2 S2 S0
a8	1001	a0 a8	0000 1001	X7 ~X7	y11 -	R0R3 -

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

S0 = a0x1 V a3~x6 V a7x5

S1 = a1x6

S2 = a3x6~x4 V a3x6x4 V a7~x5~x3 V a7~x5x3

S3 = a1~x6 V a3~x6 V a5x3 V a5~x3

R0 = a2x1 V a8x7

R1 = a3~x6 V a4~x2 V a4x2

R2 = a6

R3 = a8x7

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

l = a2x1 (2) r = a3x6 (2) x = a7~x5 (2)

m = a0x1 (2) s = a7x5 (2)

n = a3~x6 (2) t = a1~x6 (2)

o = a1x6 (2) u = a3x6~x4 (3)

p = a8x7 (2) v = a5x3 (3)

q = a4x2 (2) w = a7~x5x3 (3)

S0 = m V n V s (3)

S1 = o (0)

S2 = r V x (2)

S3 = t V n V a5 (3)

R0 = l V p (2)

R1 = n V a4 (2)

R2 = a6 (0)

R3 = p (0)

y0 = m (0)

y1 = a6 (0)

y2 = m V l (2)

y3 = o V q (2)

y4 = m V u V n (3)

y5 = o V q V v V w (4)

y11 = p (0)

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

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

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

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

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

Таблица 10.

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

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

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

Исходное состояние	Код am	Состояние перехода as	Код as	Входной сигнал X(am,as)	Выходные сигналы Y(am,as)	Функции возбуждения счётчиков
a0	0000	a0 a1	0000 0001	~X1 X1	- y0y2y4	- +1
a1	0001	a2 a8	0010 1000	X6 ~X6	y3y5 -	+1 D3EWR
a2	0010	a2 a3	0010 0010	~X1 X1	- y2	- -
a3	0011	a4 a4 a8	0100 0100 1000	X6~X4 X6X4 ~X6	y4 - y4	+1 +1 D3EWR
a4	0100	a5 a5	0101 0101	~X2 X2	- y3y5	+1 +1
a5	0101	a6 a6	0110 0110	X3 ~X3	y5 -	+1 +1
a6	0110	a7	0111	1	y1	+1
a7	0111	a6 a6 a8	0110 0110 1000	~X5~X3 ~X5X3 X5	- y5 -	-1 -1 +1
a8	1000	a0 a8	0000 1000	X7 ~X7	y11 -	R -

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

+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

R = a8y11

D3EWR = a1~x6 V a3~x6

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

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

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

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

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

5 = a1x6 (2) 11 = a2x1 (2)

6 = 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)

R = 7 (0)

D3EWR = 15 (0)

y0 = 2 (0)

y1 = a6 (0)

y2 = 2 V 11 (2)

y3 = 5 V 1 (2)

y4 = 2 V 12 V 4 (3)

y5 = 5 V 1 V 13 V 8 (4)

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения D-триггеров
b0	-	1010	b0 b1	1010 1100	~X1 X1	D1D3 D2D3
b1	y0y2y4	1100	b2 b10 b11	0101 0001 0010	X6 ~X6~X7 ~X6X7	D0D2 D0 D1
b2	y3y5	0101	b3 b4	1000 0011	~X1 X1	D3 D0D1
b3	-	1000	b3 b4	1000 0011	~X1 X1	D3 D0D1
b4	y2	0011	b5 b6 b7 b8 b9	0110 0111 1001 0100 0000	~X6 X6~X4 X6X4X2 X6X4~X2X3 X6X4~X2~X3	D1D2 D0D1D2 D0D3 D2 -
b5	y4	0110	b10 b11	0001 0010	~X7 X7	D0 D1
b6	y4	0111	b7 b8 b9	1001 0100 0000	X2 ~X2X3 ~X2~X3	D0D3 D2 -
b7	y3,y5	1001	b8 b9	0100 0000	X3 ~X3	D2 -
b8	y5	0100	b9	0000	1	-
b9	y1	0000	b8 b9 b10 b11	0100 0000 0001 0010	~X5X3 ~X5~X3 X5~X7 X5X7	D2 - D0 D1
b10	-	0001	b10 b11	0001 0010	~X7 X7	D0 D1
b11	y11	0010	b0	1010	1	D1D3

Таблица 13.

bs	b0	b1	b2	b3	b4	b5	b6	b7
{bm}	b0b11	b0	b1	b2b3	b2b3	b4	b4	b4b6
bs	b8	b9	b10	b11
{bm}	b4b6b7b9	b4b6b7b8b9	b1b5b9b10	b1b5b9b10

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

Таблица 14.

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

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

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

D0 = 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

D1 = b0~x1 V b1~x6x7 V b2x1 V b3x1 V b4~x6 V b4x6~x4 V b5x7 V b9x5x7 V b10x7 V b11

D2 = b0x1 V b1x6 V b4~x6 V b4x6~x4 V b4x6x4~x2x3 V b6~x2x3 V b7x3 V b9~x5x3

D3 = b0~x1 V b0x1 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11

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

y0 = b1

y1 = b9

y2 = b1 V b4

y3 = b7

y4 = b1 V b5 V b6

y5 = b7 V b8

y11 = b11

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

c = b1x6 (2)

d = b1~x6 (2)

e = b2x1 (2)

f = b4x6~x4 (3)

g = b3x1 (2)

h = b4~x6 (2)

i = e V g V f (3)

j = k V l (2)

k = b4x6x4x2 (4)

l = b6x2 (2)

m = b9x5 (2)

n = b5 V m V b10 V d (4)

D0 = 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)

D1 = 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)

D2 = 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)

D3 = b0 V b2~x1 V b3~x1 V b4x6x4x2 V b6x2 V b11 = b0 V ~x1(b2 V b3) V j (6)

y0 = b1 (0)

y1 = 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.

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

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

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

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

Исходное состояние bm	Выходные сигналы	Код bm	Состояние перехода bs	Код bs	Входной сигнал	Функции возбуждения RS-триггеров
b0	-	0000	b0 b1	0000 0001	~X1 X1	- S0
b1	y0y2y4	0001	b2 b10 b11	0011 1111 1101	X6 ~X6~X7 ~X6X7	S1 S1S2S3 S2S3
b2	y3y5	0011	b3 b4	0010 0110	~X1 X1	R0 R0S2
b3	-	0010	b3 b4	0010 0110	~X1 X1	- S2
b4	y2	0110	b5 b6 b7 b8 b9	0111 0100 0101 1100 1110	~X6 X6~X4 X6X4X2 X6X4~X2X3 X6X4~X2~X3	S0 R1 S0R1 R1S3 S3
b5	y4	0111	b10 b11	1111 1101	~X7 X7	S3 R1S3
b6	y4	0100	b7 b8 b9	0101 1100 1110	X2 ~X2X3 ~X2~X3	S0 S3 S1S3
b7	y3,y5	0101	b8 b9	1100 1110	X3 ~X3	R0S3 R0S1S3
b8	y5	1100	b9	1110	1	-
b9	y1	1110	b8 b9 b10 b11	1100 1110 1111 1101	~X5X3 ~X5~X3 X5~X7 X5X7	R1 - S0 S0R1
b10	-	1111	b10 b11	1111 1101	~X7 X7	- R1
b11	y11	1101	b0	0000	1	R0R2R3

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

R0 = b2~x1 V b2x1 V b7x3 V b7~x3 V b11

R1 = b4x6~x4 V b4x6x4x2 V b4x6x4~x2x3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7

R2 = b11

R3 = b11

S0 = b0x1 V b4~x6 V b4x6x4x2 V b6x2 V b9x5~x7 V b9x5x7

S1 = b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3

S2 = b1~x6~x7 V b1~x6x7 V b2x1 V b3x1

S3 = 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

y0 = b1

y1 = b8

y2 = b1 V b4

y3 = b2 V b6

y4 = b1 V b5

y5 = b2 V b6 V b7

y6 = b8

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

o = b4x6x4x2 (4)

p = b4x6x4~x2 (4)

q = b1~x6 (2)

R0 = b2 V b7 V b11 (3)

R1 = b4x6~x4 V o V px3 V b5x7 V b9~x5x3 V b9x5x7 V b10x7 (21)

R2 = b11 (0)

R3 = b11 (0)

S0 = b0x1 V b4~x6 V o V b6x2 V b9x5 (13)

S1 = b1x6 V b1~x6~x7 V b6~x2~x3 V b7~x3 (14)

S2 = q V b2x1 V b3x1 (7)

S3 = q V p V b5 V b6~x2 V b7 (7)

y0 = b1 (0)

y1 = 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.

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

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