Минимизация булевых функций многихпеременных в классе ДНФ - итеративный метод и программная реализация | ПДМ. 2009. № 1(3).

Минимизация булевых функций многихпеременных в классе ДНФ - итеративный метод и программная реализация

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

Minimization of Boolean functions of manyvariables - iterative method and program realization .pdf Классическая задача минимизации булевых функций в классе дизъюнктивных нормальных форм (ДНФ) может быть сформулирована следующим образом.Определим произвольную булеву функцию f{x) = f(x\) стандартнымобразом булевым вектором / с 2п компонентами, пронумерованными слева направо, начиная с нуля, причем компонента с номером к задает значение функции / на наборе значений аргументов, представляющем общепринятый двоичный код b числа к.Например, следующий вектор / представляет булеву функцию / шести переменных Х\, Х2, Хз, Х4, Х5, Хб, принимающую значение 1 на 27 наборах значений аргументов, образующих характеристическое множество М1 = {000000, 000011,000101,... , 111110} функции /. Порядковые номера соответствующих компонент вектора / равны 0, 3, 5, ...,62.х\х2хз ж4- - - - - - - - - - - - - - - -ХъХ(,10010101 00100110 00101101 10110010 00010010 01010100 10001001 00111010 /.Заметим, что такой вектор можно интерпретировать как совершенную нормальную форму булевой функции, члены которой представлены единичными компонентами вектора и их кодами. Например, код Ъ =001010 элемента J\q задает полную элементарную конъюнкцию Ж1Ж2Ж3Ж4Ж5Ж6.6А. Д. Закревский, Н. Р. ТороповПроблема заключается в том, чтобы представить заданную вектором / функцию / в ДНФ, желательно минимизированной. Заметим, что традиционные методы решения этой задачи связаны с затратами времени, быстро растущими с ростом п, и становятся практически неприемлемы при п > 20, когда число членов в совершенной ДНФ исчисляется миллионами [1]. В связи с этим в данной работе предлагается оригинальный метод получения ДНФ булевых функций, число аргументов которых может достигать 25. Метод основан на применении эффективных параллельных операций над булевыми 2га-векторами, предложенных в работах [2, 3].К таким операциям относится, в частности, операция конъюнктивного симметрирования вектора / по переменной Хг, обозначаемая ниже через S / Л г. При ее выполнении вектор / разбивается на 2П~1 пар компонент, соседних по переменной Хг, и оба элемента каждой пары получают значение, равное конъюнкции исходных значений этих элементов. Напомним, что соседними называются такие компоненты вектора /, которым соответствуют наборы значений аргументов, различающиеся ровно в одном аргументе.Заметим,что при числе переменных, превышающем 5, удобно представлять вектор / в виде булевой матрицы размером 25 на 2га_5, отображая её 32-компонентные строки словами в компьютерной памяти (что адекватно для большинства современных компьютеров). Тогда любые два элемента вектора /, соседние по переменной Хг, будут принадлежать к одному слову, если г < 6, и к разным словам в противном случае, что можно использовать для ускорения вычислений.1. Построение булевой матрицы соседства NНа первом этапе предлагаемого метода посредством гг-кратного применения операции S / Л г строится булева матрица соседства N размером n x 2П. Каждая строка Пг этой матрицы представляет результат выполнения операции S / Л г при конкретном значении параметра г (от 1 до и). Матрица N отображает структуру характеристического множества М1 функции f(x), на котором эта функция принимает значение 1. Элемент п^ матрицы N принимает значение 1, если и только если k-й элемент вектора / равен 1 и имеет соседа по переменной Хг, также со значением 1. Таким образом, г-я строка этой матрицы отображает (единицами) подмножество элементов из М1, имеющих в этом же множестве соседей по переменной Хг, а к-& столбец показывает, по каким переменным имеет соседей соответствующий элемент из М1, представленный к-& компонентой вектора /.Продемонстрируем получение матрицы N на примере того же вектора /, задающего случайную булеву функцию шести переменных:/ =10010101 00100110 00101101 10110010 00010010 01010100 10001001 00111010,0001000000000100 00001001 00110010 00010000 00000100 00001001 0011001000000101 00100010 00000101 00100010 00000000 00010000 00000000 000100000000010000000100 00100000 00100000 00010000 00010000 00001000 00001000N =0001000100100010 00000000 00100010 00000000 01000100 10001000 001000100000010100000000 00000101 10100000 00000000 01010000 00000000 0000101000000000 00000000 00001100 00110000 00000000 00000000 00000000 00110000.Минимизация булевых функций72. Матричное представление ДНФВ аналогичной форме булевыми вектором д и матрицей D той же размерности, называемыми вектором решения и матрицей решения, предлагается представлять и искомую ДНФ, рассматриваемую как некоторую совокупность интервалов булева пространства М = {0,1}га. В векторе д отмечаются некоторые содержащиеся в интервалах элементы множества М1, по одному для каждого интервала, а в столбцах матрицы D отмечаются внутренние переменные этих интервалов.Рассматривая векторы fug как множества отмеченных в них элементов пространства М, а матрицы N и D - как подмножества декартова произведения множеств х и М, сформулируем очевидноеУтверждение 1. д С / и D С N.Другими словами, вектор решения д и матрица решения D могут быть получены соответственно из вектора / и матрицы N заменой в них некоторых единиц на нули, как это и делается в описываемом в данной статье методе.Для рассматриваемого примера искомая ДНФ будет выглядеть следующим образом:д =10010100 00000110 00101000 10010000 00000010 01000000 10000001 00001000,00010000 00000100 00000000 00010000 00000000 00000000 00000001 00000000 00000100 00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00100000 00000000 00000000 00000000 00000000 00000000 ~ 00000000 00000010 00000000 00000000 00000000 00000000 10000000 00000000 00000100 00000000 00000000 10000000 00000000 01000000 00000000 00001000 00000000 00000000 00001000 00010000 00000000 00000000 00000000 00000000.В более известной форме эта ДНФ задается троичной матрицей, столбцы которой представляют элементарные конъюнкции {х{Х2Х^х^с^х^)'Х2Х^х^х^>х&) и т. д.)10-0-0000-11 1-1200-0-1 1 1 100 1 1 130001 1-0 110100 1400 1 1-0 1 0010-1 1501-0 1 10-11-01-6011100-0-01010.Число р конъюнкций в полученной ДНФ равно весу вектора решения д, а длина ДНФ (сумма рангов конъюнкций) равна рп - q, где q - число единиц в матрице D.Заметим, что введенные выше булевы матрицы и векторы при программной реализации предлагаемого метода обрабатываются во внутренних циклах и, следовательно, должны быть представлены в оперативной памяти, что ограничивает их допустимый размер. Учитывая параметры персонального компьютера, можно утверждать, что данный метод достаточно быстро реализуется на нем, если число переменных минимизируемой булевой функции не превышает 25.3. Выделение элементов с малым числом соседейПостроение реализующей функцию / ДНФ целесообразно начать с поиска элементов ядра решения - обязательных простых импликант высокого ранга. Назовем обязательной такую простую импликанту функции /, которая входит в любую кратчайшую8А. Д. Закревский, Н. Р. ТороповДНФ этой функции. Поиск облегчается предварительным выделением в векторе / элементов характеристического множества М1 с небольшим числом соседей, поскольку именно такие элементы могут определять импликанты высокого ранга, отображаемые элементарными конъюнкциями со многими литералами.Число соседей у элементов вектора / со значением 1 можно представить конечно-значным вектором w/=10010101 00100110 00101101 10110010 00010010 01010100 10001001 00111010 ги=0..2.3.3 ..2..22. ..1.23.3 1.62..3. ...2..0. .2.3.2.. 1...3..1 ..332.3.,однако более удобно, в перспективе программной реализации последующих вычислений, рассортировать элементы по числу соседей и представить результат серией булевых векторов rrii, в которых единицами отмечены элементы с г соседями. Для рассматриваемого примера, при г < 4, получим/ =10010101 00100110 00101101 10110010 00010010 01010100 10001001 00111010, то =10000000 00000000 00000000 00000000 00000010 00000000 00000000 00000000, Шг =00000000 00000000 00100000 10000000 00000000 00000000 10000001 00000000, т2 =00010000 00100110 00001000 00010000 00010000 01000100 00000000 00001000, га3 =00000101 00000000 00000101 00000010 00000000 00010000 00001000 00110010.Эти векторы, образующие соответствующую булеву матрицу М, легко получить эффективными покомпонентными операциями над строками матрицы N, что существенно ускоряет поиск подходящих импликант.4. Нахождение простых импликантОбозначим через tk троичный вектор, получаемый из вектора Ъ (кода элемента f\) присвоением значения - компонентам, отмеченным единицами в столбце nk матрицы N. Его можно интерпретировать как некоторый интервал Intfc пространства М = = {0,1}га, а также как соответствующую элементарную конъюнкцию, которая может оказаться простой импликантой функции /.Утверждение 2. Вектор t представляет обязательную простую импликанту функции /, если и только если Intfc С М1.Утверждение 3. Для каждой обязательной простой импликанты функции / в матрице N найдется столбец nk, соответствующий которому троичный вектор t представляет эту импликанту.Легко находятся обязательные простые импликанты ранга п - они непосредственно представляются элементами множества М1, не имеющими соседей. Они отмечаются в векторе Too и представляются соответствующими столбцами матрицы N, не содержащими единиц. Аналогично, все обязательные простые импликанты ранга п- 1 отмечены в векторе ГП\ ж также представлены соответствующими столбцами матрицы N - они содержат по одной единице.Выявление обязательных простых импликант меньшего ранга несколько сложнее. Однако оно достаточно просто для ранга п - 2 и п - 3, осуществляясь посредством покомпонентных операций над некоторыми столбцами матрицы соседства N.Утверждение 4. Предположим, что fc-й элемент вектора / имеет двух соседей. Тогда вектор t представляет обязательную простую импликанту функции /, если и только если j-я компонента вектора / равна единице, где Ь3 = Ъ ф nk.Минимизация булевых функций9Например, Ь27 0 п27 = 011011 0 100001 = 111010, j = 58 и /58 = 1, следовательно, троичный вектор t27 = -1101- представляет обязательную простую импликанту.Утверждение 5. Предположим, что k-й элемент вектора / имеет трех соседей. Тогда вектор tk представляет обязательную простую импликанту функции /, если и только если пк ^ nj (вектор пк поглощается вектором nJ), где У = Ьк 0 пк.Доказательство этого утверждения основано на том факте, что векторы Ъ и ЬР являются противолежащими элементами в интервале Int^ ранга 3 и вместе со своими соседями покрывают все восемь элементов этого интервала (рис. 1).кРис. 1Утверждение 6. Предположим, что к-й элемент вектора / имеет четырех соседей. Тогда вектор tk представляет обязательную простую импликанту функции /, если и только если пк ^ nJ для трех (это минимальное число) значений индекса j, которые можно определить в соответствии с рис. 2.Рис. 2Возникает вопрос о практической целесообразности проверки компонент вектора / на выполнение условий, сформулированных в утверждениях 4-6. Предположим, что задана булева функция от п переменных с вероятностью 1/2 значения 1 в каждой компоненте, независимо друг от друга. Рассмотрим некоторую компоненту со значением 1 и к соседями. Насколько вероятно, что эта компонента определяет соответствующую простую импликанту ранга п - к?Утверждение 7. Вероятность такого события равна 1/2* , где t = 2к - (к + 1).Эта вероятность быстро стремится к нулю. Например, при к = 2, 3,4 и 5 она равна 1/2, 1/16, 1/2048 и 1/67 208 864 соответственно, будучи независима от п.10А. Д. Закревский, Н. Р. ТороповПоэтому в предлагаемом эвристическом алгоритме анализу подвергаются лишь такие единичные компоненты вектора /, число соседей у которых не превышает трех.5. Алгоритм получения частичного решенияВ предлагаемом алгоритме последовательно находятся импликанты высокого ранга. Результат фиксируется введением единиц в вектор решения д (сначала д = 0), определением соответствующих им столбцов матрицы решения D и корректировкой вектора /*, представляющего множество еще не покрытых элементов характеристического множества М1.1.д := то, /* := /\то. Так находятся импликанты ранга п (в данном примере этодве импликанты, задаваемые векторами 000000 и 100110 и определяемые элементамивектора / с номерами 0 и 38).2.Последовательно рассматриваются элементы вектора /, отмеченные одновременно в векторах mi и /*. Для очередного элемента / берется соответствующийему набор Ъ , компонента которого, отмеченная единицей в столбце nk матрицы соседства N, заменяется на символ «-». Результат представляет простую импликантуранга тг - 1. Соответственно корректируются векторы д и /*: в первый добавляетсяодна единица, а из второго удаляются две.Так, в данном примере последовательно рассматриваются элементы с номерами к = 18,24,48 и 55, которым соответствуют наборы 010010, 011000, 110000 и 110111 и которые определяют простые импликанты ранга п-1: 01-010, 0110-0,110-00, -10111. Вектор решения принимает значениед = 10000000 00000000 00100000 10000000 00000010 00000000 10000001 00000000и соответственно (в результате удаления поглощаемых элементов они отмечены подчеркиванием) меняется значение вектора /*:/* = 00010101 00100110 00001100 00010010 00010000 01010100 00000000 00111010.3. На этом этапе рассматриваются последовательно элементы fk с двумя соседями, отмеченные одновременно в векторах Ш2 и /*, и строятся импликанты ранга п - 2.Сначала находятся элементы fk, удовлетворяющие условию утверждения 4. Соответствующие компоненты вектора д принимают значение 1, столбцы d матрицы D остаются равными столбцам пк матрицы N, и из вектора /* удаляются единицы, покрываемые интервалами Int^.Если же условие утверждения 4 не выполняется, из двух соседей элемента / выбирается один сосед, желательно еще не покрытый, в столбце d остается лишь одна соответствующая единица и выполняется операция, предусмотренная для элемента с одним соседом.В данном примере (он оказывается довольно простым) это приводит к окончательному решению - покрытию всех элементов характеристического множества М1, получению пары векторовд =10010100 00000110 00101000 10010000 00000010 01000000 10000001 00001000, /* =00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000и построению матрицы решения D, получаемой из N удалением одной единицы в столбцах, отмеченных в векторет2 = 00010000 00100110 00001000 00010000 00010000 01000100 00000000 00001000,Минимизация булевых функций11и удалением всех единиц в столбцах, не отмеченных в векторе д :00010000 00000100 00000000 00010000 00000000 00000000 00000001 00000000 00000100 00000010 00000000 00000000 00000000 00000000 00000000 00000000 D = 00000000 00000000 00100000 00000000 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 10000000 00000000 00000100 00000000 00000000 10000000 00000000 01000000 00000000 00001000 00000000 00000000 00001000 00010000 00000000 00000000 00000000 00000000.4. Если вектор /* остается отличным от нуля, рассматриваются элементы с тремя соседями, отмеченные одновременно в векторах тз и /*. Находятся элементы, удовлетворяющие условию утверждения 5, в решение вводятся соответствующие импли-канты ранга п - 3. При невыполнении данного условия находятся определяемые этими элементами импликанты более высокого ранга: п - 1 и п - 2.В результате описанной процедуры обработки элементов вектора /, имеющих не более трех соседей, мы получаем множество импликант, образующих частичное решение S и вектор /*, представляющий остаток - совокупность не покрытых этим решением элементов множества М1.6. Итеративный алгоритмИдея этого эвристического алгоритма состоит в следующем. Сначала он находит частичное решение для вектора /, затем выполняет такую же операцию для остатка /*, дополняя множество получаемых импликант и соответственно упрощая вектор /* (удаляя из него некоторые единицы). Если после упрощения /* в нем остаются единицы, выполняется следующая итерация и так далее, пока /* не станет равным нулю.Получаемые при этом импликанты могут быть далеко не обязательными и даже не простыми. Поэтому в заключение они приводятся к простым (понижением ранга), а также устраняются получаемые дубли.Продемонстрируем алгоритм на конкретном примере. Пусть п = 19 и каждый элемент вектора / принимает значение 1 с вероятностью р = 1/4. При этом предположении был сгенерирован случайный вектор / с 147 232 единицами и построена матрица соседства N с 219 = 534 288 столбцами и следующим распределением столбцов по числу единиц в них (N(i) столбцов содержат по г единиц):г = 0 1 2 34 567 8 9 10 11 12 13 1415 16,N(i) = 296 2087 7180 16352 25357 29868 26913 19406 11379 5401 2087 690 172 35 8 1 0.При первой итерации алгоритма обрабатываются элементы множества М1 с числом соседей г = 0,1, 2 и 3, всего 296 + 2087 + 7180 + 16352 = 25915 элементов. Находятся определяемые ими обязательные простые импликанты, общим числом 296 + 2082 + + 1974 + 80 = 4432. Общее число найденных при первой итерации простых импликант (вместе с необязательными) равно 24 379. Они отмечаются в векторе решения д, и покрываемые ими элементы удаляются из переменного вектора остатка /* (вначале равного /). Число единиц в векторе /* становится равным 81 910.При второй итерации рассматривается новая матрица N, представляющая отношение соседства на элементах множества М1, отмеченных в векторе остатка /*. В этом12А. Д. Закревский, Н. Р. Тороповвекторе выявляются элементы, имеющие не более трех соседей в этом же векторе, находятся соответствующие ими импликанты. Векторы д и /* получают новые значения. Если после этого /* ф 0, выполняется следующая итерация.Так для рассматриваемого примера выполняются четыре итерации, прежде чем вектор /* становится равным 0 - все элементы множества М1 оказываются покрытыми 61 477 импликантами со следующим распределением их по рангам (ранг - число импликант):19-2 458,18 - 33 668,17 - 25 237,16 - 114.Как уже говорилось, не все эти импликанты оказываются простыми. Поэтому в заключение выполняются две процедуры приведения полученного решения к корректному виду. Первая из них упрощает импликанты, обращаясь к исходной матрице соседства N и удаляя из импликант некоторые литералы, если это возможно. Она приводит к новому распределению импликант по рангам:19 - 296,18 - 20 933,17 - 38 617,16 - 1 631.Вторая процедура устраняет дубли среди полученных импликант, в результате чего число последних сокращается до 60 972, а распределение их по рангам принимает следующий вид:19 - 296,18 - 20 933,17 - 38 353,16 - 1 390.7. Компьютерные экспериментыИзложенный выше итеративный алгоритм был программно реализован на СН-Ь и испытан на компьютере (Pentium IV, 2.8 GHz). Чтобы было удобней работать с булевыми векторами, в которых перечислены соседи для рассматриваемых элементов вектора /, матрица соседства N предварительно транспонировалась.Эксперименты проводились на множестве псевдослучайных булевых функций, с двумя параметрами: числом переменных п и плотностью единиц г, определяющей ожидаемое число единиц q в представляющем булеву функцию / векторе /: г = 32q/2n. Например, при г = 16 рассматривается абсолютно случайная булева функция, принимающая на каждом элементе булева пространства значение 1 с вероятностью 1/2.Прежде всего, были определены границы практической применимости предложенного алгоритма в пространстве параметров пи г. Дело в том, что при достаточно большом значении параметра г алгоритм может прекратить свою работу после некоторого числа итераций, поскольку числа iV(0), iV(l), iV(2) и iV(3) могут оказаться равными нулю, в то время как вектор /* будет оставаться отличным от 0.Например, если п = 17иг= 15, алгоритм останавливается после восьми итераций, найдя всего 636 импликант. Но при гг=17иг = 14он находит после 90 итераций 20 077 импликант, полностью покрывающих множество М1 (после последующего упрощения этих импликант и устранения дублей их число сокращается до 19 811). Следовательно, пара (п,г) = (17,14) является элементом верхней границы области применения алгоритма.В табл. 1 представлены основные характеристики этой границы, полученные экспериментально. Строки таблицы соответствуют числу переменных п (от 4 до 23) и соответствующим им максимальным значениям параметра г, при которых программа работает корректно. Кроме того, в строках показаны следующие величины:N - число единиц в векторе / (число импликант в совершенной ДНФ функции /);Минимизация булевых функций13С - число импликант в полученной ДНФ;S - длина полученной ДНФ (сумма рангов импликант);Qk - число импликант ранга к в полученной ДНФ (при к = п, те-1, те-2, те-3, те-4);It - число итераций;Т - затраченное время, в с.Таблица 1 Экспериментальные характеристики границы области применения алгоритматегNСSЦ;гаQn-iQn-2Qn-3Vra-4ItT41653101200010,00516168270350010,006163114621490010,007166231169112180010,00816138583602182810020,009162741077440157220030,001016556194151301412753030,0011161083379335513525093040,01121622037357127031456242650,0313164337141415057045835526870,09141687342780322660641579111621120,3515151640453136732411683258185827*131,011614310211018113982714126671307324133,12171461150198112915071684128426224609024,3718131143473800750035741809266709476482142,2619122126207234312207427478753693138223412148201139299513721524629963412639104999195053810610211178634527064251218755421491207248417767318249922101442274512529102551221275885239902954478431088582392620069966357203864904811586667405946659719831064Табл. 2 отображает поведение алгоритма при числе переменных те = 17. Видно, как растет число итераций It и время решения Т при возрастании плотности единиц г. При этом распределение полученных импликант по рангам быстро изменяется в пользу импликант меньшего ранга.Таблица 2 Поведение алгоритма при числе переменных те = 17тегNСSQl7QmQl5QuQ13ItT172122857856127689228352832900020,2717420427111171772051147816218026020,5317628594137612156044178406488751031,90178365071562124072213563708883233034,041710447561734826317841386412456986146,4917125299918691279341618801389928961078,43171461150198112915071684128426224609024,5214А. Д. Закревский, Н. Р. ТороповПоведение алгоритма при максимально возможном для него числе переменных (п = 24) показано в табл. 3. При увеличении плотности единиц г на единицу время решения Т растет более чем вдвое, достигая 6,8 ч при г = 4.Таблица 3 Поведение алгоритма при числе переменных п = 24пгNСSQ24Q2SQ22Q21Itт24110473506858811598259722316344688915829021693,45242157153291968221231157148570701045700353224068,76243209559011242932575921485794853387184905207310695,152442619724129794629532155445858893353628641162324348,00ЗаключениеВ предлагаемом алгоритме минимизации булевых функций многих переменных (до 24) реализованы следующие идеи. 1) Роль элементарных операндов играют булевы векторы с 2П компонентами, представляющие произвольные булевы функции п переменных. 2) Строится булева матрица соседства N размером n x 2га, отображающая структуру характеристического множества М1. 3) С ее помощью быстро находятся простые импликанты четырех старших рангов, покрывающие часть множества М1. 4) Структура остатка представляется новой матрицей N, находятся новые импликанты высокого ранга и т. д. Итерации прекращаются, когда множество М1 становится пустым. 5) В заключение полученные импликанты доводятся до простых и устраняются дубли. Алгоритм реализуется эффективной программой, которая может оказаться полезной при решении систем булевых уравнений, верификации логических схем и решении других трудоемких задач теории булевых функций.

Ключевые слова

булевы функции , ДНФ , минимизация

Авторы

ФИООрганизацияДополнительноE-mail
Закревский Аркадий Дмитриевич Объединенный институт проблем информатики НАН Беларуси член-корр. НАН Беларуси, доктор технических наук zakrevskij@tut.by
Торопов Николай Романович Объединенный институт проблем информатики НАН Беларуси кандидат физико-математических наук
Всего: 2

Ссылки

Закревский А. Д. Логический синтез каскадных схем. М., 1981.
Zakrevskij A. D. Parallel operations over neighbors in Boolean space //Proceedings of the Sixth International Conference CAD DD-07. Minsk, 2007. V. 2. P. 613.
Закревский А. Д. Программирование вычислений в многомерном булевом пространстве // 7-я Российская конф. с международным участием «Новые информационные технологии в исследовании сложных структур». Томск, 2008
 Минимизация булевых функций многихпеременных в классе ДНФ - итеративный метод и программная реализация             | ПДМ. 2009. № 1(3).

Минимизация булевых функций многихпеременных в классе ДНФ - итеративный метод и программная реализация | ПДМ. 2009. № 1(3).

Полнотекстовая версия