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

Симметричные таблицы обеспечивают наглядность процедуры минимизации булевых функций с числом переменных 2£n£18. Громоздкость таблицы, неизбежная при увеличении местности функций, компенсируется регулярностью и наглядностью таблиц. Изложение этого метода можно найти в [ii][2]. Симметричные таблицы позволяют:

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

-легко находить максимальные интервалы функции, благодаря свойству симметрии в структуре таблицы;

-автоматизировать процесс минимизации, используя большую степень формализации алгоритма склеивания клеток.

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

Базовой структурой при использовании этого метода является таблица для минимизации функций, имеющих местность 2£n£6. Таблица, соответствующая максимальному числу переменных, содержит 2⁶=64 клеток. Каждая клетка нумеруется двумя восьмеричными цифрами, двоичный код этой последовательности при нумерации переменных справа налево(!) определяет набор значений двоичных переменных функции шести переменных имеет вид (x₆x₅x₄x₃x₂x₁). Для получения восьмеричного кода эта последовательность разбивается на тройки справа налево и каждая тройка замещается соответствующей восьмеричной цифрой. Восьмеричный код клетки обозначим (y₂y₁). В отмеченной симметричной таблице указываются группы по 2^n-1 клетке, в которых указанная при отметке переменная принимает единичные значения. Определение зон прямого и инверсного значений переменных осуществляется следующим образом. Снизу всю горизонтальную строку клеток делят вертикальной линией пополам. Полученные половины также делят вертикальными линиями пополам. Далее полученные части снова делят пополам до тех пор, пока в каждой части слева и справа от вертикальной линии не останется по одной клетке. Тогда для переменной х₁ первая клетка слева представляет инверсное значение х₁, следующие две клетки (удвоенное число)-прямое значение х₁, затем чередуются по две клетки прямое и инверсное значения х₁ до конца, где будет одна клетка, которой приписывается инверсное значение х₁. Для переменной х₂ инверсное значение, как и для остальных переменных, начинается слева, но для двух клеток, следующее прямое значение - для четырех клеток (удвоенное число) и т.д. до конца. Затем для переменной х₃ - области инверсного и прямого вхождений удвоенной длины по сравнению с предшествующей переменной. Для трех старших переменных используется та же процедура справа от таблицы в направлении сверху вниз.

Три младшие двоичные переменные указываются снизу таблицы с возрастанием индекса в направлении сверху вниз, а три старшие переменные - справа от таблицы в направлении слева направо в порядке возрастания индекса переменной. Пример симметричной таблицы для n=6 приведен на рис.9.Таким образом, каждая клетка таблицы имеет свой восьмеричный номер (адрес) и в нее записывается значение функции из строки таблицы с тем же номером.

x 4 x5 x6 y1 y2
0
1	*				*			*
3	*		*	*	*			*
2			*			*	*
6						*	*
7

Рис.9. Отмеченная симметричная таблица для минимизации булевых функций при n=6. Стрелками указаны группы клеток с единичными значениями отмеченных переменных.

Склеивание единиц в таблице осуществляют следующим образом. Любая единица может склеиваться по горизонтали: в группе из двух клеток с другой единицей или незаданным набором, образуя интервал с одной свободной переменной; в группе из четырех клеток, образуя интервал с двумя свободными переменными; в группе из 2^к клеток, образуя интервалы с к свободными переменными, где к£2£n. Аналогично можно склеивать и клетки по вертикали. Склеиванию помогает визуальная симметрия возможных для склеивания клеток.

На рис.9 звездочками и подсветкой отмечены клетки, которые можно склеивать. Номер клетки образуют две цифры-у₂, соответствующая номеру строки таблицы, и у₁, соответствующая номеру столбца. Клетки с номерами 23 и 33 - интервал (01-011) с одной свободной переменной х₄. Клетки с номерами (25,27,65,67) - интервал (-101-1) с двумя свободными переменными х₂ и х₆. Клетки с номерами (10, 12, 14, 16, 30, 32,34,36) - интервал (0-1--0) с тремя свободными переменными х₂, х₃, х₅. Интервалы, соответствующие группам склеиваемых клеток, отмечены сносками.

Основные оси симметрии таблицы выделены жирными линиями. Склеивание 2^к клеток возможно только при условии их симметричного расположения относительно основных или дополнительных осей симметрии таблицы. Например, нельзя склеить четыре рядом расположенные клетки с номерами 62, 65, 66, 67.

Пусть, например, 6-местная частично определенная функция задана следующим образом:

N₁=(-000-1)È(01--10), N₀=(11---1) È(-00-00). Соответствующая симметричная таблица и процедура отыскания максимальных интервалов показаны на рис. 10.

x 4 x5 x6 y1 y2
0				*	*	*	*
1	*	*	*	*	*	*	*	*
3	*	*	*			*	*	*
2	*	*	*			*	*	*
	*			*	*			*
7	*			*	*			*
5	*	*	*	*	*	*	*	*
4				*	*	*	*

Рис.10. Пример минимизации частично определенной 6-местной булевой функции.

Исходные интервалы функции помечены заливкой: единичные - более светлой, нулевые -темнее. Для получения МДНФ склеивают клетки, в которых находятся 1 и *. Результаты склеивания отмечены контурами и выносками. Для данной функции МДНФ=`x<sub>5</sub> x<sub>1</sub> Ú`x₁ x₂.

При увеличении местности функций таблица строится из базовой таблицы из 64 клеток. При числе переменных 6<n£12 каждая часть из 2⁶ клеток считается одной клеткой и нумеруется той же последовательностью чисел-0,1,3,2,6,7,5,4 по горизонтали и по вертикали, но каждая цифра в последовательности означает восьмеричную цифру третьего и четвертого разрядов соответственно восьмеричного кода клетки.

Для 12 <n£ 18 симметричная таблица строится аналогично предыдущей, но теперь базовой клеткой является таблица из 2¹² клеток, а их нумерация той же последовательностью восьмеричных цифр теперь соответствует пятому и шестому разрядам восьмеричного кода клетки.

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

Составление карты для n=7 показано на рис. 11. Каждая клетка нумеруется тремя восьмеричными цифрами, обозначаемыми (y₁y₂y₃). В таблице обозначены основные оси симметрии и два интервала, полученные в результате склеивания 1 и *. Им соответствует МДНФ= x₂ x₃ Ú x₁`x₃.

x4 x5 x6 y3 y2   y1

0

*

*

*

*

*

*

*

*

*

*

*

*

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

2

*

*

*

*

*

*

*

6

*

*

*

*

*

*

7

*

*

*

*

*

*

*

*

*

*

*

*

*

5

*

*

*

*

*

*

*

*

*

*

*

*

*

*

4

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Рис.11. Симметричная таблица для n=7 и пример склеивания единичных и неопределенных клеток для определения МДНФ.

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

ЛИТЕРАТУРА

[i] А.Я. Савельев. Прикладная теория цифровых автоматов. М.: “Высшая школа”, 1987.

[ii] С.П.Плеханов. Симметричные карты - мощное средство минимизации булевых функций при проектировании цифровых устройств больших размерностей. “Электронная техника”. Сер.10. Микроэлектронные устройства, вып. 4(88), 1991.