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

Рис . 6.8. Пример неполностью заданной функции.

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

Х2

0 гт- г~^1 ^

Хо •ГГ1 р~1 1 0 2;^ ]^ i J

Рис . 6.9. Первичные импликанты для примера, показаного на рис. 6.7.

Отсюда для минимизированной формы получаем:

Без применения термов вида don't care (то есть с d = 0) полу­ чили бы следующую минимизированную форму:

Следовательно, с помощью термов вида don't care функцию мож­ но представить более просто.

6.2.Способ Квина-Мак^Класки

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

6.2. Способ Квина-Мак-Класки

В основе его лежат таблицы, процесс обработки которых соответ­ ствует уравнению (3.34):

Функция представлена с использованием минтермов, выполнен­ ных на основе двоичного эквивалента. Для выступающей в минтерме переменной установлено обозначение 1, для переменной с отри­ цанием — обозначение О и для не появляющейся переменной обозна­ чение (-).

Например:

а;з-13723^0 записывается как: 10-1

Данный способ представим ниже с использованием примера, при­ веденного в табл. 6.1. Минтермы переключательной функции внесе­ ны в таблицу (табл. 6.2), в которой они собраны в группы с одина­ ковым числом 1-элементов. Столбцы содержат: десятичный эквива­ лент и группу (то есть число единичных элементов двоичного экви­ валента) .

Таблица 6.2. Упорядочение минтермов по группам с равным числом 1-эле­ ментов.

Далее в табл. 6.3 в отдельные строчки собраны термы следующих друг за другом групп, отличающихся одним разрядом. Эта таблица является результатом применения уравнения (6.8). Разряд, в кото­ ром элементы различаются, помечен чертой (-). Для формирования десятичного эквивалента внесены десятичные числа минтермов, из которых составлен новый терм.

В данном примере О и 1 могут быть объединены, поскольку они различаются только разрядом xi. Все термы, которые позво­ ляют их объединить, промаркированы в табл. 6.2 знаком (посколь­ ку, например, минтермы О и 1 сплавлены вместе, они маркируются

6.2. Способ Квина-Мак-Класки

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

В том случае, когда в столбце находится только один значок х, соответствующий ему первичный импликант является основным пер­ вичным импликантом. Охваченные им минтермы отмечены знач­ ком в кружке ®. В данном примере минтермы О, 2 и 10 охвачены только основным первичным импликантом О, 2, 8, 10, появившимся в минимизированной DNF. Охваченные им минтермы О, 2, 8 и 10 отмечены, в том числе и в других строках, значком ®.

Таблица 6.5. Приведенная в качестве примера таблица с первичными им­ пликантами

Импликанты 5, 13и13, 15 также являются основными первичны­ ми импликантами, поскольку только они охватьюают по одному минтерму 5 и 15. Охваченные минтермы 5, 3 и 15 отмечены значком (0).

Таблица 6.6. Приведенная в качестве примера таблица с первичными им­ пликантами, минтермы в которой отмечены значком (8).

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

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

функции. Например, р^ля остающегося минтерма 12 могут быть вы­ браны первичные импликанты 8, 12 или 12, 13.

Таблица 6.7. Установление связи между импликантами.

Итак, при применении первичных импликантов 12, 13 можно получить: /(жз,Х2,з;1,д;о) ^ X2-^xiX() V XSX2XQ \/ x^X2-'Xi V -1X2-'а^о (6.9)

или, если применить импликанты 8, 12:

Эти уравнения идентичны минимизированным формам, найден­ ным с помощью диаграммы Карно-Вейча.

6.3. Другие направления оптимизации

Логическая схема, описанная с помощью нормальных форм KDNF и KKNF либо с помощью минимизированных форм DNF и KNF, мо­ жет быть реализована напрямую в виде двухступенчатой управля­ ющей схемы. Следует учитывать, что двухступенчатая схема име­ ет удвоенное время задержки, если мы пренебрегли задержкой ин­ вертора или если в нашем распоряжении имеются инвертированные входные переменные.

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

-Часто управляющая схема должна быть построена на основе вентилей одного типа, например, NOR или NAND;

-Часто задается максимальная величина времени задержки, так что рассматриваться могут только двухступенчатые управля­ ющие схемы;

-Совместно должны минимизироваться большое число функций;