2.7. Минимизация булевых функций по картам Вейча

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

1. Минимизируемая функция заносится на карту в двоичных кодах.

2. Производится склеивание единиц (для ДНФ) или нулей (для КНФ) по эвристическому правилу: использовать наименьшее число наиболее крупных склеек для получения минимальных ДНФ (КНФ).

3. Можно склеивать 1, 2, 4, 8, …, 2^k соседних клеток. В записи склеек для карты на переменных будет букв, т.е. чем крупнее склейка, тем меньше букв в ее записи.

4. Каждая клетка может входить одновременно в несколько склеек, если это соответствует п. 2.3.

5. Не всегда включение в решение самых крупных склеек дает минимальную форму (пример 2.10).

6. На карте можно находить существенные импликанты и строить ядро покрытия функции.

7. Обработку карт можно совмещать с обработкой таблиц покрытий по методу Петрика.

Рассмотрим некоторые особенности минимизации по картам Вейча на примерах.

Пример 2.10. Задана функция от 4-х переменных . Найти минимальные формы функции в ДНФ и КНФ.

Решение. Заносим наборы функции на карту Вейча (рис. 2.18).

Находим наиболее крупные возможные склейки. Такая склейка одна (единицы по углам) - - показана на карте. Чтобы склеить остальные единицы, требуется еще 4 склейки ( , - показаны точками на карте). Но получается, что эти 4 склейки покрывают все единицы карты и, следовательно, склейка - лишняя и включение ее в решение даст не минимальную ДНФ, а сокращенную. Дело в том, что перечисленные склейки образуют существенные импликанты. Для обнаружения таковых заметим что единицы, помеченные точками, допускают единственные склейки, т.е. являются существенными импликантами.

Рис. 2.18. К примеру 2.10	Рис. 2.19. К примеру 2.10 для КНФ

Таким образом, минимальная ДНФ заданной функции будет равна

.

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

Для склеивания всех нулей нужно еще добавить 4 склейки по две переменных каждая и получим значение функции в КНФ.

.

Снова замечаем, что для получения тупиковой формы (она же минимальная и кратчайшая) достаточно включить в решение 4 последних члена, а первый член оказывается лишним, так как дает сокращенную, а не тупиковую формы.

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

Окончательно получим

. (2.21)

Рис. 2.20. К примеру 2.11

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

Пример 2.11. Минимизировать функцию в ДНФ по картам Вейча.

Решение. Занесем функцию на карту Вейча. Так как функция полностью определена, то в клетки запишем только единичные наборы. Кроме того, пронумеруем единичные наборы по порядку. Это упростит обращение к каждой единице по номеру (рис. 2.20) Составим таблицу покрытий, в строчки которой запишем возможные склейки по следующему правилу: Если имеется более крупная склейка, то более мелкие ее составляющие в таблицу не записываются. Если записана, например, склейка клеток (1,3) то склейка (3,1) не записывается.

Сведем в табл. 2.21 все возможные склейки карты.

Обработка таблицы покрытий практически не отличается от метода Квайна–Мак-Класки. Ищутся существенные импликанты, вычеркиваются столбцы и находятся минимальные или кратчайшие покрытия.

Так, существенными импликантами являются склейки (2,9) и (3,5) образующие ядро покрытия. Вычеркиваем столбцы (3,5,2,9). Оставшиеся столбцы можно покрыть склейками (1,7), (4,6) и (6,8) или (7,8), или (8,9). Это равноценные формы по количеству букв и количеству членов. В табл. 2.21 показаны склейки для первой тупиковой формы.

Таблица 2.21. Обработка таблицы покрытий

Склейки	№ клетки
	1	2	3	4	5	6	7	8	9
1,7
1,3
2,9
3,4
3,5
4,6
6,8
7,8
8,9

Переходя от склеек к формулам можно записать:

. (2.22)

Тот же результат можно получить, применив к табл. 2.21 метод Петрика.

С увеличением размерности карт количество вариантов и сложность нахождения оптимальных схем сильно возрастает, ведь даже функции от 4-х переменных могут иметь 10-40 тупиковых форм. (По крайней мере, автору встречались такие функции.) При ручной минимизации перебор вариантов энтузиазма ни у кого не вызовет, но компьютерный анализ подтверждает это, (правда, варианты почти не отличаются по количеству членов, поэтому все варианты анализировать нет смысла). Много тупиковых форм бывает у функций, не имеющих существенных импликант, тем более в функциях 5-ти 6-ти и более переменных. Но в практических задачах обычно можно применить методы карт Вейча. Рассмотрим на примере 5 переменных обработку карт Вейча.

Пример 2.12. Минимизировать функцию в ДНФ .

