Shared Multi-Terminal Binary Decision Diagrams for Multiple-Output Functions (Special Section on VLSI Design and CAD Algorithms)

概要

論文の詳細を見る
This paper describes a method to represent m output functions using shared multi-terminal binary decision diagrams (SMTBDDs). The SMTBDD (k) consists of multi-terminal binary decision diagrams (MTBDDs), where each MTBDD represents k output functions. An SMTBDD (k) is the generalization of shared binary decision diagrams (SBDDs) and MTBDDs : for k= 1. it is an SBDD, and for k=m, it is an MTBDD. The size of a BDD is the total number of nodes. The features of SMTBDD (k) s are : 1) they are often smaller than SBDDs or MTBDDs ; and 2) they evaluate k outputs simultaneously. We also propose an algorithm for grouping output functions to reduce the size of SMTBDD (k) s. Experimental results show the compactness of SMTBDD (k) s. An SMTBDD_<min> denotes the smaller SMTBDD which is either an SMTBDD (2) or an SMTBDD (3) with fewer nodes. The average relative sizes for SBDDs. MTBDDs, and SMTBDDs are 1.00, 152.73, and 0.80, respectively.
社団法人電子情報通信学会の論文
1998-12-25