The testability-preserving concurrent decomposition and factorization of Boolean expressions

The authors present a concurrent method for the decomposition and factorization of Boolean expressions. The method uses only two-literal single-cube divisors and double-cube divisors considered concurrently with their complements. The authors demonstrate that these objects, despite their simplicity, provide a very good framework on which to reason about common algebraic divisors and the duality relations between expressions. The simplicity of these objects makes it possible to compute the cost function associated with them accurately and dynamically. Hence, the method is entirely greedy, and in each iteration it extracts the best expression along with its complement. The decomposition is based on testability-preserving transformations, and the synthesized multilevel network is fully tested by a complete test derived for the original circuit. The algorithm has been implemented and excellent results on several benchmark circuits illustrate its efficiency and effectiveness