An Approximation Algorithm for Fully Testable kEP-SOP Networks

Multi-level logic synthesis yields much more compact expressions of a given Boolean function with respect to standard two-level sum of products (SOP) forms. On the other hand, minimizing an expression with more than two-levels can take a large time.
In this paper we introduce a novel algebraic four-level expression, named k-EXOR-projected sum of products (kEP-SOP) form,
whose synthesis can be performed in polynomial time with an approximation algorithm starting from a minimal SOP.
Our experiments show that the resulting networks can be obtained in very short computational time and often exhibit a high quality.
We also study the testability of these networks under the Stuck-at-fault model, and show how fully testable circuits can be generated from them by adding at most a constant number of multiplexer gates. Experimental results show the effectiveness of this method both for four-level logic and general multi-level logic synthesis.