Search

This paper introduces the theory of bi-decomposition of Boolean functions. This approach optimally exploits functional properties of a Boolean function in order to find an associated multilevel circuit representation having a very short delay by using simple two input gates. The machine learning process is based on the Boolean Differential Calculus and is focused on the aim of detecting the profitable functional properties available for the Boolean function. For clear understanding the bi-decomposition of completely specified Boolean functions is introduced first. Significantly better chance of success are given for bi-decomposition of incompletely specified Boolean functions, discussed secondly. The inclusion of the weak bi-decomposition allows to prove the the completeness of the suggested decomposition method. The basic task for machine learning consists of determining the decomposition type and dedicated sets of variables. Lean on this knowledge a complete recursive design algorithm is suggested. Experimental results over MCNC benchmarks show that the bi-decomposition outperforms SIS and other BDD-based decomposition methods in terms of area and delay of the resulting circuits with comparable CPU time. By switching from the ON-set/OFF-set model of Boolean function lattices to their upper- and lower-bound model a new view to the bi-decomposition arises. This new form of the bi-decomposition theory makes a comprehensible generalization of the bi-decomposition to multivalued function possible. [ABSTRACT FROM AUTHOR]

This article presents a theory for the bi-decomposition of functions in multi-valued logic (MVL). MVL functions are applied in logic design of multi-valued circuits and machine learning applications. Bi-decomposition is a method to decompose a function into two decomposition functions that are connected by a two-input operator called gate. Each of the decomposition functions depends on fewer variables than the original function. Recursive bi-decomposition represents a function as a structure of interconnected gates. For logic synthesis, the type of the gate can be chosen so that it has an efficient hardware representation. For machine learning, gates are selected to represent simple and understandable classification rules.Algorithms are presented for non-disjoint bi-decomposition, where the decomposition functions may share variables with each other. Bi-decomposition is discussed for the min- and max-operators. To describe the MVL bi-decomposition theory, the notion of incompletely specified functions is generalized to function intervals. The application of MVL differential calculus leads to particular efficient algorithms. To ensure complete recursive decomposition, separation is introduced as a new concept to simplify non-decomposable functions. Multi-decomposition is presented as an example of separation.The decomposition algorithms are implemented in a decomposition system called YADE. MVL test functions from logic synthesis and machine learning applications are decomposed. The results are compared to other decomposers. It is verified that YADE finds decompositions of superior quality by bi-decomposition of MVL function sets. [ABSTRACT FROM AUTHOR]