Implementation of a system of incompletely specified Boolean functions in a circuit of two-input gates by means of bi-decomposition

Cover Page

Cite item

Full Text

Abstract

The problem of bi-decomposition of a Boolean function is to represent a given Boolean function as a logic algebra operation over two Boolean functions. A meth-od based on bi-decomposition of Boolean functions is suggested to implement sys-tems of incompletely specified (partial) Boolean functions in the basis of two-input gates. This basis can be the basis of NOR gates, NAND gates or the basis of AND and OR gates with accessible input complements. The used method for bi-decomposition is reduced to the search for two-block weighted cover of a complete bipartite weighted graph with complete bipartite subgraphs (bi-cliques). The graph represents differences between the rows of Boolean matrices that specify the given system of partial Boolean functions. The system is given by two Boolean matrices, one of which represents the domain of Boolean space where the values of the given functions are specified, and the other the values of the functions on the elements of the domain. Every bi-clique in the obtained cover is assigned in a certain way with а set of variables that are the arguments of the function. This set is the weight of the bi-clique. Every of those bi-cliques defines a Boolean function whose arguments are the variables assigned to it. The functions obtained in such a way constitute the re-quired decomposition. The process of synthesis of a combinational circuit consists in successive application of bi-decomposition to the obtained functions. The meth-od for two-block covering the orthogonality graph of rows of ternary matrices is de-scribed.

Full Text

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

Существует довольно много различных видов декомпозиции булевой функции [1]. Одним из таких видов выступает алгебраическая декомпозиция. Задача алгебраической декомпозиции (в англоязычной литературе – bi-decomposition) ставится следующим образом. Для заданной булевой функции у = f(x), где компонентами вектора x = (x1, x2, …, xn) являются булевы переменные, составляющие множество Х, требуется найти суперпозицию f(x) = ϕ(g1(z1), g2(z2)), где компоненты векторов z1 и z2 – переменные из множеств Z1 ⊆ X и Z2 ⊆ X соответственно. Вид функции ϕ от двух переменных также задан. Это может быть любая из 10 булевых функций, существенно зависящих от обеих переменных и представляемых операциями алгебры логики. Обычно множества Z1 и Z2 заданы и Z1 ∩ Z2 = ∅. Такая декомпозиция называется разделительной в отличие от неразделительной декомпозиции, где условие Z1 ∩ Z2 = ∅ необязательно, но при этом на мощности множеств Z1 и Z2 могут быть наложены ограничения.

Существуют разнообразные методы решения как разделительной, так и неразделительной алгебраической декомпозиции при заданных множествах Z1 и Z2 [2–7]. Вопрос определения множеств Z1 и Z2, для которых существует нетривиальная алгебраическая декомпозиция булевой функции, имеет особый интерес. Нетривиальной считается декомпозиция, если числа аргументов функций g1 и g2 меньше числа аргументов функции f. Среди публикаций, где рассматривается задача подходящей пары множеств Z1, Z2 для получения нетривиальной декомпозиции, можно назвать работы [1, 5, 8–11]. В [12] решается задача алгебраической декомпозиции, где множества Z1 и Z2 определяются в процессе решения задачи. Метод, описанный в [12], использует подход к решению задачи параллельной декомпозиции системы частичных булевых функций, предложенный в [13]. Метод, усовершенствованный для случая, когда функция ϕ представляется операцией сложения по модулю 2, приведен в [14]. Методы из [12, 14] минимизируют мощности множеств Z1 и Z2, применяя полный перебор возможных ситуаций в процессе решения, что значительно ограничивает их практическое использование. В [15] описан эвристический метод алгебраической декомпозиции частичных булевых функций, который не гарантирует абсолютного минимума этих мощностей, но позволяет решить задачу за более короткое время.

Вероятность существования какой-либо нетривиальной декомпозиции для полностью определенных булевых функций весьма низка, но по-другому дело обстоит, когда рассматриваемые функции являются не полностью определенными (частичными), особенно когда они заданы только на небольшой части булева пространства аргументов. Поэтому в литературе основное внимание уделялось декомпозиции (в том числе алгебраической) частичных булевых функций. Если функция ϕ относится к классу нелинейных функций, то функции g1 и g2 оказываются проще функции f в том смысле, что степень зависимости их от некоторых переменных может быть меньше, чем у функции f. Данный параметр рассматривался в [16]. Под степенью зависимости функции f от переменной xi здесь понимается число пар значений (х′, х″) вектора х с различными значениями i-й компоненты, для которых f(х′) ≠ f(х″). Кроме того, если какая-то из функций gi, i = 1, 2, оказалась с тем же числом аргументов, что и полностью определенная функция f, то эта функция gi в любом случае будет не полностью определенной функцией, что увеличивает вероятность ее разложимости.

Известны примеры применения методов алгебраической декомпозиции для повышения быстродействия схем [17, 18] и при синтезе схем на базе программируемой вентильной матрицы (FPGA) [19]. Далее предлагается метод синтеза комбинационных схем в базисе двухвходовых элементов, реализующих нелинейные функции. Имеются в виду базисы И-НЕ, ИЛИ-НЕ, а также базис элементов И, ИЛИ при доступных инверсиях переменных. Метод основан на последовательном применении алгебраической декомпозиции к получаемым функциям, в которой используется подход, описанный в [15]. Построение функций ϕ, g1 и g2, представляющих искомую декомпозицию, сводится в данном подходе к поиску в некотором двудольном графе взвешенного покрытия его двудольными полными подграфами (бикликами). Применение в задачах логического проектирования аппарата, связанного с (бикликами), описано в [20].

1. Предлагаемый подход. Предполагается, что система не полностью определенных (частичных) булевых функций f(x), где f и х – векторы (f1, f2, …, fm) и (х1, х2, …, хn), задана двумя матрицами X и Y. Строками матрицы Х служат элементы булева пространства аргументов х1, х2, …, хn, а соответствующими строками матрицы Y – векторы, представляющие наборы значений функций на соответствующих элементах булева пространства. Для каждой функции fi заданной системы можно из матрицы X выделить булевы матрицы М1(fi) и М0(fi), представляющие области булева пространства, где функция fi имеет соответственно значения 1 и 0. Далее эту же символику будем использовать для задания любых других функций.

Рассмотрим полный двудольный граф G(fi) = (V 1, V 0, E) с взвешенными ребрами, где вершины из множества V 1 соответствуют строкам матрицы М1(fi), вершины из множества V 0 – строкам матрицы М0(fi). Каждому ребру v1v0 (v1 ∈ V 1, v0 ∈ V 0) графа G(fi) в качестве веса приписана элементарная дизъюнкция xi ∨ xj ∨ … ∨ xk аргументов заданной системы функций, если компоненты строк матриц М1(fi) и М0(fi), связанных с ребром v1v, в столбцах xi, xj, …, xk имеют различные значения (0 и 1).

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

Пусть требуется выразить некоторую заданную частичную функцию f(x) как f(x) = ϕ(g1(z1), g2(z2)), где ϕ – булева функция от двух переменных g1 и g2, которые являются функциями соответственно от векторных переменных z1 и z2, представляющих собой части вектора х. Символ «=» обозначает как отношение реализации, так и равенство, которое можно рассматривать в качестве частного случая отношения реализации. Функция ϕ, частичная или полностью определенная, реализует частичную функцию f, если значения функции ϕ совпадают со значениями функции f везде, где они определены [21].

Функции g1 и g2 построим следующим образом. В графе G(f) выделим две биклики B1 = = (V11, V10, E1) и B2 = (V21, V20, E2) так, чтобы любое ребро графа G присутствовало хотя бы в одном из множеств E1 или E2, те биклики В1 и В2 должны покрывать своими ребрами все множество Е ребер графа G(f). Биклики В1 и В2 достаточно задать парами множеств (V11, V10) и (V21, V20), так как в биклике каждая вершина из одной доли связана ребрами со всеми вершинами другой доли.

Аргументами функции gi, i = 1, 2, являются переменные, приписанные биклике Bi. Строки матрицы М1(gi), представляющие собой значения векторной переменной zi, где функция gi имеет значение 1, составляют части строк из матрицы М1(f) или из М0(f) (в зависимости от заданного вида функции ϕ), соответствующих вершинам из множества Vi1. Части этих векторов определяются переменными, приписанными биклике Bi, т. е. эти переменные являются компонентами вектора zi. Аналогично формируется матрица М0(gi) из частей векторов, связанных с вершинами из множества Vi0. Таким образом, каждой строке из М1(f) или из М0(f) соответствует пара значений функций g1 и g2. Если эта пара связана со строкой из матрицы М1(f), то она составляет строку матрицы М1(ϕ). Если она соответствует строке из матрицы М0(f), то она составляет строку матрицы М0(ϕ). Так будет задана функция ϕ. Заметим, что пары (V11, V10) и (V21, V20) следует считать упорядоченными, поскольку они связаны со значениями функцийg1 и g2.

