Раздел: Документация
0 ... 5 6 7 8 9 10 11 ... 119 а)
в) Рис. 1.2 3-куба и двух 2-кубов, которым соответствуют контермы х2, x3xi и x3xi, поэтому МДНФ данной функции f{v) = х2 V x3xi Vx3xi. Минимальное же покрытие 0-клеток состоит из двух 1-кубов, которым соответствуют контермы x3x2xi и х3х2хь поэтому МКНФ этой функции /И = (Х3 V Х2 V Х!)(Х3 V Х2 VX!). Из МДНФ и МКНФ не составляет труда получить МНФ в базисах И-НЕ и ИЛИ-НЕ. Выбор m-кубов, покрывающих 1-клетки диаграммы Вейча, не всегда столь очевиден, как-это было в предыдущих примерах. На рис. 1.2.в часть 1-клеток можно было бы покрыть 2-кубом (ему соответствует контерм x4xi), однако при покрытии 1-куба.ми остальных четырех 1-клеток становится понятным, что необходимость использования 2-куба отпадает. МДНФ этой функции /(") = x4x3x2 Vx3x2xi Vx3x2X! Vx4x3x2. Таким образом, не всегда следует начинать покрытие 1-клеток с отыскания m-кубов максимального размера. Сформулируем общие правила минимизации функций с помощью диаграмм Вейча, справедливые для любого числа переменных га: для получения МДНФ необходимо найти минимальное покрытие 1-клеток, которое состоит из минимального числа т-кубов максимального размера; m-кубу, покрывающему 2т 1-клеток, соответствует контерм, не зависящий от т переменных, причем исключаются те т переменные, которые в прямоугольной области на диаграмме Вейча, состоящей из 1-клеток, имеют различное значение хр и хр; прямоугольные области на диаграммах Вейча, используемые при покрытии функции f{v), могут состоять только из 2т 1-клеток, где т = 0,1,..., га, т.е. из 1, 2, 4, 8, 16 и т.д. 1-клеток; покрытие следует начинать с выбора тех 1-клеток, которые могут войти в один и только один m-куб, а затем выбранные таким образом 1-клетки покрываются m-кубами максимального размера (это правило позволяет исключить возможность появления лишних m-кубов, как это могло иметь место в примере на рис. 1.2,в); если 1-клеток, входящих только в один m-куб, нет, то следует рассмотреть несколько вариантов минимизации. а)
в) г)
Рис. 1.3 Диаграммы Вейча для числа переменных га > 4 составляются из идентичных ДВ*-4 (в смысле обозначения сторон первичными термами хРр). Знак "*" означает, что имеется несколько одинаковых ДВ-4. На рис. 1.3 представлены диаграммы Вейча для га = 5 и 6 (ДВ-5 и ДВ-6). Две ДВ*-4 будем называть соседними, если они имеют общую грань. Клетки, расположенные в одинаковых местах соседних ДВ*-4, являются соседними, так как им соответствуют соседние минтермы. Так, например, клетки с номерами 0 и 16, 5 и 21 и т. п. (рис. 1.3,а), 0 и 16, 0 и 32, 5 и 21, 5 и 37 и т. п. (рис. 1.3,в) являются соседними, но клетки 0 и 48, 5 и 53, 16 и 32 и т. п. (см. рис. 1.3,в) не являются соседними, так как они расположены не в соседних ДВ*-4. Легко убедиться в том, что та-кубы, расположенные в одинаковых местах двух соседних ДВ*-4, образуют та + 1-куб. С учетом этого МДНФ функции f(y), представленной на рис. 1.3,5, имеет вид: /( ) = x3xi V х2Х\ V х5х4 V хх4Х\. В ДВ-6 та-кубы, расположенные в одинаковых местах всех четырех ДВ*-4, образуют та + 2-куб. Поэтому МДНФ функции, показанной на рис. 1.3,г, /(f) = х4х3 V Х5Х4Х1 V ХбХ4хг V х6х5х4. Основываясь на сформулированных выше правилах минимизации с помощью диаграмм Вейча, достаточно просто также отыскивать МДНФ функций семи и восьми переменных. Для этого нужно только подходящим образом выбрать способ расположения 23 = 8 и 24 = 16 ДВ*-4 на ДВ-7 и ДВ-8. Удобнее всего располагать эти ДВ*-4 так, как и клетки на ДВ-3 и ДВ-4, т.е. на рис. 1.1 и 1.2 следует заменить хр на хр+4, а каждую клетку заменить на ДВ*-4. Тогда соседними будут те же ДВ*-4, что и клетки на рис. 1.1 и 1.2. Правила покрытия та-кубами 1-клеток функций трех и четырех переменных полностью переносятся на покрытие одинаковых m-кубов (по размеру и местоположению на ДВ--4) на ДВ-7 и ДВ-8. Модификация диаграмм (карт) Вейча, введенных в 1952 г., известна под названием карт Карно (1953 г.) [7, 9]. Известны также методы минимизации Квайна - Мак-Класки, Блейка и ДР- [7]. 1.12. Минимизация неполностью определенных функций, совместная минимизация нескольких функций Основная задача минимизации неполностью определенных функций заключается в отыскании оптимального варианта ее доопределения, позволяющего получить минимальную из всех возможных ДНФ или КНФ. Если значения функции не заданы в та точках, то ее можно доопределить 2т способами. Поэтому минимизация неполностью определенной функции состоит в оптимальном выборе одной из 2т полностью определенных функций (понятно, что, как и при минимизации полностью определенных функций, может быть получено несколько равноценных МДНФ и МКНФ). Совершенную ДНФ неполностью определенной функции /(f) можно представить в виде f{v) = \J K4{v)V*-\J Kh{v), где v = (xn,...,xi); и - номера тех точек области определения, в которых функция /(f) имеет значение 1, т.е. /(fij = 1, а гф - номера тех точек, в которых функция /(f) имеет неопределенное значение, т.е. /(ф) = Ф- Пусть задана СДНФ неполностью определенной функции четырех переменных х4, хз, х2 и х\\ /(f) = Ао V А4 V А7 V А8 V Ф • (Aj V А5 V А6 V А9 V Ai2), где К,- = A,(f), v = (х4,хз,Х2,х1). Составим для этой функции диаграмму Вейча (рис. 1.4). Для этого в клетки с номерами i = 0,4,7 и 8 следует занести значения функции, равные 1, а в клетки с номерами » = 1,5,6,9 и 12 - неопределенные значения Ф. С помощью диаграммы Вейча легко найти все минимальные покрытия, полагая либо Ф = 0, либо Ф = 1. На рис. 1.4 представлены два варианта доопределения функции /(f), которые дают минимальные ДНФ: f(y) = х4х3 Vx2xb /(f) = Х4Х3 V х3х2 (ф = 0, если символ Ф не вошел ни в один m-куб, и Ф = 1, если он вошел хотя бы в один m-куб). VfCV)Х1/Су?
Рис. 1.4 Аналогично этому можно найти и МКНФ данной неполностью определенной функции, произведя оптимальным способом доопределение инверсной функции /(f): 7(f) = х4х3 V х3х2, /(f) = (х4 V х3)(х3 V х2). Для данной функции имеется только один способ доопределения, дающий минимальную КНФ. Следует иметь в виду, что в результате минимизации неполностью определенных функций всегда получаются полностью определенные функции. Комбинационные схемы. Логическая схема (рис. 1.5), выходные сигналы zq которой описываются системой переключательных функций Zq - fq(xn,...,Xi),(1-84) где хр - входные сигналы логической схемы, р = 1,2, q = 1,2,называется комбинационной схемой (КС). Из (1.84) следует, что КС реализует однознач-„ г ное соответствие между значениями вход-, z ных и выходных сигналов. 2При реализации функций zq, описыва- " z* ющих выходные сигналы КС, используются логические элементы (ЛЭ), выпускаемые в 1.5виде интегральных схем. Условные графи- ческие обозначения таких ЛЭ, выполненные в соответствии с требованиями ЕСКД [12], представлены на рис. 1.6. кс Повторитель CBu er) хх И <ди» - а или сою - 1 НЕ СЛОТ, Inverter) И-НЕ СНАНЮ ИЛИ-НЕ СПОЮ х- 1 -хх,- &-x2xtх, -j 1 -х2 V х, И-ИЛИ-НЕ (ДНВ-НОЮ Исключающее ИЛИ СХОЮ Мажоритарный элемент CMajority Gate) x3x2v Рис. 1.6 Совместная минимизация нескольких функций. При синтезе КС, имеющих несколько выходов zq, независимая минимизация каждой функции fq(xn,..., хх), как правило, не дает наилучшего результата в смысле суммарного числа первичных термов, требуемых для представления всех функций. МДНФ функций f\(v) и /2(f), заданных диаграммами Вейча (рис. 1.7), имеют вид fi(v) = х4х3 V X4X2, /2(i>) = х4х3 V х3х2.(1.85) На рис. 1.8,а показана КС, реализующая эти функции. Из рис. 1.7 следует, что функции f\(u) и /2(f) можно представить 1
/2С»>
Рис. 1.7 а) -Iй 1 -/, Рис. 1.8 1 -/.
Рис. 1.9 МДНФ МНФ в базисе И-НЕ I- & МНФ в базисе И-ИЛИ-НЕ МКНФ МНФ в базисе ИЛИ-НЕ Рис. 1.10 0 ... 5 6 7 8 9 10 11 ... 119
|
