Comparison of Decision Diagrams for Multiple-Output Logic Functions.
Tsutomu Sasao, Yukihiro Iguchi, Munehiro Matsuura · 2002
This paper shows four different methods to evaluate multiple-output logic functions using decision diagrams: SBDD, MTBDD, BDD for characteristic functions (CF), and BDDs for ECFNs (Encoded Characteristic Function for Non-zero outputs). Methods to compute average evaluation time for each type of decision diagrams are presented. By experimental analysis using benchmark functions, the number of nodes and average evaluation time are compared. Evaluation using BDDs for ECFN outperforms those using MTBDDs, BDDs for CF, and SBDDs with respect to the size of BDDs and computation time. The sizes of BDDs for ECFNs are smaller than ones of corresponding MTBDDs (Multi-Terminal BDDs), BDDs for CFs (Characteristic Functions), and SBDDs (Shared BDDs).