Application of the ternary matrix cover technique to search for a partition of the argument set in decomposition of Boolean functions.pdf Задача декомпозиции булевых функций является одной из важных и сложныхзадач из области логического проектирования, успешное решение которой непо-средственно влияет на качество и стоимость проектируемых цифровых устройств.Поэтому поиск новых эффективных методов решения этой задачи привлекаетмногих исследователей. Как показывает обзор [1], на данную тему написанобольшое количество статей. В данной работе рассматривается задача декомпози-ции системы булевых функций в следующей постановке. Задана система полно-стью определенных булевых функций y = f (x), где y = (y1, y2, …, ym), x = (x1, x2,…, xn), f(x) = (f1(x), f2(x), …, fm(x)). Требуется найти суперпозицию y = ϕ (w, z2),w = g (z1), где z1 и z2 - векторные переменные, компонентами которых служат со-ответственно переменные из подмножеств Z1 и Z2, образующих разбиение множе-ства Х = {x1, x2, …, xn}. При этом число компонент векторной переменной wдолжно быть меньше, чем у z1. Такой вид декомпозиции назван двухблочной раз-делительной декомпозицией [2]. Обычно переменные из Z1 называют связанными,а переменные из Z2 - свободными. В подавляющем большинстве публикаций,рассматривающих данную задачу, подмножества Z1 и Z2 считаются заданными.Вопросу поиска разбиения {Z1, Z2}, при котором данная задача имеет решение,посвящено немного публикаций. Среди работ, где рассматривается данный во-прос, можно назвать работы [1, 3 - 5]. Ниже предлагается метод поиска разбиения{Z1, Z2} множества аргументов Х, который основан на использовании аппаратапокрытий троичной матрицы [6]. Для этого привлекается также понятие компакт-ной таблицы [6], которая так же, как и карта Карно, является двумерной таблицей,но представляющей не только одну функцию, но и систему функций в более сжа-том виде. По компактной таблице довольно просто определяется существованиерешения задачи декомпозиции для заданной системы функций и, если такое ре-шение существует, легко находится соответствующая суперпозиция функций.1. Основные определения. Постановка задачиПусть система полностью определенных булевых функций y = f (x) заданаматрицами U, V, которые являются матричным представлением системы дизъ-юнктивных нормальных форм (ДНФ) заданных функций [2]. Матрица U являетсятроичной матрицей размерности l  n, где п - число элементарных конъюнкций взаданных ДНФ. Столбцы матрицы U помечены переменными x1, x2, … , xn, а стро-ки представляют упомянутые элементарные конъюнкции (интервалы пространст-ва переменных x1, x2, … , xn). Матрица V - булева, ее размерность l  т, а столбцыпомечены переменными y1, y2, … , ym. Единицы в этих столбцах указывают эле-ментарные конъюнкции из заданных ДНФ. Строка и троичной матрицы U погло-щает булев вектор а, если а принадлежит интервалу, представляемому строкой и.Обозначим через Z1 и Z2 некоторые подмножества множества Х = {x1, x2, …, xn}таких, что X = Z1  Z2 и Z1  Z2 = ∅. Через z1 и z2 обозначим векторные перемен-ные, компонентами которых служат соответственно переменные из подмножествZ1, Z2Рассматриваемая задача декомпозиции ставится следующим образом: для сис-темы полностью определенных булевых функций y = f (x) требуется найти супер-позицию y = ϕ (w, z2), w = g (z1), в которой число компонент векторной переменнойw должно быть меньше, чем число компонент переменной z1. Основное вниманиев данной работе уделено поиску таких подмножеств Z1 и Z2, при которых даннаязадача может иметь решение.2. Карта покрытия, компактная таблицаПокрытием ƒ некоторого множества L назовем любую совокупность различ-ных подмножеств множества L, объединение которых совпадает с множеством L.Элементами (блоками) покрытия могут быть как пустое множество, так и самомножество L. Пусть L = {1, 2, ... , l} - множество номеров строк троичной матри-цы U. Покрытие ƒ множества L назовем покрытием троичной матрицы U, есликаждому значению x* векторной переменной х в покрытии ƒ соответствует блок,содержащий номера всех тех и только тех строк матрицы U, которые поглощаютx*. Значению x*, не поглощаемому ни одной строкой матрицы U, соответствуетблок, представляющий собой пустое множество ∅. Другие подмножества множе-ства L не присутствуют в ƒ.Пусть t(x*, U) - множество номеров тех строк троичной матрицы U, которыепоглощают булев вектор x*. Для каждого блока ƒj покрытия ƒ определим булевуфункцию ƒj(x), положив, что для любого x*  {0,1}п выполняется ƒj(x*) = 1, еслиt(x*, U) = ƒj, и ƒj(x*) = 0 в противном случае.Очевидно, покрытие ƒ единственно для конкретной матрицы U. Дизъюнкциявсех булевых функций, приписанных блокам покрытия, равна логической едини-це, и конъюнкция любых двух булевых функций, приписанных различным блокампокрытия, равна логическому нулю [6], т. е. эти функции взаимно ортогональны.Пусть для некоторых матриц U1 и U2 с общим множеством номеров строк Lзаданы соответственно покрытия ƒ1 и ƒ2. Сформируем множество ƒ = {ƒ1i  ƒ2j /ƒ1i  ƒ1, ƒ2j  ƒ2, ƒ1i(x)  ƒ2j(x)  0}. Для каждого элемента ƒ ij = ƒ1i  ƒ2j множестваƒ положим ƒij(x) = ƒ1i(x)  ƒ2j(x). Образуем покрытие ƒ, взяв в качестве его бло-ков все различные элементы множества ƒ. Для всякого блока ƒ s покрытия ƒ оп-ределим булеву функцию ƒ s(x) как дизъюнкцию всех булевых функций, припи-санных тем элементам множества ƒ, которые равны блоку ƒ s. Покрытие ƒ естьпроизведение покрытий ƒ1 и ƒ2 (ƒ = ƒ1  ƒ2). Операция произведения дает воз-можность предложить простой способ вычисления покрытия для троичной мат-рицы U [6]. Этот способ состоит в получении произведения тривиальных покры-тий всех одностолбцовых матриц, представляющих столбцы матрицы U.Определим операцию (ƒi, V) над строками матрицы V, результатом которойявляется вектор y* (y* = (ƒi, V)), получаемый покомпонентной дизъюнкциейстрок матрицы V, номера которых входят в блок ƒi. Если ƒi = ∅, то все компонен-ты вектора y* имеют значение 0. В работе [6] показано, что если ƒi(x*) = 1, тоf(x*) = y* = (ƒi, V).Удобным способом нахождения покрытия троичной матрицы U при неболь-шом числе аргументов является способ, использующий карту покрытия. Картапокрытия аналогична карте Карно. Разница состоит в том, что в любой клеткекарты Карно, соответствующей вектору х*, вместо значения y* = f(x*) = (ƒi, V)помещается множество ƒi = t(x*, U).Пример 1. На рис. 1 представлена некоторая матрица U и ее карта покрытия.Само покрытие имеет вид ƒ = {ƒ1 = ∅, ƒ2 = {1}, ƒ3 = {2}, ƒ4 = {3}, ƒ5 = {1, 2}}. Покарте покрытия, как по карте Карно, легко получить ДНФ булевых функцийƒ1(x) =⎯х1⎯х4 ⎯х1 х3  х2⎯х4  х2 х3, ƒ2(x) =⎯х1⎯х2⎯х3 х4, ƒ3(x) = х1 х2⎯х3 х4, ƒ4(x) = х1⎯х2,ƒ5(x) =⎯х1 х2⎯х3 х4.х4х3∅ ∅ ∅ 1∅ ∅ ∅ 1,2∅ ∅ ∅ 23 3 3 3U =1 2 3 40 0 1 11 0 1 21 0 3x x x x⎡ − ⎤⎢− ⎥⎢⎣ − −⎥⎦х2х1Рис. 1. Пример карты покрытия троичной матрицыПусть пара матриц U, V задает систему полностью определенных булевыхфункций y = f (x) и пусть матрица U1 составлена из столбцов матрицы U, поме-ченных переменными из множества Z1 и матрица U2 - из столбцов, помеченныхпеременными из множества Z2. Покрытиями матриц U1 и U2 являются соответст-венно ƒ1 = {ƒ11, ƒ12, … , ƒ1r} и ƒ2 = {ƒ21, ƒ22, … , ƒ2s}. Построим по покрытиям ƒ1 иƒ2 таблицу M. Столбцам этой таблицы припишем блоки ƒ11, ƒ12, … , ƒ1r и булевыфункции ƒ11(z1), ƒ12(z1), … , ƒ1r(z1), а строкам - блоки ƒ21, ƒ22, … , ƒ2s и булевыфункции ƒ21(z2), ƒ22(z2), … , ƒ2s(z2). На пересечении i-го столбца (1 ≤ i ≤ r) и j-йстроки (1 ≤ j ≤ s) таблицы M поместим значение y* = (ƒ1i  ƒ2j, V). Таблица Мявляется частным случаем компактной таблицы [6]. Она задает систему булевыхфункций y = f(x) следующим образом: на любом наборе аргументов x*, обра-щающем функцию ƒ1i(z1)  ƒ2j(z2) в единицу, значением векторной булевой функ-ции f (x*) является (ƒ1i  ƒ2j, V). Компактная таблица имеет ту же форму, что иизвестная карта декомпозиции [1], с той лишь разницей, что строкам и столбцамкарты декомпозиции соответствуют наборы значений аргументов, а строкам истолбцам компактной таблицы - попарно непересекающиеся множества таких на-боров.Имея компактную таблицу для системы функций y = f (x), легко построить ис-комые системы y = ϕ(w, z2) и w = g (z1). Столбцы компактной таблицы кодируютсядвоичными кодами, причем одинаковые столбцы могут иметь одинаковые коды.Длина кода равна ⎡log2 r⎤ , где r - число различных столбцов компактной табли-цы и ⎡a⎤ - наименьшее целое число, не меньшее а. Таким образом, определенасистема функций w = g (z1). Значением векторной переменной w при любом набо-ре значений векторной переменной z1, обращающем функцию ƒ1i(z1) в единицу,является код i-го столбца (1 ≤ i ≤ r). Естественно, что если длина кода не меньшедлины вектора z1, то при данном разбиении {Z1, Z2} множества аргументов Х за-дача не имеет решения. В противном случае имеющуюся компактную таблицу,столбцам которой припишем значения переменной w, можно считать формойпредставления другой искомой системы функций y = ϕ (w, z2). Значением вектор-ной переменной y при значении переменной w, приписанном i-му столбцу(1 ≤ i ≤ r), и при любом значении переменной z2, обращающем функцию ƒ2j(z2) вединицу (1 ≤ j ≤ s), является вектор, присутствующий в компактной таблице напересечении i-го столбца и j-й строки.Пример 2. Пусть система полностью определенных булевых функций y = f (x)задана парой матриц U, V:U =1 2 3 4 50 0 0 1 10 1 0 0 20 1 0 1 30 0 0 40 0 0 1 51 1 0 1 61 1 1 1 7x x x x x⎡ −⎤⎢ ⎥ −⎢⎢ − ⎥⎥⎢ − −⎥⎢ − ⎥⎢ ⎥⎢ −⎥⎢⎣ − ⎥⎦, V =1 21 0 11 0 21 0 30 1 40 1 50 1 60 1 7y y⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢⎣ ⎥⎦.При разбиении множества аргументов на подмножества Z1 = {х1, х2, х3} иZ2 = {х4, х5} получим следующие матрицы:U1 =1 2 30 0 0 10 1 0 20 1 30 0 40 0 51 1 0 61 1 7x x x⎡ ⎤⎢ ⎥⎢⎢ −⎥⎥⎢ − ⎥⎢ −⎥⎢ ⎥⎢ ⎥⎢⎣ −⎥⎦, U2 =4 51 10 20 1 30 40 1 51 61 1 7x x⎡ −⎤⎢ ⎥ −⎢ ⎥⎢ ⎥⎢ −⎥⎢ ⎥⎢ ⎥⎢ −⎥⎢⎣ ⎥⎦.Для определения длины векторной переменной w в суперпозиции y = ϕ (w, z2),w = g (z1), где z1 = (х1, х2, х3) и z2 = (х4, х5), находим покрытия троичных матриц U1и U2: ƒ1 = {∅, {3}, {5}, {7}, {6, 7}, {1, 4, 5}, {2, 3, 4}} и ƒ2 = {{1, 6}, {2, 4},{1, 6, 7}, {2, 3, 4, 5}}. Соответствующая компактная таблица представлена в видетабл. 1, которая имеет семь различных столбцов. Ясно, что при заданных множе-ствах Z1 и Z2 данная задача не имеет решения, поскольку для кодирования столб-цов компактной таблицы значениями вектора w требуется три переменных, что неменьше длины вектора z1.Т а б л и ц а 1Компактная таблица для системы функций из примера 1∅ 3 5 7 6,7 1,4,5 2,3,41,6 00 00 00 00 01 10 002,4 00 00 00 00 01 01 111,6,7 00 00 00 01 01 10 002,3,4,5 00 10 01 00 00 11 113. Поиск разбиения множества аргументовДля поиска подходящего разбиения множества аргументов, приводящего крешению задачи декомпозиции системы полностью определенных булевых функ-ций, используем покрытия троичных матриц и порождаемые ими компактныетаблицы.Ранее было сказано, что получить покрытие троичной матрицы U можно, ис-пользуя операцию произведения тривиальных покрытий всех одностолбцовыхматриц, представляющих столбцы матрицы U. Покрытие любого столбца троич-ной матрицы состоит ровно из двух блоков: один из них содержит номера одно-элементных строк, состоящих из нулей и знаков «-», другой - номера строк, со-стоящих из единиц и знаков «-». Если столбец состоит из одних нулей или из од-них единиц, то один из блоков покрытия представляет собой пустое множество.Таким образом, если матрица U состоит из п столбцов, то ее покрытие ƒ можнополучить как ƒ = ƒ1  ƒ2  …  ƒп, где ƒi - покрытие i-го столбца (1 ≤ i ≤ п).Пусть требуется найти небольшое количество свободных переменных, состав-ляющих множество Z2 (тогда множество связанных переменных Z1 определитсякак Z1 = Х \ Z2). Для этого используем операцию деления покрытия троичной мат-рицы на покрытие одного ее столбца.Определим операцию деления покрытия ƒ троичной матрицы U на покрытие ƒiее i-го столбца как ƒ / ƒi = ƒ1  ƒ2  …  ƒi - 1  ƒi + 1  …  ƒп. Эту операцию легковыполнить с помощью карты покрытия, которая, так же как карта Карно, имеетоси симметрии, связанные с переменными булева пространства, представляемогоданной картой [2]. Чтобы преобразовать карту покрытия матрицы U в карту по-крытия матрицы, получаемой из U удалением i-го столбца, надо совместить по-парно элементы, симметричные относительно осей, соответствующих переменнойxi, и значением каждого из полученных элементов карты сделать объединениемножеств из совмещаемых элементов. Полученная карта покрытия представитискомое покрытие.Пример 3. Карта покрытия троичной матрицы U из примера 2 представлена нарис. 2. Покрытием матрицы U является ƒ = {∅, {1}, {3}, {4}, {5}, {6}, {7}, {2, 4},{4, 5}, {6, 7}, {2, 3, 4}}. Деление покрытия ƒ на покрытие столбца х1 не меняет ƒ,что видно из карты покрытия, изображенной на рис. 3. Преобразовав эту картуописанным способом по оси симметрии, связанной с переменной х2, получим{∅, {7}, {1, 6}, {2, 4}, {3, 5}, {1, 6, 7}, {2, 3, 4, 5}} как результат деления ƒ на по-крытия yстолбцов(табл. 2) имеет пять различных столбцов, и так же, как в примере 2, задача де-композиции для выбранного разбиения аргументов не имеет решения.Предлагаемый метод поиска подходящего разбиения состоит в выполнениилексикографического перебора и проверки описанным способом для каждого ва-рианта множества Z2 возможности получения решения рассматриваемой задачидекомпозиции.х5х4х34 ∅ ∅ 1 1 ∅ 5 4,52,4 ∅ ∅ 6 6,7 7 3 2,3,4х2Рис. 3. Карта покрытия, полученного от деления ƒ на покрытие столбца х1х5х4х32,4 ∅ ∅ 1,6 1,6,7 7 3,5 2,3,4,5Рис. 4. Карта покрытия, полученного от деления ƒ на покрытия столбцов х1 и х2Т а б л и ц а 2Компактная таблица для разбиения из примера 3∅ 7 1,6 2,4 3,5 1,6,7 2,3,4,5∅ 00 00 00 00 00 00 006,7 00 01 01 00 00 01 001,4,5 00 00 10 01 01 10 012,3,4 00 00 00 11 10 00 11Пример 4. Пусть задана система полностью определенных булевых функцийиз примера 2. Выполняя лексикографический перебор вариантов множества Z2,состоящего из двух переменных, начиная с варианта из примера 3, убеждаемся,что первым подходящим вариантом является, Z1 = {x1, x3, x5}, Z2 = {x2, x4}. Дляэтого варианта из карты покрытия на рис. 2 получаем карту покрытия, изобра-женную на рис. 5, а из нее - карту на рис. 6.х5х4х32,4 ∅ ∅ 1 1 ∅ 3,5 2,3,4,5∅ ∅ ∅ 6 6,7 7 ∅ ∅х1Рис. 5. Карта покрытия, полученного от деления ƒ на покрытие столбца х2х5х31,2,4 ∅ 3,5 1,2,3,4,56 ∅ 7 6,7х2Рис. 6. Карта покрытия, полученного от деления ƒ на покрытия столбцов х2 и х4Т а б л и ц а 3Компактная таблица для разбиения из примера 4∅ 6 7 3,5 6,7 1,2,4 1,2,3,4,51 00 00 00 00 00 10 104,5 00 00 00 01 00 01 016,7 00 01 01 00 01 00 002,3,4 00 00 00 10 00 11 1100 01 01 10 01 11 11Компактная таблица для покрытий ƒ1 = {∅, {6}, {7}, {3, 5}, {6, 7}, {1, 2, 4},{1, 2, 3, 4, 5}} и ƒ2 = {{1}, {4, 5}, {6, 7}, {2, 3, 4}} представлена в виде табл. 3, ко-торая имеет четыре различных столбца, для кодирования которых достаточнодвух переменных. Коды столбцов показаны снизу таблицы.Для построения систем функций y = ϕ (w, z2) и w = g (z1), являющихся решени-ем задачи декомпозиции, требуется получить функции, связанные с блоками по-лученных покрытий. ДНФ функций, связанных с блоками покрытия ƒ1, можнополучить по карте покрытий на рис. 6: ƒ11(z1) = х3⎯х5, ƒ12(z1) = х1⎯х3⎯х5,ƒ13(z1) = х1 х3 х5, ƒ14(z1) =⎯х1 х3 х5, ƒ15(z1) = х1⎯х3 х5, ƒ16(z1) =⎯х1⎯х3⎯х5, ƒ17(z1) ==⎯х1⎯х3 х5. Аналогично получаются функции ƒ21(z2) =⎯х2 х4, ƒ22(z2) =⎯х2⎯х4,ƒ23(z2) = х2 х4, ƒ24(z2) = х2⎯х4. В результате несложной минимизации получим сле-дующие матрицы, представляющие искомую суперпозицию y = ϕ (w, z2), w = g (z1):1 2 2 41 1 0 10 1 1 11 1 01 0 01 1 0w w x x⎡ ⎤⎢ ⎥⎢⎢ − ⎥⎥⎢ − ⎥⎢⎣ − ⎥⎦,1 21 00 11 00 10 1y y⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢⎣ ⎥⎦;1 3 50 00 01 1x x x⎡ −⎤⎢− ⎥⎢⎣ − ⎥⎦,1 21 00 10 1w w⎡ ⎤⎢ ⎥⎢ ⎥⎣ ⎦.Если задаться целью минимизировать длину вектора w, то следует продолжитьпоиск. В данном примере уменьшить длину w не удается, но есть еще один вари-ант: Z2 = {x3, x5}, Z1 = {x1, x2, x4}, при котором длина вектора w также равна двум.ЗаключениеПредложенный метод поиска разбиения множества аргументов при декомпо-зиции системы булевых функций не исключает полного перебора различныхвариантов разбиений, но использование покрытий троичных матриц и связанногос ними представления системы булевых функций в виде компактной таблицыпозволяет довольно просто вести проверку пригодности разбиений для декомпо-зиции.

Скачать электронную версию публикации