In this paper we introduce a new algebraic form for Boolean function representation, called EXOR-Projected Sum of Products (EP-SOP), resulting in a four level network that can be easily implemented in practice. We prove that deriving an optimal EP-SOP from an optimal Sum of Products (SOP) form is a hard problem (NPNP-hard); nevertheless we propose a very efficient approximation algorithm, which returns in polynomial time an EP-SOP form whose cost is guaranteed to be near the optimum. Experimental evidence shows that for about 35% of the classical synthesis benchmarks the EP-SOP networks have a smaller area and delay with respect to the optimal SOPs (sometimes gaining even 40-50% of the area). Since the computational times required are extremely short, we recommend the use of the proposed approach as a post-processing step after SOP minimization.

EXOR Projected Sum of Products

BERNASCONI, ANNA;
2006-01-01

Abstract

In this paper we introduce a new algebraic form for Boolean function representation, called EXOR-Projected Sum of Products (EP-SOP), resulting in a four level network that can be easily implemented in practice. We prove that deriving an optimal EP-SOP from an optimal Sum of Products (SOP) form is a hard problem (NPNP-hard); nevertheless we propose a very efficient approximation algorithm, which returns in polynomial time an EP-SOP form whose cost is guaranteed to be near the optimum. Experimental evidence shows that for about 35% of the classical synthesis benchmarks the EP-SOP networks have a smaller area and delay with respect to the optimal SOPs (sometimes gaining even 40-50% of the area). Since the computational times required are extremely short, we recommend the use of the proposed approach as a post-processing step after SOP minimization.
2006
3901882197
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11568/106747
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact