Минимизация булевых функций с помощью матрицы Квайна

Табличный метод построения множества минималей Квайна–Мак-Класки

Метод Квайна - Мак-Класки предназначен для нахождения множества минималей (простых импликант) для функций, заданных совокупностью наборов, на которых функция равна единице, или дизъюнктивной совершенной нормальной формой. Если Cⁿ(ц) - множество кодов, определяющих функцию ц, то наборы и , отличающиеся значением только одного компонента у_i, можно склеить и получить набор ранга n-1. Выполняя все возможные склеивания наборов , можно построить множество наборов C^n-1(ц) для заданной функции. Если операцию склеивания повторить для кодов ф ∈ C^n-1(ц), то можно получить множество кодов C^n-1(ц). Повторяя подобным образом операции склеивания, можно последовательно получить множества C ^n-1(ц), C ^n-2(ц),...,C¹(ц), если, конечно, они существуют. При этом коды, которые не были использованы для получения кодов меньшего ранга, т.е. коды, которые не покрываются кодами меньшего ранга, образуют искомое множество минималей.

Чтобы упростить процедуру поиска склеивающихся кодов, используют таблицу, состоящую из n столбцов. В первый столбец таблицы заносят коды множества Cⁿ(ц). Склеивание кодов этого множества возможно лишь в том случае, если коды отличаются значением только одного компонента. Поэтому коды в этом столбце можно разместить, разделяя их на группы так, чтобы в каждую группу входили коды, имеющие одинаковое число единиц. Группы целесообразно расположить таким образом, чтобы число единиц в кодах каждой последующей группы было на единицу больше, чем в предыдущей. При таком размещении склеивание возможно только между кодами, расположенными в соседних группах. В результате склеивания кодов соседних групп может быть получено множество кодов ранга n-1, которые будут иметь одинаковое число единиц. Полученные коды расположим в столбце n-1, сохраняя разбиение по группам с одинаковым числом единиц и располагая группы в порядке возрастания числа единиц. Для кодов в полученном столбце можно повторить операцию склеивания для соседних групп и построить множество кодов ранга n-2. Сохраняя разбиение на группы и упорядочение групп, в каждом из последующих столбцов можем найти множества C^n-3(ц), C^n-4(ц),..., C¹(ц).

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

В качестве иллюстрации описанного способа рассмотрим следующий пример.

Пример 3.2.

Требуется найти множество минималей для функции ц(x₁, x₂,x₃,х₄)={0000, 0001, 1000, 0011, 0101, 0111, 1100, 1101} из примера 3.1.

Таблица 3.1

C^4(ц)	C^3(ц)	C^2(ц)	C^1(ц)
0000 ∨
0001 ∨1000 ∨	000zz000
0011 ∨0101 ∨1100 ∨	00z1 ∨0z01 ∨1z00
0111 ∨1101 ∨	0z11 ∨01z1 ∨110z z101	0zz1

Построим таблицу из четырех столбцов и поместим в первый столбец таблицы заданные коды, предварительно разбив их на группы по числу единиц, как это показано в табл.3.1. Выполняя операцию склеивания смежных кодов, расположенных в соседних группах, и помечая коды, использованные для склеивания, получаем коды ранга три, которые записаны во второй столбец табл.3.1. В этом столбце коды также разделены на группы с одинаковым числом единиц. Выполняя операцию склеивания для смежных кодов в соседних группах, получаем коды ранга два, которые запишем в третий столбец. Поскольку в рассматриваемом примере получается всего один код ранга два, то процесс заканчивается, и множество кодов, не имеющих отметок в таблице, представляет собой множество минималей

Q = {000z, z000, 1z00, 110z, z101, 0zz1}.

Полученный результат может быть изображен геометрически в виде совокупности граней гиперкуба, как это показано на рис. 8.27.

Рис.8.27

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

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

соответствующих отдельным клеткам карты Карно:

{0,2} ≈ {00000, 00010} = 000z0, {0,4} ≈ {00000, 00100} = 00z00,
{0,16} ≈ {00000, 10000} = z0000.

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

{2,0} = {0,2} ≈ 000z0, {2,6} ≈ {00010, 00110} = 00z10,
{2,18} ≈ {00010, 10010} = z0010.

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

{6,2} = {2,6} ≈ 00z10, {6,4} ≈ {00110, 00100} = 001z0,
{6,22} ≈ {00110, 10110} = z0110.

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

{4,0} = {0,4} ≈ 00z00, {4,6} = {6,4} ≈ 001z0,
{4,20} ≈ {00100, 10100} = z0100.

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

{0,2,16,18} = {{0,16},{2,18}} ≈ {z0000, z0010} = z00z0,
{0,4,16,20} = {{0,16},{4,20}} ≈ {z0000, z0100} = z0z00,
{2,6,18,20} = {{2,18},{6,22}} ≈ {z0010, z0110} = z0z10,
{6,4,22,20} = {{6,22},{4,20}} ≈ {z0110, z0100} = z01z0

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

{0,2,6,4,16,18,22,20} = {{0,2,16,18},{6,4,22,20}} ≈ {z00z0, z01z0} = z0zz0.

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

Правило покрытия 1

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

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

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

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

Пример 3.7.

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

y(x₁, x₂, x₃, x₄)={0000,0001,1000,0011,0101,0111,1100,1101}.

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

Рис.8.32

На рис. 8.32 выделены все области смежных клеток, соответствующие минималям:

{0,1} ≈ {0000,0001} = 000z, {0,8} ≈ {0000,1000} = z000,
{12,8} ≈ {1100,1000} = 1z00, {12,13} ≈ {1100,1101} = 110z,
{5,13} ≈ {0101,1101} = z101, {1,3,5,7} ≈ {0001,001,0101,0111} = {00z1,01z1} = 0zz1.

Построение минимального покрытия начнем с нахождения экстремалей. На рис. 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.35

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

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

Дата добавления: 2015-07-07