CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn 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.
| Titolo: | EXOR Projected Sum of Products |
| Autori interni: | |
| Anno del prodotto: | 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. |
| Handle: | http://hdl.handle.net/11568/106747 |
| ISBN: | 3901882197 |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11568/106747
Copyright © 2020