8.3.7. Визуальный метод минимизации ПФ

Рассмотренный ранее метод Квайна-Мак-Класки минимизации ПФ является универсальным, допускает формализацию и может быть использован при построении систем автоматизации проектирования (САПР) дискретных устройств. Однако наглядность этого метода невысока, и в инженерной практике при минимизации формул функций небольшого числа аргументов (n ≤ 7) применяется визуальный метод минимизации на картах Карно.

Каждой "единичной" (заполненной символом "1") клетке карты Карно для ПФ n переменных соответствует единственный двоичный набор длиной n и, соответственно, единственная элементарная конъюнкция (ЭК) ранга n. Дизъюнкция всех таких ЭК представляет собой СДНФ переключательной функции.

Две смежные "единичные" клетки карты Карно, соседние или симметрично расположенные относительно какой-либо оси симметрии по горизонтали или по вертикали, отмечены соседними двоичными наборами, отличающимися только одним i-м компонентом. Таким парам клеток в СДНФ будут соответствовать ЭК Ax_i и A_i отличающиеся одной переменной x_i.

В СДНФ элементарные конъюнкции Ax_i и A_i могут быть склеены по букве x_i: Ax_i ∨ A_i = A . В силу этого паре смежных клеток карты Карно можно поставить в соответствие конъюнкции (n-1)-го ранга. При этом в конъюнкции (n-1)-го ранга будет отсутствовать переменная, значение которой различно в двоичных наборах, соответствующих склеенным наборам.

Рассмотрим карту Карно для ПФ пяти переменных (n = 5) на рис. 8.31. Для удобства работы с картой на рис. 8.31 в правом нижнем углу каждой клетки карты проставлен десятичный номер соответствующего двоичного набора, отмечающего данную клетку. Будем использовать номер набора в качестве номера клетки. В дальнейшем будем говорить о "единичных" клетках карты Карно.

Клетка 0 имеет смежные клетки с номерами 2, 4, 16. Парам смежных клеток будет соответствовать конъюнкции 4-го ранга в результате склеивания ЭК 5-го ранга,

Рис.8.31

Клетка 2 имеет смежные клетки с номерами 0, 16, 18, в результате склеивания наборов получим:

Клетка 6 имеет смежные клетки с номерами 2, 4, 22, в результате склеивания наборов получим:

Клетка 4 имеет смежные клетки с номерами 0, 6, 20, в результате склеивания наборов получим:

Выделенные пары смежных клеток, в свою очередь, могут вступать в отношение смежности (соседства или симметрии относительно какой-либо из осей симметрии). В результате смежные пары клеток будут образовывать области из 4 смежных клеток, которым будут соответствовать конъюнкции ранга 3:

Следующим шагом индукции будет объединение областей из 4 смежных клеток, которым будут соответствовать конъюнкции 2-го ранга:

Рассуждая по индукции, назовем областью смежных клеток совокупность из 2^k клеток (k ∈ {0,1,...,n}), каждая из которых имеет k смежных с ней клеток из этой области. Каждой такой области можно поставить в соответствие конъюнкции ранга (n-k). Область смежных клеток при k > 0 симметрична относительно какой-либо оси симметрии. В общем случае области смежных клеток могут пересекаться, т. е. иметь общие клетки карты Карно.

Правило покрытия 1.
Любой области из 2^k смежных клеток можно поставить в соответствие конъюнкцию (n-k)-го ранга, состоящую из переменных, которые имеют постоянное значение во всех единичных наборах, соответствующих клеткам области. Причем переменная x_i включается в конъюнкции в прямом виде, если эта переменная имеет значение 1 на всех клетках области. Соответственно переменная x_i включается в конъюнкции в инверсном виде, если она имеет значение 0 на всех клетках области. "Покрытая" область на карте обводится контуром. Дизъюнкция конъюнкции, совместно покрывающих все клетки карты, заполненные единицами, есть одна из ДНФ переключательной функции.

Цель минимизации формулы ПФ по карте Карно - "покрыть" все клетки, содержащие единицы, наименьшим числом конъюнкции наименьшего ранга, т. е. "покрыть" наименьшим числом контуров, каждый из которых охватывает как можно большую область смежных клеток, все клетки, содержащие единицы. Дизъюнкция полученных конъюнкций есть одна из тупиковых (возможно, минимальная) ДНФ функции.

Простым импликантам (минималям) в методе Квайна-Мак-Класки на карте Карно соответствуют области смежных клеток, не являющиеся частью никакой другой области смежных клеток.

Обязательной простой импликанте (экстремали) в методе Квайна-Мак-Класки соответствует область смежных клеток, которая покрывает хотя бы одну единичную клетку, не входящую в состав никакой из других областей смежных клеток.

Пример 3.7.

Минимизируем функцию четырех переменных

Карта Карно для этой функции имеет вид:

Рис.8.32

Построение минимального покрытия начнем с нахождения экстремалей. На рис. 8.32 нетрудно увидеть область смежных клеток {1,3,5,7}, которая единственным образом покрывает клетки 3, 7, следовательно, этой области соответствует экстремаль 0zz1.

Включим экстремаль 0zz1 в минимальное покрытие и перерисуем карту Карно, оставив покрытые клетки пустыми (рис. 8.33).

Рис.8.33

На рис. 8.33 легко увидеть избыточные минимали 000z (область {0,1}) и z101 (область {5,13}), которые называют ущербными кодами. Очевидно, что эти минимали можно безболезненно удалить из дальнейшего рассмотрения. Перерисуем карту Карно еще раз:

Рис.8.34

Из рис. 8.34 следует, что минимали z000 (область {0,8}) и 110z (область {12,13}) являются экстремалями 2-го порядка, поскольку соответствующие им области смежных клеток единственным образом покрывают единичные клетки карты Карно с номерами 0 и 13. Следовательно, эти минимали должны войти в искомое покрытие минимального ранга:

При наличии опыта всю рассмотренную последовательность построения H_min можно выполнить на одной карте Карно, не перерисовывая ее и не выделяя всех минималей.

Рассмотрим особенности построения минимальных КНФ по картам Карно. Учитывая свойство двойственности ДНФ и КНФ функции, по карте Карно можно построить тупиковую (возможно, минимальную) КНФ.

Правило покрытия 2.
Любой смежной области 2^k клеток, заполненных нулями, можно поставить в соответствие дизъюнкцию (n-k)-го ранга, состоящую из переменных, которые имеют постоянное значение во всех нулевых наборах, соответствующих клеткам области, причем переменная x_i входит в дизъюнкцию в прямом виде, если имеет значение 0 на всех клетках области, и, соответственно в инверсном виде, если она имеет значение 1 на всех клетках области. Конъюнкция минимального числа дизъюнкций, совместно покрывающих все клетки карты, заполненные нулями, есть одна из тупиковых (возможно, минимальных) КНФ переключательной функции.

Пример 3.8.

Построить минимальную КНФ функции из предыдущего примера.

Рис.8.35

Построим покрытие минимального ранга всех нулевых клеток карты Карно:

Cравнив ранг МДНФ (8) и МКНФ (10), следует отдать предпочтение МДНФ.

Пред.Страница  След.Страница    Раздел    Содержание