Решение. Наносим функцию на карту так же, как в предыдущем примере по координатам клеток, приведенным в п. 2.6. Вместо единиц записываем их порядковые номера. Нули не записываем. Получаем карту (рис. 2.21).

Рис. 2.21. К примеру 2.12

Анализируя карту, отыскиваем самые крупные склейки. Напомним, что можно склеивать клеток ( ). При этом в записи склейки выпадает переменных и остается переменных, для чего надо уметь находить соседние клетки (см. п. 2.6). Для самоконтроля удобно использовать следующее правило: чтобы узнать, разрешена ли рассматриваемая склейка на клеток, надо проверить, можно ли ее записать с помощью переменных. Если это удается, то склеиваемые клетки соседние; в противном случае – так склеивать нельзя.

Если все 32 клетки – единицы, то функция равна 1, если склеиваются 16 единиц, то останется одна переменная. Здесь таких областей нет.

Рассмотрим, есть ли импликанта на 8 клеток. Клетка с единицей для кода 00000 имеет соседние единицы – 2,3,5,13,15,16,17, причем эта единица, порождает существенную импликанту на 8 клеток.

Проверим, можно ли записать эти единицы двумя переменными? Да, можно, это - .

Единица 9 образует существенную импликанту на 4 клетки – 2,3,8,9. Эти клетки соседние. Соседними являются также клетки – 6,10,11,12 с существенной импликантой в 12-й клетке. Эти склейки показаны на рис. 2.21. Они образуют ядро покрытия:

.

Остальные 3 единицы 4,7,14 допускают склеивание только по 2 клетки.

Запишем возможные варианты импликант на 2 клетки и ядро покрытия. Получим 8 тупиковых форм функции, каждая из которых является и минимальной и кратчайшей

.

Над записью функции в числителях и знаменателях записаны номера склеиваемых единиц.

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

Пример 2.13. Минимизировать карту на 6 переменных, если функция равна 1 на следующих наборах:

Решение. Находим на карте клетки соответствующие двоичным значениям заданных наборов и пронумеруем по порядку единичные наборы (рис. 2.22).

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

Обзор карты показывает, что склеек на 8 и более клеток нет.

Рис. 2.22. К примеру 2.13

Клетка 1 порождает существенную импликанту на 4 угловых клетки (1,3,20,22), которая запишется как . Единица 15 образует существенную импликанту на 4 клетки (6,9,15,18) - . Единицы (4,10,14,19) образуют существенные импликанты на 2 клетки - , , , , - соответственно. Единица 12 одна образует существенную импликанту, так как не склеивается - . Больше существенных импликант нет. Оставшиеся единицы можно склеить импликантой на четыре клетки (2,11,13,21) - , и двумя импликантами по две клетки (7,8) - и (16,17) - .

Окончательное решение запишется следующим образом:

Вертикальная черта отделяет существенные импликанты от остальных. Функция содержит 10 членов, 48 букв.

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

Здесь же мы рассмотрим факторный алгоритм на конкретном примере.

Пример 2.14. Задана функция 6-ти переменных, равная 1 на следующих наборах:

Найти скобочную форму функции, используя факторный алгоритм.

Решение. Используя методику минимизации примера 2.13 получить минимальную ДНФ (предоставляется выполнить самостоятельно). Получится функция:

. (2.23)

Обозначим конъюнкции полученного выражения буквами A, B, C, D. Тогда функцию можно представить элементами множества .

Находим попарные пересечения всех элементов множества . Получаем результат пересечений:

; ; ; ; ; .

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

.

Обозначим ; ; .

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

.

Обозначим ; , получим множество . Пересечение . Получаем окончательную скобочную форму

. (2.24)

Она имеет 9 букв, тогда как минимальная ДНФ содержит 14 букв.

Недостатком реализации БФ в скобочной форме является увеличение времени задержки сигнала при прохождении через логическую схему (п. 2.1). Чем больше скобок в представлении функции, тем больше задержка и меньше быстродействие. Как уже было сказано в п. 2.1, при реализации функции в КНФ или ДНФ не может быть больше трех каскадов (ярусов) при наличии инверторов. В логике используется также термин “глубина” схемы.

Количество каскадов можно найти по схеме или подсчитать по формуле из скобочной формы (2.24):

Начиная построение схемы с внутренней скобки, получаем часть схемы

,

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

,

для которой, также нужны 2 каскада. Наконец, - требует еще одной конъюнкции. Получается 5 каскадов. Для реализации инверсных переменных нужен еще один каскад. Общая задержка , т. е. на 3 каскада больше.

Найдем цену по Квайну для схемы по формулам 2.23 и 2.24.

,

.

Видно, что цена по Квайну для ДНФ незначительно больше цены для СФ, поэтому разработчик должен решать, что для данной схемы важнее – экономичность или быстродействие.