Описываемый метод предполагает дальнейшее подобное разложение функций g1 и g2 и последующих получаемых функций до функций от двух переменных из множества Х = {х1, х2, …, хn}.

2. Получение покрытия графа G(f) двумя бикликами. В таблице показано, какие значения должны иметь функции g1 и g2 при определенных значениях функции ϕ и при разных видах этой функции. Из нее видно, что V11 = V21 = V 1 должно быть для операции И, V10 = V20 = V 0 – для операции ИЛИ, V11 = V21 = V 0 – для операции И-НЕ и V10 = V20 = V 1 – для операции ИЛИ-НЕ.

 

Таблица 1. Соотношения значений функций g1, g2 и ϕ

И

ИЛИ

И-НЕ

ИЛИ-НЕ

ϕ g1 g2

1 1 1

0 – 0

0 0 –

ϕ g1 g2

0 0 0

1 – 1

1 1 –

ϕ g1 g2

0 1 1

1 – 0

1 0 –

ϕ g1 g2

1 0 0

0 – 1

0 1 –

 

Таким образом, одна из долей биклики всегда определена видом функции ϕ, как одна из долей полного двудольного графа G, и она присутствует в обеих бикликах. Другие доли биклик В1 и В2 образуются как блоки разбиения другой доли графа G. Например, если V10 = V20 = V 1, то B1 = (V11, V 1) и B2 = (V21, V 1), где V11 ∪ V21 = V 0, и V11 ∩ V21 = ∅.

Исходной информацией для получения искомого покрытия выступает множество звездных графов, которые являются подграфами графа G(f). Звездным графом, или звездой называется полный двудольный граф K1, n [22]. Одноэлементная доля его представляет собой центр звезды. В нашем случае упомянутое множество – это множество всех биклик, у которых одной долей является одноэлементное множество с вершиной v ∈ V 0, а другой – множество V 1 или у которых одна доля – одноэлементное множество с вершиной v ∈ V 1, а другая – множество V 0 двудольного графа G. Назовем их звездными бикликами.

Как было сказано выше, каждой биклике приписывается КНФ, которая преобразуется в ДНФ. Из ДНФ выберем элементарную конъюнкцию K минимального ранга и вместо ДНФ и КНФ припишем соответствующей звездной биклике Bi множество переменных Xi из конъюнкции K. Выберем две звездных биклики Bi и Bj, у которых пересечение Xi ∩ Xj имеет минимальную мощность среди всех пар рассматриваемых звездных биклик. Если таких вариантов несколько, то отдаем предпочтение множествам Xi и Xj максимальной мощности. Естественно, желателен вариант Xi ∩ Xj = ∅. Примем пару (Bi, Bj) за начальное значение пары биклик, которая должна покрывать граф G(f), и обозначим ее (B1, B2). Конъюнкций минимального ранга в ДНФ может быть несколько, и есть возможность выбора варианта, лучшим образом удовлетворяющего указанным условиям.

Дальнейший процесс представляет собой последовательное расширение тех долей биклик B1 и B2, которые в начальных значениях были одноэлементными, за счет вершин, являющихся центрами рассматриваемых звездных биклик. Соответственно меняются множества Х1 и Х2. Пусть, например, B1 = (V11, V10), B2 = (V21, V20) и V11 ∪ V21 = V 0, а множество V ′ состоит из вершин графа G(f), которые не принадлежат ни V 0, ни одному из V10 и V20. Выбираются вершина vk ∈ V ′, являющаяся центром некоторой звездной биклики Bk, и множество Vi0, i ∈ 1, 2, такие, что мощность множества Xi ∪ Xk отличается от мощности множества Xi или Xk на минимальную величину. Множество Vi0 меняется на Vi0 ∪ {vk}, а вершина vk удаляется из V ′. Процесс заканчивается, когда множество V ′ окажется пустым. Пара (B1, B2) представит искомое покрытие.

Далее рассмотрим на примерах построение комбинационных схем в базисах двухвходовых элементов ИЛИ-НЕ и И, ИЛИ.

3. Синтез комбинационных схем в базисе ИЛИ-НЕ. Пусть требуется построить логическую сеть из двухвходовых элементов ИЛИ-НЕ, реализующую систему булевых функций, представленную следующими матрицами (на любом наборе значений аргументов, не совпадающем ни с какой строкой матрицы Х, значения функций не определены):

X=x1x2x3x4x50000111111011111111111000000111101011010000000110112345678910,   Y=f1f2f311100010111111011010001101101112345678910.

Каждую из функций f1, f2 и f3 зададим следующими матрицами с сохранением нумерации строк матриц X и Y:

 

M0f1=x1x2x3x4x5011111110000101000014568,  M0f2=x1x2x3x4x51111110010000115810,

M0f3=x1x2x3x4x5001101111100110000011258.

Двудольные графы G(fi) = (V 1, V 0, E), i = 1, 2, 3, представим матрицами G(fi), подобными матрице смежности. Строки матрицы G(fi) соответствуют вершинам из множества V 1 (строкам матрицы М1(fi)), а столбцы – вершинам из множества V 0 (строкам матрицы М0(fi)). На пересечении строки k и столбца l матрицы G(fi) (в качестве обозначений строк и столбцов и вершин графа используются номера соответствующих строк исходных матриц Х и Y) находится элементарная дизъюнкция или одиночная переменная, приписанные ребру между вершинами k и l:

Gf1=4568x2∨x3x3x4x1∨x5x1∨x3x1∨x3∨x4∨x5x1∨x2∨x3∨x4x1∨x3∨x4x1x4∨x5x3∨x4x3∨x5x1∨x2∨x3x1∨x3x1∨x4x5x3x3∨x4∨x5x1∨x2∨x3∨x4∨x5x1∨x3∨x4∨x5x1∨x5x4x3∨x4∨x5x31237910,

Gf2=5810x1∨x2∨x3∨x4x1∨x3∨x4x1x1∨x4x4x4∨x5x3∨x4x1∨x2∨x3∨x4∨x5x1∨x3∨x4∨x5x1∨x5x1∨x4∨x5x4∨x5x4x3∨x4∨x5x1∨x2∨x4∨x5x1∨x4∨x5x1∨x3∨x5x1∨x3∨x4∨x5x3∨x4∨x5x3∨x4x4∨x51234679,

Gf3=1258x2∨x3∨x4x2∨x3x1∨x2∨x3x1∨x2∨x3∨x5x1∨x2x1∨x2∨x4∨x5x3∨x4x3x1∨x3x1∨x3∨x5x1x1∨x4∨x5x1x1∨x4x4x4∨x5x3∨x4x3∨x5x1∨x5x1∨x4∨x5x4∨x5x4x3∨x4∨x5x33467910.

Получим реализацию функции f1. Биклики B1 = (V11, V10) и B2 = (V21, V20), покрывающие граф G(f1), должны иметь одну общую долю: согласно приведенной выше таблице, для выбранного базиса ИЛИ-НЕ имеем V10 = V20 = V 1. Звездные биклики с приписанными КНФ (в квадратных скобках) имеют следующий вид:

({4}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)]; ({5}, {1,2,3,7,9,10}) [x1 (х3 ∨ х4) (х4 ∨ х5) (х3 ∨ х5)];

({6}, {1,2,3,7,9,10}) [x3 x5 (х1 ∨ х4)]; ({8}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)].

За начальные значения биклик В1 и В2 примем ({4}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)] и ({6}, {1,2,3,7,9,10}) [x3 x5 (х1 ∨ х4)]. Результатом выполнения следующего шага может быть один из следующих вариантов:

({4,5}, {1,2,3,7,9,10}) [x1 x3 x4]; ({4,8}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)];

({5,6}, {1,2,3,7,9,10}) [x1 x3 x5]; ({6,8}, {1,2,3,7,9,10}) [x3 x4 х5].

Во всех вариантах, кроме одного, приписанные КНФ совпадают с ДНФ. Следует выбрать вариант ({4,8}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)], поскольку приписанная этой биклике ДНФ состоит из двух элементарных конъюнкций одного ранга 3 и имеется в дальнейшем больше возможностей оптимизировать решение. Таким образом, текущим значением пары биклик (В1, В2) является

({4,8}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)], ({6}, {1,2,3,7,9,10}) [x3 x5 (х1 ∨ х4)].

Выбор варианта на следующем шаге привел к следующему взвешенному покрытию графа G(f1):

В1 = ({4,8}, {1,2,3,7,9,10}) [x3 x4 (х1 ∨ х5)], В2 = ({5,6}, {1,2,3,7,9,10}) [х1 x3 x5].

Таким образом, функция f1 разлагается на две функции g1 и g2, связанные операцией ИЛИ-НЕ, или «стрелка Пирса»: f1 = g1 ↑ g2. Функция g2, соответствующая биклике В2, зависит от переменных х1, x3, x5 и ее можно задать матрицами, которые получаются из матриц M1(f1) и M0(f1) и после удаления строки 6, совпадающей со строкой 5, имеют следующий вид:

M1g2=x1x3x51005,  M0g2 =x1x3x5001111001100101137910 .

Аргументами функции g1 могут быть х1, x3, x4 или x3, x4, x5, и ее могут задавать матрицы

M1g1=x1x3x401001048,  M0g1 =x1x3x4001111001110110137910

или

M1g1 =x3x4x500100148,  M0g1 =x3x4x510011010001113710.

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

Функциям g1 и g2 соответствуют графы, которые задаются следующими матрицами:

Gg1=13710x3x3∨x4∨x5x4x5x5x4x3∨x4∨x5x348.  Gg2=1379x1∨x3x1x5x35.

Граф G(g1) покрывают биклики ({1,10}, {4,8}) [х3] и ({3,7}, {4,8}) [х4 x5], а граф G(g2) – ({1,3,9}, {5}) [х1 х3] и (7), (5) [х5]. Эти биклики определяют разложения g1 = х3 ↑ g3(х4, х5) и g2 = =∑g4(х1, х3) ↑ х5, где функции g3 = (х4 ↑∑х5) ↑ (∑х4 ↑ х5) и g4 =∑х1 ↑ х3 представлены матрицами, получаемыми из матриц M1(g1) и M0(g1):

M1g3=x4x5010137, M0g3=x4x5100148  и  M1g4 =x1x3001101139,  M0g4=x1x3105.

Функция f1 реализована сетью, представляемой следующей системой уравнений:

f1 = g1 ↑ g2,

g1 = х3 ↑ g3, g2 =∑g4 ↑ х5,

g3 = g5 ↑ g6, g4 =∑x1 ↑ x3,

g5 = x4 ↑∑x5, g6 =∑x4 ↑ x5.

В графе G(f2) имеются звездные биклики ({5}, {1,2,3,4,6,7,9}) [x1 x4], ({8}, {1,2,3,4,6,7,9}) [x4 (x1 ∨ x5)] и ({10}, {1,2,3,4,6,7,9}) [(x1 ∨ x3 ∨ x5) (x3 ∨ x4) (x4 ∨ x5)]. Отсюда видно, что функция f2 может быть реализована функцией от двух переменных – x1 и x4, которая задается матрицами

M1f2 =x1x4105 и  M0f2 =x1x4001101136,

т. е. f2 =∑x1 ↑ x4.

Граф G(f3) содержит следующие звездные биклики:

({1}, {3,4,6,7,9,10}) [(x1 ∨ x2) (x2 ∨ x3)], ({2}, {3,4,6,7,9,10}) [x1 x3],

({5}, {3,4,6,7,9,10}) [x1 x4 (x3 ∨ x5)], ({8}, {3,4,6,7,9,10}) [x3 x4 (x1 ∨ x5)].

По ним получим покрытие с бикликами ({1}, {3,4,6,7,9,10}) [(x1 ∨ x2) (x2 ∨ x3)] и ({2,5,8}, {3,4,6,7,9,10}) [x1 x3 x4], которые определяют разложение f3 =∑x2 ↑ g7(x1, x3, x4), где функция g7 задается матрицами

M1g7=x1x3x401101025,  M0g7=x1x3x4001110001101110346910.

Граф G(g7) представляется следующей матрицей:

Gg7=346910x3∨x4x1x3x1∨x4x1∨x3x4x1x3∨x4x1∨x4x325.

