Heuristics to Minimize Multiple-Valued Decision Diagrams

Hafiz Md. HASAN BABU; Tsutomu SASAO

Heuristics to Minimize Multiple-Valued Decision Diagrams

Hafiz Md. HASAN BABU, Tsutomu SASAO

Full Text Views

0

Cite this

Summary :

In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.12 pp.2498-2504

Publication Date: 2000/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category: Logic Synthesis

Cite this

Copy

Hafiz Md. HASAN BABU, Tsutomu SASAO, "Heuristics to Minimize Multiple-Valued Decision Diagrams" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 12, pp. 2498-2504, December 2000, doi: .
Abstract: In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_12_2498/_p

Copy

@ARTICLE{e83-a_12_2498,
author={Hafiz Md. HASAN BABU, Tsutomu SASAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Heuristics to Minimize Multiple-Valued Decision Diagrams},
year={2000},
volume={E83-A},
number={12},
pages={2498-2504},
abstract={In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Heuristics to Minimize Multiple-Valued Decision Diagrams
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2498
EP - 2504
AU - Hafiz Md. HASAN BABU
AU - Tsutomu SASAO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2000
AB - In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.
ER -