We define a new algebraic form for Boolean function representation, called EXOR-Projected Sum of Products(EP-SOP), consisting in a four level network that can be easily implemented in practice. Deriving an optimal EP-SOP from an optimal SOP form is a NPNP-hard problem; 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, 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.

Logic synthesis of EXOR projected sum of products / A. Bernasconi, V. Ciriani, R. Cordone - In: VLSI-SoC: research trends in VLSI and systems on chip : 16th International conference on very large scale integration of system on chip (VLSI-SoC 2008) : Rhodes Island, Greece October 13-15, 2008 / [a cura di] G. De Micheli, S. Mir, R. Reis. - New York : Springer, 2008. - ISBN 9780387749082. - pp. 241-257 (( Intervento presentato al 16. convegno International conference on very large scale integration of system on chip (VLSI-SoC 2008) : Rhodes Island, Greece, October 13-15, 2008 tenutosi a Rhodes Island, Greece nel 2008 [10.1007/978-0-387-74909-9_14].

Logic synthesis of EXOR projected sum of products

V. Ciriani
Secondo
;
R. Cordone
Ultimo
2008

Abstract

We define a new algebraic form for Boolean function representation, called EXOR-Projected Sum of Products(EP-SOP), consisting in a four level network that can be easily implemented in practice. Deriving an optimal EP-SOP from an optimal SOP form is a NPNP-hard problem; 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, 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.
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/37669
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact