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

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

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

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

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

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

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

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

(Стрелками указаны группы клеток с единичными значениями отмеченных переменных)

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

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

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

На рис.6 звездочками и подсветкой отмечены клетки, которые можно склеивать. Номер клетки образуют две восьмеричные цифры-(у₂у₁), где у₂ соответствует номеру строки таблицы, а у₁ - номеру столбца. Клетки с номерами 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.

y1 y2
				*	*	*	*
	*	*	*	*	*	*	*	*
	*	*	*			*	*	*
	*	*	*			*	*	*
	*			*	*			*
	*			*	*			*
	*	*	*	*	*	*	*	*
				*	*	*	*

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

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

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

Исходные интервалы функции помечены заливкой: единичные - более светлой, нулевые –

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

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

x4 x5 x6 y3 y2   y1

0

*

*

*

*

*

*

*

*

*

*

*

*

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

2

*

*

*

*

*

*

*

6

*

*

*

*

*

*

7

*

*

*

*

*

*

*

*

*

*

*

*

*

5

*

*

*

*

*

*

*

*

*

*

*

*

*

*

4

*

*

*

*

*

*

*

*

*

*

*

*

*

*

	Рисунок 8 Пример минимизации булевой функции 7 переменных

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

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

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

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

Метод таблиц различий

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

Таблица различий содержит |N₀| столбцов и |N₁| строк, именуемые значениями нулевых и единичных интервалов минимизируемой функции соответственно. Каждая из строк таблицы различий содержит n подстрок, соответствующих местности n функции. В каждую клетку таблицы записывают вектор длины n, каждый разряд которого получен применением к одноименным разрядам единичного и нулевого интервалов модифицированной операции суммы по модулю 2, представленной Табл.

Таблица 1 Модифицированная сумма mod2

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

Таблица 2 Применение метода таблиц различий

	Интервалы нулевой области	Допустимые импликанты
Имена переменных	Интервалы единичной области	1-10-	1-001	0-100
x5 x4 x3 x2 x1	- -
x5 x4 x3 x2 x1	-
x5 x4 x3 x2 x1	-

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

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

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

В последнем столбце Табл.2 перечислены все претенденты на роль простых импликант. Им соответствуют максимальные интервалы функции.

Для определения МДНФ построим импликантную таблицу, в которой столбцы будут именоваться именами единичных интервалов, которыми задана функция, а строки – именами максимальных интервалов, соответствующих простым импликантам, полученным в Табл. 2. На пересечении i-й строки и j-го столбца импликантной таблицы записывают 1, если j-й единичный интервал является подмножеством i-го максимального интервала, и прочерк в противном случае, Табл 3.

Таблица 3 Импликантная таблица

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

МДНФ= .

Не нашли, что искали? Воспользуйтесь поиском по сайту: