Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 65
Текст из файла (страница 65)
На первом шаге берется дополнение г' функции Е. Если 278 Глава 4. Принципы проектирования комбинационных логических схем функция г представлена в виде списка минтермов или в виде таблицы истинности, то найти дополнение совсем легко: просто нули в р заменяются в р' на единицы. Затем мы находим минимальную сумму для р' по правилам, описанным в предыдущем разделе. Наконец, по обобщенной теореме Де Моргана берем дополнение к результату, что и приводит нас к минимальному произведению для (Е)' = р. (Обратите внимание, что простое «разнесение слагаемых по сомножителям» в минимальной сумме для исходной функции не гарантирует того, что получающееся при этом произведение сумм будет минимальным; см., например, задачу 4.61.) В общем случае, для того чтобы построить двухуровневую схему, которая была бы самой дешевой реализацией некоторой логической функции, необходимо найти как минимальную сумму, так и минимальное произведение, и сравнить их.
Если в минимальной сумме данной логической функции много слагаемых, то минимальное произведение той же самой логической функции может состоять из меньшего числа сомножителей. Вот тривиальный пример такого сопоставления — функция ИЛИ 4-х переменных: Г = ((//) + (Х) + (у) + (7) (сумма четырех элементарных термов- произведений) = (Ч/+ Х+ у+ Е) (произведение, состоящее из одного терма- суммы).
В качестве нетривиального примера приглашаем вас найти минимальное произведение для функции на рис.4.33, которую мы минимизировали выше; в минимальном произведении всего два терма-суммы. Иногда бывает верно и обратное, как это видно на простейшем примере функции И 4-х переменных: Е=(Ч/) (Х) (У).(2) (произведениечетырехэлементариыхтермов-сумм) = (Ф Х У 2) (сумма, состоящая из одного герма-произведения). МИНИМИЗАЦИЯ ПРИМЕНИТЕЛЬНО К ПЛУ Структура типичною ПЛУ представляет собой решетку И-ИЛИ, соответствующую логическому выражению вида «сумма произведений», поэтому можно подумать, что при проектировании на основе ПЛУ нужна только минимальнаяя сумма произведений. Однако у большинства ПЛУ на выходах решетки И-ИЛИ имеются программируемые инверторы/буферы, с помощью которых любой из выходных сигналов легко инвертировать или пропускать без инверсии.
Таким образом, применительно к ПЛУ можно воспользоваться эквивалентом минимальной суммы и на решетке И вЂ” ИЛИ реализовать дополнение желаемой функции, а затем осуществить инвертирование, соответственно запрограммировав инвертор/буфер. Большинство программ минимизации логических функций для ПЛу автоматически находят как минимальную сумм)', так и минимальное произведение и выбирают ту из форм, в которой меньше тернов.
4.3. Синтез комбинационных окем 279 НетРивиальным пРимеРом является функция, приведенная парис. 4.29, для которой стоимость реализации произведения сумм больше. У некоторых логических функций стоимость реализации для обеих форм одинакова. Рассмотрим, например, функцию ИСКЛЮЧАКМЦЕЕ ИЛИ 3-х переменных; каждое из минимальных выражений состоит из четырех термов и в каждом терме содержатся три литерала: Р =Ххтк(1,2,4,7) = (Х' У' 2) + (Х' У 2') + (Х У'. 2') + (Х .У . 2) = (Х+У+ 7) (Х+У'+ 2') (Х'+У+у') (Х'+У'+ э) Но все же в большинстве случаев либо одна, либо другая форма дает лучшие результаты. Рассмотреть обе формы особенно полезно при проектировании устройств иа основе ПЛУ.
'4.3.7. «Безразличные» комбинации Переменных Иногда требования, предъявляемые к комбинационной схеме, таковы, что не имеет значения, какой сигнал будет возникать на ее выходах при определенных комбинациях входных сигналов. Такие комбинации называются безр~ачичиыми (пои 1- саге). Это может иметь место по той причине, что значения выходного сигнала при этих комбинациях сигналов на входах и в самом деле не играют никакой роли, либо потому, что при нормальной работе схемы эти комбинации входных сигналов никогда не возникают. Предположим, например, что мы хотим создать устройство для обнаружения простых чисел, 4-разрядное двоичное слово 1ч' = Мз и) зй ~ Ые на входах которого всегда является двоично-десятичной цифрой; в этом случае минтермы 1Π— 15 никогда не нужно будет принимать во внимание. С учетом этого функцию, реализуемую устройством, предназначенным для обнаружения простых двоично-десятичных чисел, можно записать так: Р = Х, ньн,нине (1, 2, 3, 5, 7) "- с((10, 11, 12, 13, 14, 15).
Здесь б(...)- список безразличных комбинаций переменных для данной функции, образующих так называемое 1-множество (Ыыаг). Согласно этой записи функция Г должна принимать значение 1 при комбинациях переменных из множества включений (1, 2, 3, 5, 7), может иметь любые значения при комбинациях переменных из д-множества и должна равняться О при всех других комбинациях переменных (принадлежащих О-множеству). На рис, 4,37 показано, как найти минимальную реализацию суммы произведенийй лля устройства, обнаруживающего простые двоич но-десятичные числа, с учетом безразличных комбинаций переменных. Клетки, соответствующие безразличным комбинациям переменных, помечены на карте буквой г(. Процелура обведения наборов единиц (простых импликант) видоизменяется следующим образом: При обводе единиц допускается включение клеток, помеченных буквой д, с целью получения наборов возможно большего размера.
Это сокращает число переменных в соответствующих простых импликантах. В примере парис. 4.37такихпростыхимпликантдве: Нз Ыеийг' Нь 280 Глава 4. Принципы проактировагяоя КоолбиоищиОиньгХ ЛОгичЕСХИХ СХЕМ ° Не обводятся наборы, состоящие только нз клеток, помеченных буквой г(. Если бы соответствующие термы-произведения были приняты во внимание, то зто привело бы к ненужному увеличению стоимости реализации.
В примере на рис. 4.37 таких термов-произведений два: Мз. Мз и Мз Мг. ° Как обычно, не обводятся никакие клетки, содержащие О. (Это просто напоминание.) Ог) (а] иг огог Иг г — ' — 1 ИИХФ Ог И Ш о ОО "г "г "гг 1 — — г ООО1 И 1О 111' Ио нг' нг иг к топ чозл ое(12здтг+ 41011,12131416) нг я = но' но + чг" иг Рис. 4.37. Устройство для обнаружения простых чисел в двоичио-десяти <ном представлении; (а) исходная карта карно; (о) карта карно с простыми импликан- тами и особенными клетками, содержащими 1 Некоторые языки описания схем, в том числе язык АВЕ1., содержат средства, с помощью ипорых разработчик указывает безразличные комбинации входных сигналов, и программа логической минимизации учитывает эти комбинации при нахождении минимальной суммы. *4.3.8.
Минимизация схем со многими выходами На практике у большинства комбинационных логических схем число выходов бывает больше одного. Задачу минимизации схемы с л выходами всегда можно свести к решению и независимых задач с единственным выходом. Однако, по. ступая так, мы можем пропустить те или иные возможности оптимизации. Рассмотрим, например, следующие две логические функции: г = 4.хт (3, б, 7) О = Х „ (О, 1, 3). На рис. 4.38 представлена схема с выходами г и 6, получающаяся в результате решения двух независимых задач минимизации схем с одним выходом, относя- Остальная часть процедуры — та же, что и раньше.
В частности, мы ищем особен ные клетки, содержащие 1, и не особенные клетки, помеченные буквой г), и включаем в составляемое логическое выражение только существенные простые импликанты и такие другие импликанты, которые необходимы, чтобы покрыть все единицы на карте.
В примере на рис. 4.37 двух существенных простых импликант достаточно, чтобы покрыть все единицы на карте. При этом оказываются покрытыми также две клетки, помеченные буквой г), так что при безразличных комбинациях переменных 1О и 11 функция г будет иметь значение 1, а при других безразличных комбинациях переменных — О. гцихся к функциям г и О порознь. Однако, как показано парис. 439, можно найти также такую паРу выражений вида «сумма произведенийв, в каждую из которых входит один и тот же терм-произведение, в результате чего получается схема, со- держащая на один вентиль меньше, чем в первоначальном варианте. (Ь) х у Е Х У + У.2 2'«ОО О1 Н 1О х' т )2 е х" т. х'2 Рис. 4.38. Задача о проектировании схемы с двумя выходами, Рассматривае- мая как две независимые задачи о построении схем с одним выходом: (а) карты Карно; (Ь) минимальная» схема (а) 2««ОО О1 и 1О о (Ь) 2««ОО О1 И 1О В х" У'+ Х' У 2 рис.
4.39. Минимизация схемы сдвумя выходами: (а) минимизируемые каРты и выделение общего герма; (Ь) минимальная схема, составленная с учетом двух выходов При проектировании комбинационных схем со многими выходами на основе отдельных вентилей, как это имеет местов случае специализированных ИС, наличие общих термов-произведений очевидным образом приводит к уменьшению Размера схемы и ее стоимости.
Кроме того, в ПЛУ структура, реализующая сумму произведений, повторена много раз, и мы знаем тепеРь, как минимизировать такую структуру отдельно дчя каждого выхода; в некоторых ПЛУ допускается со- ~НН 4.3. Синтез комбинационных схем 28т 282 Главе 4. Принципы проектирования комбинационных логических схем вместное использование термов-произведений схемами, относящимися к разным выходам. Идеи, излагаемые в этом разделе, использованы во многих программах логической минимизации. Возможно, что в примере, приведенном парис.
4.39, вы смогли непосредственно «углядеть» минимальное решение, рассматривая карты Карно для функций Г и О Однако минимизацию схем большего размера можно осуществить только путем применения формального алгоритма минимизации для случая многих выходов. Сейчас этот алгоритм в общих чертах будет описан; подробнее с ним можно ознакомиться по литературе. Ключом к успешной минимизации схемы со многими выходами, описывае мой набором из п функций, является рассмотрение не только самих исходных и функций, относящихся к отдельным выходам, но также и «функций-произведений>>. т-произв«дени«и (т-ргодис! 1ипс>1оп) для набора из п функций называется функция, являющаяся произведением т функций, где 2 ь т < п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
