Опадчий Ю.Ф., Глудкин О.П., Гуров А.И. Аналоговая и цифровая электроника (2000) (1095415), страница 101
Текст из файла (страница 101)
Что отражают теоремы булевой алгебры7 Сформулируйте теоремы Де-Моргана, поглощения и склеивания. 12. Приведите классификацию логических устройств по спосо. бу ввода-вывода переменных; по принципу действия. ГЛАВА !$. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ УСТРОЙСТВ !ад. целы а!иииа1мздции лОГЙЧЕСких УСТРОЙСТВ В предыдущей главе было показано, что логическую схему, реализующую заданный алгоритм преобразования спгналов, можно синтезировать непосредственно по выражению, представлен.
ному в виде СДНФ или СКНФ. Однако полученная прн этом схема, как правило, не оптимальна с точки зрения ее практической реализации, Поэтому исходные ФЛЛ обычно минимизируют. 8!8 Целью минимизации логической функции является уменьшение стоимости ее технической реализации. Следует отметить, что сам критерий, в соответствии с которым выполняется минимизация ФАЛ, далеко не однозначен и зависит как от типа решаемол задачи, так и уровня развития технологии. Так, в те времена, когда цнФровые устройства строились на дискретных элементах, минимизация числа этих элементов и числа построенных на их основе элементарных логических узлов однозначно определяла н уменьшение стоимости технической реализации.
С появлением БИС и СБИС, стоимость которых определяется в основном площадью схемы на кристалле и мало зависит от чксла входящих в нее транзисторов и других элементов, критерии мнкимизации ФАЛ претерпели существенные изменения. На первое место прн ироекгированнн самих ИС выдвигается требование регулярности их внутреннем структуры и минимизация числа внешних соединений даже за счет увеличения числа элементов н внутренних соединений. Эти требования диктуются требованиями повышения надежности электронных средсгн. Однако при проектировании аппаратуры с применением БИС и СБИС требование умеишиеиня числа корпусов ИС и их межгоедииений по-прежнему остается весьма важным.
Требование уменьшения числа элементарных ЛЭ, входящих в разрабатываемое устройство, в настоящее время так ке не потеряло своей актуальности. Объясняется это все более широким использованием прн проектировании электронных средств программируемых логических СБИС широкого применения н полузаказиых СБИС на основе ба~оных матричных кристаллов. Эти СБИС и БНС, как правило. содержат отдельные нескоммутированиые между собой элементарные ЛЭ, например 2И вЂ” НЕ нли 2ИЛИ— НЕ, или просто наборы транзисторов, резисторов н яиодов.
которые могут быть соединены между собой в соответствии с заданным алгоритмом обработки логических сигналов. Поскольку число элементов в одной СБИС задано из технологических соображений, то минимизация ФАЛ по критерию уменьшения числа используемых элементов позволяет иа одном кристалле решать бо. лее сложные задачи логической обработки сигналов, т, е. в конечном счете уменьшать число требуемых ИС и связей между яимн. Это снижает стоимость и повышает надежность электроиион аппаратуры.
Рассмотрим ряд методов, позволяющих провести минимизацию ФАЛ по критерию уменьшении числа элементарных ЛЭ. 1ВЛ. ОБЩИЕ ПРИНИИПЫ МИНИМИЗАМИИ Наиболее просто и наглядно гадача минимизации ФАЛ решается с использованием ее кубических представлений.
Ранее было 5!9 показано, что любая логическая функции л-переменных характеризуется своим кубическим комплексом К(х), образованным кубическими комплексами Ко, К!... К„=!. Из кубического комплекса К(г) всегда можно выделить множество кубов П(г), таких. что каждый член комплекса Ко, т. е. першина куба будет вклю. чеи по крайней мере в одни куб из множества П(е). Множество кубов П(х) называется покрытием комплекса К(г) илп покры.
гнем логической функиин, Вполне очевидно, что для любой ФАЛ сушествует несколько ее покрытии. В свою очередь, каждому покрытию П(г), так же как и самому комплексу. соответствует своя дизьюнктивиая нормальная форма, получаемая логическим суммированием лоп!ческих произиедений, соответствующих выделен. иым кубам ФАЛ. Пример 1б.!. <хтя кубического комикелса из ирнмера НК!2 ваагн иокры тия ФАЛ. Р е щ е н и е. Кубический лонилекс ФАЛ имеет вик К1 ) = !Ш 1; 100; 101: 1!О; 1! 1; .! 1: Ич !.1; 10; 1-0; 1"). Ну,асмой кубический комплекс вкзючмет все вершины куба (см.
рис. !4,3). ио. этому образует иокрытие Фуилщи< П<1«)=Ко-(О!11 100: 101~ 1Кй 11!). Все неравны ктба включак<тся токмо а единичный кубический комилекс К, иозтону ои так ке образует иокрытие ФАЛ Па(х) К< [-11: 11; 1 1; !Оч 1-0). Перебирая сочетание кубов раззныиых рщиъв мол но ии.<учить слеиующие ко. крытия ФАЛ: Пз(х) К. !011; 1!к 10-) И<(2) К<= 1-! 1; 1-1; 1 01, Пл(х) =К< !011; 1-), По(х) =Ко 1 11; 1-) и т к, Соответствующие указанным покрытиям ДНФ имеют вна х< 1«) .=- х,х,хе+«тз,хо+«.х<хо+ хо«<хо+хтх,хо, хо(х) «<хо+<ах<в«а<о+хе«<+тахо, ха (х) = хоз'< хо+ хзх < ч хзх < х,(х) ха«о+«,хо4-« хо, хо(х) =ха«<«в+хм хв(х) =«<ха+хо.
Сложность полученной такил! образом ДНФ принято характеризовать понятием «г(еио покрытия» (Цо), которая равна сумме цен всех кубов, составляюших данное покрытие П(т); Цч=Е Нл, 320 В свою очередь. цена одного г-куба ФАЛ п.переменных определи. ется лак разность полного числа входных переменных и ранг.> соответствуюшего куба, т, е, равна числу п«ременных в соответст. вуюшей дизъюикцин: Пе=п — г.
Так, для ФАЛ трех переменных ценя 0-куба равна трем, а 2-куба — единице. В соответствии со сказанным, задача минимизации ФАЛ сво. антея к поиску покрытия П(з) кубического комплекса К(г), имеющего минимальную цену. Покрытие П(г) комплекса К(г), имеющее минимальную цену, называется покрытием Квайпи, ы соответствующая это>чу покрытию ДНФ вЂ” называется минимальной ДОФ (МДНФ). )Зх. МИНИа)ИЗдцмя ЭАЛ С НСПОЛЬЗОВАНИСВ) Кпрт ППИЧА Данный метод базиру«гся на табличном виде представления ФАЛ, Он широко использугхн и при ручной, без применения ЭВМ, минимизации ФАЛ, число и«р«менных в >шторой обычно не превышает пяти.
Карта Вейча — это прямоугольная таблица, число клеток в которой для ФАЛ и-пер«м<ниых равно 2", каждой нз клеток поставлен в соответстын«н«который набор входных переменных, причем рядом располож«оным клеткам соответствуют соседние наборы входных пер«м«нных (кодов), а в самих клетках записаны значения функции, определенные для этих кодов. Рассмотрим постро«нне карт Вейча длл функций двух, трех, четырех н пяти пер«м«нных. Карта Вейча функции двух переменных приведена на рнс.15,1. Она содержит четыр«клетки н является плоской фигурой. Для удобства использования по краям карты указаны значения входных переменных. которые для соответствующих строк и столбцов остаются постоянными.
Набор переменных для заданной клдткн таблицы определяется как совокупность аргументов, постоянных для строк н столбцов, на пересечении которых она расположена. Карта Вейча функции трех переменных приведена на рис. 15.2.. Она содержит и<>семь ллеток. Наборы входных переменных, с<ютветств)юшцс крайним левому и правому столбцам, являются со- х, Ле> хе) 1(х>, хе) 1(хь хе) Ихь хе) хе Рве. 15.!. Карта Выпча фуыкнаы двух керенеыынх х, )(хз хьха) ((хз, хь хз) )(хь хь х.) ) (хз, хь хз) хз хз хз Рис 152 Карта Вейте функции трез неремеииыз седними. Поэтому данную карту удобно представить как поверхность цилиндра н она, в отлична от карты двух переменных, является объемной фигурой.
Карта Вейча функции четырех иеремеиных приведена на рнс. 15.3. Она содержит )6 клеток. Очевндзю, что наборы входных переменных, соответствующие крайним левому и правому столбцам, как н в карте длн трех переменных, являются соседними. Кроме этого соседние коды содержатся в нижней и верхней строках карты. Поэтому данная карта тоже является объемной фигурой н может быть представлена как поверхность тора. Еще более сложную форму имеет карта Вейча функции пяти переменных, Ее можно представить как две карты Вейча функции четырех переменных, расположенные одна над другой н отличающиеся лишь значением одной переменной.
Геометрически это можно представить как два тора, один из которых расположен в другом, Соседким кодам тут дополнительно соответствуют клетки, расположенные на разных торах одна под другой. Ввиду сложности работы с такимн картами, данный способ редко используется при минимизации ФАЛ пяти переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
