Файл: Вводый курс цифровой электроники (К.Фрике, 2003).pdf

6.1. Минимизация с помощью диаграмм Карно-Вейча

законом (уравнение (3.34)):

На основе этого могут быть образованы весьма большие области полей с 1. Но приемлемы только прилегающие друг к другу области с 1, 2, 4, 8 и т.д. полями. Эти поля описываются конъюнкцией входных переменных, которые называются импликантами. При этом мыслен­ но соединяют левую сторону полей с правой стороной, точно также как и верхнюю сторону с нижней. Импликант, состоящий из 4 вход­ ных переменных, состоит из одного поля (в случае функции с че­ тырьмя переменными). Если импликант имеет на одну переменную меньше, то при этом число полей удваивается. Поэтому А,ЛЯ мини­ мизации затрат на вентили формируются максимально возможно большие поля.

Х2

Р и с . 6.3. Диаграмм Карно-Вейча с минтермами функции из табл. 6.1

Находим для области 1 импликант Д:

область /i = жо~'^1^2

Убеждаемся, что никакой другой из импликантов полностью не перекрывает Д. Импликант функции Д называют первичным импликантом, поскольку не имеется какого-либо другого импликанта /х, который бы полностью перекрывал Д. Импликанты дизъюнк­ тивной формы (DNF) называют термами логического произведения (product term).

Приведенные в примере импликанты промаркированы цифра­ ми от 1 до 5. Иные первичные импликанты подобрать нельзя. Для других маркированных первичных импликантов можно с помош;ью

Глава 6. Логические схемы

переменных на краю диаграммы определить конъюнкции, которые однозначно образуют следующие области:

область 2: I2 = х^Х2Х^ область 3: /з = -i 3:1X2X3 область 4: /4 = -^x^^xix^ область 5: /5 = -^хо-^Х2

В диаграмме ^\ля четырех входных переменных область из четы­ рех полей соответствует импликанту с двумя переменными, как это имеет место ^\ля импликанта /5. Этот импликант лежит в четырех углах диаграммы, которая рассматривается как связанная.

Различают:

-основные, первичные импликанты Рк-

Первичный импликант является основным первичным импликантом в том случае, если он не перекрывает дизъюнкции всех других первичных импликантов. Следовательно, основные им­ пликанты соответствуют 1, которую они в одиночку покрыва­ ют. Основные первичные импликанты в каждом случае пред­ ставляются в минимизированной форме DNF.

-абсолютно элиминируемые первичные импликанты Р4:

Первичный импликант элиминируем (то есть устраним) в том случае, когда он полностью перекрывается основным первич­ ным импликантом. Он является избыточным.

-относительно элиминируемые первичные импликанты PR\

Все остальные первичные импликанты называются относитель­ но элиминируемыми первичными импликантами. Выборка отно­ сительно элиминируемых первичных импликантов может быть взята из минимизированной формы DNF.

Например, имеются множества:

Минимизированная переключательная функция составляется из ос­ новных первичных импликантов а выборка из относительно элими­ нируемых первичных импликантов таким образом, чтобы все минитермы были покрыты. Следовательно, упрощенная функция будет

справедлива тогда, когда устраняются относительно элиминируе­ мые первичные импликанты 4:

И тогда, когда элиминируются первичные импликанты 3:

f {xs,X2,xi,xo) = xo-'rz:iX2 V XQX2XS у -^XQ-^XIXS V ->хо-':г2 (6.3)

6.1.2. Минимизация нормальной KKNF

Метод минимизации KKNF основывается на использовании макстермов. На местах единиц следует рассматривать нули. В анало­ гичном приведенному вьппе примере в диаграмму вносятся макстермы.

хг

Рис. 6.4. Диаграмма Карно-Вейча с макстермами для функции из табл. 6.1.

Действуя по тем же правилам, что и при определении DNF, отме­ тим возможно наибольшие области полей с 0. Отмеченные на рис. 6.4 области представляют собой первичные импликанты конъюктивнои нормальной формы (KNF). Они представленны дизъюнкциями вход­ ных переменных, которые вне данных областей выдают значения функции, равные 1:

область 1: 1\ = х^У ^Х2У х^

область 2: /2 = -> :го V а;2 область 3: 1^ = -^ххУ -^Х2У xz область 4: 1^ = -^х^У -^Х2У х^

область 5: /5 = жо V -> ^i V -«^2

178 Глава 6. Логические схемы

Следовательно, в данном примере получаем множества:

РА = 0

Минимальную форму можно получить путем применения основ­ ных первичных импликантов и импликанта /з*

(6.4)

= (жо V -I Ж2 V xs) (-> хо V Х2) (-> Ж1 V -1Ж2 V хз) (д^о V -1Ж1 V -1Х2)

Вторую из возможных минимальных форм KNF можно вывести с помощью применения основных первичных импликантов и импли­ канта Ц:

=

{хо V ^ :Г2 V хз) (-^ Хо V Х2) (^ гго V -^ гп V xs) (:го V ^ ^i V -1Х2)(6.5)

6.1.3.Диаграммы Карно-Вейча для 2, 3, 4, 5, 6 входных переменных

Здесь вы можете найти порядок составления различных диаграмм Вейча с внесенными десятичными эквивалентами. Диаграммы Кар­ но-Вейча с более чем пятью переменными применяются очень редко, поскольку они не наглядны.

Рис. 6.5. Диаграммы Карно-Вейча для 2 и 3 входных переменных.

6.1.4. Неполностью заданные функции.

Иногда функция задается неполностью. В таком случае некоторые значения функций могут быть выбраны произвольно. Они марки­ руются в диаграмме Карно буквой d (don't care). Эти don't care

хз

Рис . 6.7. Диаграмма Карно-Вейча для б переменных.