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. Ciriani
Secondo
;
R. Cordone
Ultimo
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.
Logic optimization; Testing; Multilevel networks
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/37691
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact