We propose a new heuristic algorithm for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function f, based on a new algebraic criterion for product selection. The basic idea behind the new algorithm is to transform a given irredundant Sum-of-Products (SOP), i.e., a set of products covering the on-set minterms of f, into a disjoint SOP by repeated applications of two transformations. The first transformation selects pairs of suitable overlapping products in the initial SOP and replaces them with pairs of non-overlapping products covering the same minterms. By this step, some products are made disjoint, while keeping the overall number of products in the SOP unchanged. Next, a second transformation returns a completely disjoint SOP. By this second step, the number of products will increase. A set of experiments on a standard collection of combinational benchmarks shows that this new method is efficient and produces better results compared to the current best heuristic, achieving a 34.4% average cost reduction in about the 46% of the benchmarks, with less computation time.
A Boolean Heuristic for Disjoint SOP Synthesis / P. Balasubramanian, A. Bernasconi, V. Ciriani, T. Villa - In: 2021 24th Euromicro Conference on Digital System Design (DSD)[s.l] : IEEE, 2021. - ISBN 978-1-6654-2703-6. - pp. 62-68 (( Intervento presentato al 24. convegno Euromicro Conference on Digital System Design, DSD tenutosi a Palermo nel 2021 [10.1109/DSD53832.2021.00019].
A Boolean Heuristic for Disjoint SOP Synthesis
V. CirianiPenultimo
;
2021
Abstract
We propose a new heuristic algorithm for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function f, based on a new algebraic criterion for product selection. The basic idea behind the new algorithm is to transform a given irredundant Sum-of-Products (SOP), i.e., a set of products covering the on-set minterms of f, into a disjoint SOP by repeated applications of two transformations. The first transformation selects pairs of suitable overlapping products in the initial SOP and replaces them with pairs of non-overlapping products covering the same minterms. By this step, some products are made disjoint, while keeping the overall number of products in the SOP unchanged. Next, a second transformation returns a completely disjoint SOP. By this second step, the number of products will increase. A set of experiments on a standard collection of combinational benchmarks shows that this new method is efficient and produces better results compared to the current best heuristic, achieving a 34.4% average cost reduction in about the 46% of the benchmarks, with less computation time.File | Dimensione | Formato | |
---|---|---|---|
main.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
188.99 kB
Formato
Adobe PDF
|
188.99 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
A_Boolean_Heuristic_for_Disjoint_SOP_Synthesis.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
2.04 MB
Formato
Adobe PDF
|
2.04 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.