Title :
Reduction of sizes of decision diagrams by autocorrelation functions
Author :
Karpovsky, Mark G. ; Stankovic, Radomir S. ; Astola, Jaakko T.
Author_Institution :
Dept. of Electr. & Comput. Eng., Boston Univ., MA, USA
fDate :
5/1/2003 12:00:00 AM
Abstract :
This paper discusses optimization of decisions diagrams (DDs) by total autocorrelation functions. We present an efficient algorithm for construction of linearly transformed binary decision diagrams (LT-BDDs) and Linearly transformed multiterminal BDDs (LT-MTBDDs) for systems of Boolean functions, based on linearization of these functions by the corresponding autocorrelation functions. Then, we present a method for reduction of sizes of DDs by a level-by-level reduction of the width of DDs using the total autocorrelation functions. The approach provides for a simple procedure for minimization of LT-BDDs and LT-MTBDDs and upper bounds on their sizes. Experimental results for benchmarks illustrate that the proposed method on average is very efficient.
Keywords :
Boolean functions; binary decision diagrams; Boolean functions; autocorrelation functions; benchmarks; decisions diagram size reduction; level-by-level width reduction; linearization; linearly transformed binary decision diagrams; linearly transformed multiterminal binary decision diagrams; minimization; optimization; upper bounds; Autocorrelation; Boolean functions; Data structures; Decision trees; Discrete transforms; Galois fields; Logic functions; Mathematical model; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2003.1197126