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

Volume

52

Issue

5

fYear

2003

fDate

5/1/2003 12:00:00 AM

Firstpage

592

Lastpage

606

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;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2003.1197126

Filename

1197126