Искомое покрытие графа G(g7) составляют биклики ({3,6,9}, {2,5}) [x1 x4] и ({4,10}, {2,5}) [x3 (x1 ∨ x4)], и функция g7 определяется как g7 = g8(x1, x4) ↑ g9(x1, x3), где функции g8 и g9 задаются следующими матрицами:

M1g8 =x1x4010136. M0g8=x1x4011025 и M1g9 =x1x30101410, M0g9=x1x3011025. 

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

f1 = g1 ↑ g2, f2 = g11, f3 =∑x2 ↑ g7,

g1 = x3 ↑ g3, g2 = x5 ↑∑g4, g7 = g8 ↑ g9,

g3 = g5 ↑ g6, g8 = g10 ↑ g11, g9 = g12 ↑ g4,

g4 =∑x1 ↑ x3, g5 = x4 ↑∑x5, g6 =∑x4 ↑ x5, g10 = x1 ↑∑x4, g11 =∑x1 ↑ x4, g12 = x1 ↑∑x3.

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

 

Рис. 1. Схема из элементов ИЛИ-НЕ

 

4. Синтез комбинационных схем в базисе И, ИЛИ. Пусть теперь требуется построить логическую сеть из элементов И и ИЛИ с доступными инверсиями входных сигналов, реализующую систему булевых функций из рассмотренного примера. Согласно приведенной выше таблице в бикликах B1 = (V11, V10) и B2 = (V21, V20), покрывающих граф G(fi), имеем V11 = V21 = V 1 для операции И и V10 = V20 = V 0 для операции ИЛИ. Для очередного разложения h = ϕ(gk, gl), где h – любая из функций, исходная или получаемая в процессе разложения, следует выбрать элемент И или ИЛИ, соответствующий функции ϕ. Предлагается взять тот элемент, который дает меньшую степень определенности функций gk и gl. Если функции gk и gl оказываются полностью определёнными, то по матрице G(h) можно заметить, что для лучшего варианта разложения h = ϕ(gk, gl) желательно выбрать для функции ϕ операцию И, если матрица М0(h) имеет больше строк, чем матрица М1(h), и, наоборот, операцию ИЛИ, если М1(h) имеет строк больше, чем М0(h). Кроме того, разложение считается лучшим, если при прочих равных условиях получаемые функции имеют меньшее суммарное число аргументов.

Для функции f1 и операции ИЛИ имеем следующие звёздные биклики, полученные по матрице G(f1):

({1}, {4,5,6,8}) [х2 ∨ х3], ({2}, {4,5,6,8}) [x3], ({3}, {4,5,6,8}) [x1 x4],

({7}, {4,5,6,8}) [x4 x5], ({9}, {4,5,6,8}) [x3], ({10}, {4,5,6,8}) [x3].

Описанным выше способом получаем В1 = ({1,2,9,10}, {4,5,6,8},) [x3] и В2 = ({3,7}, {4,5,6,8},) [x1 x4 x5], что определяет разложение f1 = x3 ∨ g1(x1, x4, x5).

Если взять операцию И для разложения функции f1, то звездные биклики будут иметь следующий вид:

({1,2,3,7,9,10}, {4}) [x3 x4 (x1 ∨ x5)], ({1,2,3,7,9,10}, {5}) [x1 (x3 ∨ x4) (x3 ∨ x5) (x4 ∨ x5)],

({1,2,3,7,9,10}, {6}) [x3 x5 (x1 ∨ x4)], ({1,2,3,7,9,10}, {8}) [x3 x4 (x1 ∨ x5)].

В этом случае граф G(f1) покрывают биклики ({1,2,3,7,9,10}, {4,8}) [x3 x4 (x1 ∨ x5)] и ({1,2,3,7,9,10}, {5,6}) [x1 x3 x5]. Выбираем элемент ИЛИ, так как в разложении f1 = g1 g2 обе функции g1 и g2 зависят от трех переменных, тогда как в случае элемента ИЛИ числа аргументов получаемых функций – 1 и 3. Таким образом, имеем разложение f1 = x3 ∨ g1(x1, x4, x5), где функция g1 задается матрицами

M1g1=x1x4x501010137 и  M0g1=x1x4x50111101000014568.

Граф G(g1) представляется матрицей

Gg1=4568x4x1∨x5x1x4∨x5x1∨x4x5x1∨x5x437.

По числу аргументов функций разложения следует выбрать операцию ИЛИ. Непосред-ственно по матрице G(g1) находится покрытие, которое составляют биклики ({3}, {4,5,6,8}) [x1 x4] и ({7}, {4,5,6,8}) [x4 x5], определяющие разложение g1 = g2(x1, x4) ∨ g3(x4, x5). Матрица М1(g2) является минором матрицы М1(g1), образованным строкой 3 и столбцами x1 и x4, а матрица матриц М0(g2) – минором матрицы М0(g2), образованным строками 4 – 6, 8 и столбцами x1 и x4. По этим матрицам функция g2 находится как g2 =∑x1∑x4. Аналогично определяется функция g3 по минорам тех же матриц: g3 = x4 x5. Таким образом, получено полное разложение функции f1 на функции не более чем от двух аргументов.

Звездными бикликами графа G(f2) при операции ИЛИ являются:

({1}, {5,8,10}) [(x1 ∨ x2 ∨ x3 ∨ x4) (x1 ∨ x2 ∨ x4 ∨ x5)],

({2}, {5,8,10}) [(x1 ∨ x3 ∨ x4) (x1 ∨ x4 ∨ x5)],

({3}, {5,8,10}) [x1],

({4}, {5,8,10}) [x1 ∨ x4],

({6}, {5,8,10}) [x4],

({7}, {5,8,10}) [x4],

({9}, {5,8,10}) [(x3 ∨ x4) (x4 ∨ x5)].

Из них легко получается покрытие графа G(f2) бикликами ({1,2,3,4}, {5,8,10}) [x1] и ({6,7,9}, {5,8,10}) [x4], которое определяет реализацию функции f2: f2 =∑x1 ∨ x4.

По степени определенности функций g4 и g5, на которые разлагается функция f3, выбираем операцию И, для которой покрытие графа G(f3) составят биклики ({3,4,6,7,9,10}), {1,2}) [x1 x3] и ({3,4,6,7,9,10}, {5,8}) [x1 x3 x4], определяющие разложение f3 = g4(x1, x3) g5(x1 x3 x4). Матрицы, получаемые из матриц М1(f3) и М0(f3) и задающие функции g4 и g5, имеют следующий вид:

M1g4=x1x3011001369.   M0g4=x1x3011,  M1g5=x1x3x4001110001101110346910,  M0g5=x1x3x41005.  

Функция g4 представляется как g4 = x1 ∨∑x3. Для функции g5, как сказано выше, следует выбрать дизъюнктивное разложение, поскольку матрица М1(g5) имеет больше строк, чем матрица М0(g5). Граф G(g5), представляемый матрицей

Gg5=5x1x1∨x4x4x3∨x4x3346910,

покрывается бикликами ({3,4}, {5}) [x1] и ({6,9,10}, {5}) [x3 x4], определяющими разложение g5 =∑x1 ∨ g6(x3, x4), где g6(x3, x4) = x3 ∨ x4.

Таким образом, получено полное разложение функций заданной системы на функции, представляемые операциями И и ИЛИ, и вся заданная система не полностью определенных булевых функций реализуется структурой, описываемой следующей системой уравнений:

f1 = x3 ∨ g1, f2 = ∑x1∨ x4, f3 = g4 g5,

g1 = g2 ∨ g3, g4 = x1 ∨∑x3, g5 =∑x1 ∨ g6,

g2 =∑x1∑x4, g3 = x4 х5, g6 = x3 ∨ x4.

Соответствующая комбинационная схема из элементов И и ИЛИ показана на рис. 2.

x1∑x1 x3∑x3 x4∑x4 x5

 

Рис. 2. Схема из элементов И и ИЛИ

 

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

×

About the authors

Yu. V. Pottosin

United Institute of Informatics Problems, National Academy of Sciences of Belarus

Author for correspondence.
Email: pott@newman.bas-net.by
Belarus, Minsk

References

  1. Perkowski M.A., Grygiel S. A Survey of Literature on Functional Decomposition, Version IV (Technical Report). Portland, USA: Portland State University, Department of Electrical En-gineering, 1995.
  2. Zakrevskij A.D. On a Special Kind Decomposition of Weakly Specified Boolean Functions // Second Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’97). Minsk, Belarus: National Academy of Sciences of Belarus, Institute of Engineering Cybernetics, 1997. V. 1. P. 36–41.
  3. Fišer P., Schmidt J. Small but Nasty Logic Synthesis Examples // Proc. 8th Intern. Workshop on Boolean Problems (IWSBP’8), Freiberg, Germany, 2008. P. 183–190.
  4. Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравне-ний. Минск: Беларус. навука, 2009.
  5. Choudhury M., Mohanram K. Bi-decomposition of Large Boolean Functions Using Blocking Edge Graphs // 2010 IEEE/ACM Intern. Conf. on Computer-Aided Design (ICCAD’2010). San Jose: IEEE Press, 2010. Р. 586–591.
  6. Cheng D., Xu X. Bi-decomposition of Logical Mappings via Semi-Tensor Product of Matri-ces // Automatica. 2013. V. 49. N 7. Р. 1979–1985.
  7. Steinbach B., Posthoff C. Vectorial Bi-decomposition for Lattices of Boolean Functions // Further Improvements in the Boolean Domain / Cambridge. Cambridge Scholars Publishing, 2018. Р. 175–198.
  8. Jóžwiak L., Chojnacki A. An Effective and Efficient Method for Functional Decomposition of Boolean Functions Based on Information Relationship Measures // Design and Diagnos-tics of Electronic Circuits and Systams: Proc. of 3rd DDECS Workshop, Smolenice Castle, Slovakia, Bratislava: Institute of Informatics, Slovak Academy of Sciences, 2000. Р. 242–249.
  9. Закревский А.Д. Декомпозиция частичных булевых функций – проверка на раздели-мость по заданному разбиению // Информатика. 2007. № 1 (13). С. 16–21.
  10. Поттосин Ю.В., Шестаков Е.А. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций // Вестн. Томск. гос. ун-та. Управление, вычислительная техника и информатика. 2011. № 3(16). С. 100–107.
  11. Taghavi Afshord S., Pottosin Yu.V., Arasteh B. An Input Variable Partitioning Algorithm for Functional Decomposition of a System of Boolean Functions Based on the Tabular Method // Discrete Applied Mathematics. 2015. V. 185. P. 208–219.
  12. Поттосин Ю.В. Метод бидекомпозиции частичных булевых функций // Информа-тика. 2019. Т. 16, № 4. С. 77–87.
  13. Поттосин Ю.В., Шестаков Е.А. Декомпозиция системы частичных булевых функ-ций с помощью покрытия графа полными двудольными подграфами // Новые инфор-мационные технологии в исследовании дискретных структур. Докл. второй Всерос-сийск. конф. Екатеринбург: УрО РАН, 1998. С. 185–189.
  14. Pottosin Yu.V. A Method for Bi-decomposition of Partial Boolean Functions // Приклад-ная дискретная математика. 2020. № 47. С. 108–116.
  15. Поттосин Ю.В. Эвристический метод алгебраической декомпозиции частичных булевых функций // Информатика. 2020. Т. 17, № 3. С. 44–53.
  16. Поттосин Ю.В., Шестаков Е.А. Параллельно-последовательная декомпозиция си-стемы частичных булевых функций // Прикладная дискретная математика. 2010. № 4(10). С. 55-63.
  17. Cortadella J. Timing-driven Logic Bi-decomposition // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 2003. V. 22. N 6. Р. 675–685.
  18. Mishchenko A., Steinbach B., Perkowski M. An Algorithm for Bi-decomposition of Logic Functions // Proc. 38th Annual Design Automation Conf. (DAC’2001), Las Vegas, USA, 2001. Р. 103–108.
  19. Chang S.C., Marek-Sadowska M., Hwang T. Technology Mapping for TLU FPGA’s Based on Decomposition of Binary Decision Diagrams // IEEE Trans. Computer-Aided De-sign. 1996. V. 15. N 10. Р. 1226–1235.
  20. Поттосин Ю.В. Комбинаторные задачи в логическом проектировании дискретных устройств. Минск: Беларус. навука, 2021.
  21. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проекти-рования дискретных устройств. М.: Физматлит, 2007.
  22. Евстигнеев В.А., Касьянов В.Н. Толковый словарь по теории графов в информатике и программировании. Новосибирск: Наука. СО РАН, 1999.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Formula

Download (62KB)
Indexing metadata
3. Fig. 1. Circuit of OR-NOT elements

Download (118KB)
Indexing metadata
4. Fig. 2. Circuit of AND and OR elements

Download (134KB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

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

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».