We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NPNP-hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis.

The optimization of kEP-SOPs : computational complexity, approximability and experiments / A. Bernasconi, V. Ciriani, R. Cordone. - In: ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS. - ISSN 1084-4309. - 13:2(2008). [10.1145/1344418.1344431]

The optimization of kEP-SOPs : computational complexity, approximability and experiments

V. Ciriani
Secondo
;
R. Cordone
Ultimo
2008

Abstract

We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NPNP-hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis.
Automatic synthesis ; Approximation algorithm ; Multilevel logic synthesis ; Optimization ; Testing
Settore INF/01 - Informatica
Article (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/37726
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact