Поттосин Ю. В. - кандидат физико-математических наук, ведущий научный сотрудник.
Ул. Сурганова, 6, 220012, Минск
Yuri V. Pottosin - Cand. Sci. (Phys.-Math.), Leading Researcher.
6, Surganova Str., 220012, Minsk
Описывается эвристический метод многоблочной параллельной декомпозиции системы частичных булевых функций, минимизирующий число функций, которые составляют искомую суперпозицию. При этом накладывается ограничение на число аргументов получаемых функций. Метод предполагает задание функций в интервальной форме, т. е. в виде пары троичных матриц. Одна из матриц представляет интервалы булева пространства аргументов (матрица интервалов), другая матрица - значения функций на этих интервалах (матрица функций). Рассматриваются графы ортогональности строк указанных матриц, и задача декомпозиции функций сводится к задаче о кратчайшем покрытии множества ребер графа ортогональности строк матрицы функций полными двудольными подграфами (бикликами) графа ортогональности строк матрицы интервалов. Каждой биклике приписывается определенным образом дизъюнктивная нормальная форма (ДНФ), и рассматриваются только те биклики, у которых соответствующие ДНФ имеют элементарные конъюнкции ранга, не превышающего границы числа аргументов получаемых функций. Биклики, составляющие искомое покрытие, и само покрытие формируются последовательно по определенным правилам. По каждой из этих биклик строится функция, аргументами которой являются переменные из элементарной конъюнкции минимального ранга соответствующей ДНФ. Получаемые функции представляются также в интервальной форме.
A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions is described. The method minimizes the number of functions forming the required superposition. The restriction on the number of arguments of the obtained functions is imposed. The method involves the specification of functions by interval form i. e. in the form of a pair of ternary matrices. One of the matrices represents intervals of Boolean space of the arguments (matrix of intervals), the other one represents the values of the functions at these intervals (matrix of functions). The graphs of rows orthogonality of those matrices are considered. The problem of functions decomposition is reduced to covering the edge set of the rows orthogonality graph of the matrix of functions by complete bipartite subgraphs (bicliques) of the row orthogonality graph of the matrix of intervals. Every biclique is assigned with a disjunctive normal form (DNF) by a certain way, and only those bicliques are taken into consideration whose DNFs have terms with the ranks not more than the bounds of the number of arguments of the obtained functions. The bicliques that form the desired cover and the cover itself are constructed sequentially by certain rules. Every biclique is used to construct the function whose arguments are the variables from the term of minimum rank from the corresponding DNF. The obtained functions are given also in interval form.
The authors declare that there are no conflicts of interest present.