(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation каждой другой простой импликанты, покрывающей начальную клетку, содержащую 1; результатом каждый раз будет новая гипотетическая минимальная сумма. На этом пути можно споткнуться, и тогда метод ветвления необходимо применять рекурсивно. В конце концов мы сравниваем все полученные таким образом гипотетические минимальные суммы и выбираем одну из них, которая является минимальной на самом деле. (а) W WX ,-, Yz\ 00 01 Ю
WX ,- YZ \ 00 01 11 10
WX ,- Yz\ 00 01 11 10 W X Z гХ 00 01 11 10 . W Y Z F = W-X-Z + W-Y-Z + X-Y-Z F = X-Y-Z + W-X-Z + WYZ Рис. 4.36. F=IjYz( 1.5,7,9.11,15): (a) карта Карно; (b) простые импликанты; (с) минимальная сумма; (d) другая минимальная сумма 4.3.6. Упрощение произведений сумм На основании принципа двойственности можно минимизировать выражения вида произведение сумм , рассматривая нули на карте Карно. Каждый О на карте соответствует макстерму в каноническом произведении логической функции. Все, что было изложено в предыдущем разделе, можно переформулировать в плане двойственности, включая правила составления термов-сумм, соответствующих обведенным наборам нулей, в результате чего находится минимальное произведение (minimal product). Если, однако, нам известно, как находить минимальные суммы, то отыскание Минимального произведения для данной логической функции, к счастью, оказывается более легким. На первом щаге берется дополнение F функции F. Если МИНИМИЗАЦИЯ ПРИМЕНИТЕЛЬНО К ПЛУ Структура типичного ПЛУ представляет собой решетку И-ИЛИ, соответствующую логическому выражению вида сумма произведений , поэтому можно подумать, что при проектировании на основе ПЛУ нужна только минимальная сумма произведений. Однако у большинства ПЛУ на выходах решетки И-ИЛИ имеются программируемые инверторы/буферы, с помощью которых любой из выходных сигналов легко инвертировать или пропускать без инверсии. Таким образом, применительно к ПЛУ можно воспользоваться эквивалентом минимальной суммы и на решетке И-ИЛИ реализовать дополнение желаемой функции, а затем осуществить инвертирование, соответственно запрограммировав инвертор/буфер. Большинство профамм минимизации логических функций для ПЛУ автоматически находят как минимальную сумму, так и минимальное произведение и выбирают ту из форм, в которой меньше термов. функция F представлена в виде списка минтермов или в виде таблицы истинности, то найти дополнение совсем легко: просто нули в F заменяются в F на единицы. Затем мы находим минимальную сумму для F по правилам, описанным в предыдущем разделе. Наконец, по обобщенной теореме Де Моргана берем дополнение к результату, что и приводит нас к минимальному произведению для (F) = F. (Обратите внимание, что простое разнесение слагаемых по сомножителям в минимальной сумме для исходной функции не гарантирует того, что получающееся при этом произведение сумм будет минимальным; см., например, задачу 4.61.) В общем случае, для того чтобы построить двухуровневую схему, которая была бы самой дешевой реализацией некоторой логической функции, необходимо найти как минимальную сумму, так и минимальное произведение, и сравнить их. Если в минимальной сумме данной логической функции много слагаемых, то минимальное произведение той же самой логической функции может состоять из меньшего числа сомножителей. Вот тривиальный пример такого сопоставления-функция ИЛИ 4-х переменных: F = (W) + (Х) + (Y) + (Z) (сумма четырех элементарных термов-произведений) = (W + X + Y + Z) (произведение, состоящее из одного терма-суммы). В качестве нетривиального примера приглашаем вас найти минимальное произведение для функции на рис. 4.33, которую мы минимизировали выше; в минимальном произведении всего два терма-суммы. Иногда бывает верно и обратное, как это видно на простейшем примере функции И 4-х переменных; F = (W) (Х) (У) (Z) (произведение четырех элементарных термов-сумм) = {W X Y Z) (сумма, состоящая из одного терма-произведения). Нетривиальным примером является функция, приведенная на рис. 4.29, для которой стоимость реализации произведения сумм больше. У некоторых логических функций стоимость реализации для обеих форм одинакова. Рассмотрим, например, функцию ИСКЛЮЧАЮЩЕЕ ИЛИ 3-х переменных; каждое из минимальных выражений состоит из четырех термов и в каждом терме содержатся три литерала: = (X-Y Z) + (X -Y- Z) + (Х Y Z) + (Х -Y- Z) = (X + Y+ Z) (X + Y+ Z) (X + Y+ Z) (X + Y+ Z). Ho все же в большинстве случаев либо одна, либо другая форма дает лучшие результаты. Рассмотреть обе формы особенно полезно при проектировании устройств на основе ПЛУ. *4.3.7. Безразличные комбинации переменных Иногда требования, предъявляемые к комбинационной схеме, таковы, что не имеет значения, какой сигнал будет возникать на ее выходах при определенных комбинациях входных сигналов. Такие комбинации называются безразличными {dont-care). Это может иметь место по той причине, что значения выходного сигнала при этих комбинациях сигналов на входах и в самом деле не играют никакой роли, либо потому, что при нормальной работе схемы эти комбинации входных сигналов никогда не возникают. Предположим, например, что мы хотим создать устройство для обнаружения простых чисел, 4-разрядное двоичное слово N = N3N2NiNo на входах которого всегда является двоично-десятичной цифрой; в этом случае минтермы 10-15 никогда не нужно будет принимать во внимание. С учетом этого функцию, реализуемую устройством, предназначенным для обнаружения простых двоично-десятичных чисел, можно записать так: F= In3,N2,n No (l,2,3,5,7) + d(10. И, 12,13,14,15). Здесь d(...) - список безразличных комбинаций переменных для данной функции, образующих так называемое d-множество {d-sei). Согласно этой записи функция F должна принимать значение 1 при комбинациях переменных из множества включений (1,2,3,5,7), может иметь любые значения при комбинациях переменных из d-множества и должна равняться О при всех других комбинациях переменных (принадлежащих 0-множеству). Нарис. 4.37 показано, как найти минимальную реализацию суммы произведений для устройства, обнаруживающего простые двоично-десятичные числа, с учетом безразличных комбинаций переменных. Клетки, соответствующие безразличным комбинациям переменных, помечены на карте буквой d. Процедура обведения наборов единиц (простых импликант) видоизменяется следующим образом: При обводе единиц допускается включение клеток, помеченных буквой d, с целью получения наборов возможно большего размера. Это сокращает число переменных в соответствующих простых импликантах. В примере нарис. 4.37 таких простых импликант две: N2 No и N2 Ni. ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |