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 / A. Bernasconi, V. Ciriani, R. Cordone - In: Very Large Scale Integration, 2006 IFIP International Conference on / [a cura di] G. De, R. Reis, E. Simeu. - Piscataway : IEEE, 2006. - ISBN 3901882197. - pp. 284-289 (( Intervento presentato al 14. convegno International Conference on Very Large Scale Integration and System-on-Chip tenutosi a Nice nel 2006.
EXOR projected sum of products
V. CirianiSecondo
;R. CordoneUltimo
2006
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.