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.
An approximation algorithm for fully testable kEP-SOP networks / A. Bernasconi, V. Ciriani, R. Cordone - In: GLSVLSI '07 : ProceedingsNew York : ACM, 2007. - ISBN 9781595936059. - pp. 417-422 (( Intervento presentato al 17. convegno Great Lakes Symposium on VLSI tenutosi a Stresa nel 2007.
An approximation algorithm for fully testable kEP-SOP networks
V. CirianiSecondo
;R. CordoneUltimo
2007
Abstract
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.