Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

У'УнУііФьФі

a,ß3x,x2x3x6

Phc. 6-16. Логическая схема, построенная по табл. 6-9: а — без вынесений общих множителей, б — с вынесениями общих мно­ жителей

Кроме вынесения вниз для схем «И», эта операция может быть ис­ пользована при построении схем «ИЛИ», например, для выходных сиг­ налов. После построения всех переходов в каждое состояние часто бывает, что одни и те же микрооперации выдаются на различных пе­

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

Рассмотрим пример. Пусть выходной сигнал у х снимается со схем

«И» 1, «И» 7, «ИЛИ» 12, «ИЛИ» 14, «И» 15, «ИЛИ» 18, выходной сиг­ нал у .2 — со с-хем «И» 1, «И» 7, «И» 15 и выходной сигнал у3 — со схем

«И» 1, «ИЛИ» 2, «И» 3, «И» 7, «ИЛИ» 12, «ИЛИ» 14, «И» 15. Для полу-

jnjnjunflz .JflSJUUflQ „И"! „07Л15 jn ЛЛІГи-ЗЛІЯІІЮМКуіЖН

Рис. 6-17. Вынесение вниз для дизъюнкций: а — схема до выне­

сения, б — схема после вынесения

„И"! . H l j n s

чения каждого из этих сигналов необходимо построить три схемы «ИЛИ», после чего схема примет вид рис. 6-17, а (цена схемы равна 16).

Представим у ІУу 2 и у 3 в виде слов, составленных из индексов схем, с которых они снимаются, после чего применим процедуру вынесения вниз, используя на каждом шаге общую часть с наибольшей ценой:

Za= l , 7, 12, 14, 15(уи уз)\ W(Z2) = 3.

Выносим Z2. Выход схемы для Z1 обозначим буквой 19.

Z3= 12, 14, 19(1/!, уз)-, W(Z3)= 1.

116

Выносим Z3. Выход схемы для Zg обозначим буквой 20. Дальней­

рис. 6-17, б. Цена схемы сократилась на 5 входов в логические эле­ менты.

Процедура вынесения вниз может быть использована при минимизации схем «ИЛИ» для выходных сигналов и функции возбуждения с одновременным до­ определением функций возбуждения. Проиллюстрируем это на примере построе­ ния схемы для переходов в состояние а33 в табл. 6-10, являющейся частью об­ ратной структурной таблицы некоторого автомата. Так как в данном случае конкретный вид входных сигналов безразличен, они представлены в этой таблице в общем виде.

117

Очевидно, что при построении схем, соответствующих каждой строчке, табл. 6-10, получим семь схем «И», с которых снимаются записанные в этих строч­ ках выходные сигналы и функции возбуждения:

с „И “ 1— f/oi, 0о2>ФбІ

Для получения каждого выходного сигнала или функции возбуждения не­ обходимо построить схему «ИЛИ», на которую подать выходы тех схем из «И» 1,

. . . , «И» 7, с которых снимается этот выходной сигнал или эта функция воз­ буждения (рис. 6-18, а). Схему на рис. 6-18, а можно проминимизировать с по­ мощью вынесения вниз, как это было сделано выше для выходных сигналов. Но так как эта схема соответствует переходам в одно состояние, можно попытаться для ее минимизации доопределить функции возбуждения.

Как и в рассмотренном выше примере вынесения вниз для выходных сигна­ лов, выпишем для каждого выходного сигнала и функции возбуждения номера схем «И», с которых они снимаются. Кроме того, для каждой функции возбужде­ ния в скобках запишем номера схем, с которых можно снять эту функцию воз­ буждения, если доопределить функции возбуждения на рассматриваемом пере­ ходе. Таким образом, каждой функции возбуждения соответствует слово из двух частей: обязательной (без скобок) и необязательной (в скобках).

Находим пересечения всех выписанных слов, не делая различия между бук­ вами в обязательной и необязательной частях. Так, например, пересечение ме­ жду і/оі = 1, 4, 5, 6 и Фі = 3, 5, 6, 7 (1, 2, 4) равно 1, 4, 5, 6 и т. д. Находим,

таким образом, все общие части:

Z, = 1, 2, 3, 4, 5, 6, 7 ( фз, фй, ф5, ф|, ф0, фЗ);

Z3= l , 5 , б(«/61, г/62, ФІ, Фг, ФІ, Ф5, Фе, ФІ);

Z4 = 2, 7 (у15, у№, ф|, фі, фі, ф§).

В скобках после общей части, как и выше, записываем номера слов, в ко­ торые она входит, но только в том случае, если хотя бы одна буква из общей части входит в обязательную часть слова. Именно поэтому после общей части Z4 в скобках нет ф4 и ф7, так как все буквы Z^ входят в необязательную часть ф.}

118

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

Например, после общей части Z2 — 1, 4, 5, 6 в скобках стоят (у81, фр ф,, ф^,

ФІ’ Фщ Ф?)' Действительно, две буквы общей части Z2 (1 и 4) стоят в скобках в

слове фр Верхний индекс у ф7 равен единице, так как только одна буква из ф7 fl) входит в необязательную часть слова ф7.

jRjnjn .и)ßvwxsjajn jfijnxum

~УisУss

Уя'

ТТ

-Увг 2 7

Рис. 6-18. Вынесение вниз с доопределением функций возбуждениям — схема без вынесения, б — схема после вынесения с доопределением, в — схема после вынесения без доопределения

Цена общей части при вынесении вниз с учетом доопределения подсчиты­ вается по формуле:

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

Включение і со знаком минус в выражение для W (Z) объясняется тем, что уменьшение цены схемы в результате вынесения вниз учитывается только для

119

обязательной части. По формуле (6-9) найдем цену каждой пз общих частей.

щие в необязательную часть ф7, становятся обязательными, т. е. происходит доопределение cpt, что равносильно тому, что со схем «И»1, «И»2 и «И»4 снимается функция возбуждения tpt. То же самое справедливо и для других функций, из которых выносится Zx.

После вынесения вниз Zt слова cpj, фо, ф.,, фг>, ф„ п ф7 удаляются из исход­ ного множества слов, так как все они совпадают с общей частью. Выход схемы, реализующей Zl( обозначим новой буквой, 8.

Находим пересечения в новом множестве слов:

Выносим Z5. Выход схемы «ИЛИ», реализующей Z5, обозначим буквой 9.

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

120