Heuristics to minimize multiple-valued decision diagrams

作     者：Babu, HMH Sasao, T 

作者机构：Kyushu Inst Technol Dept Comp Sci & Elect Iizuka Fukuoka 8208502 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：2000年第E83A卷第12期

页      面：2498-2504页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：binary decision diagram (BDD) multiple-valued decision diagram (MDD) multiple-output function multiple-walled logic FPGA design 

摘      要：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.