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. Ciriani
Penultimo
;
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.
Settore INF/01 - Informatica
2021
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/908868
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact