MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION

Abstract

A locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduced ordered Binary Decision Diagram. The results of experimental comparison of the program implementing the proposed algorithm and the program implementing the algorithm for enumeration of random permutations are given. The results show the advantage of the proposed algorithm when it is used for synthesis of logical circuits on the basis of library elements.