Authors: Karpovsky, Mark
Stanković, Radomir 
Astola, Jaakko
Title: Reduction of sizes of decision diagrams by autocorrelation functions
Journal: IEEE Transactions on Computers
Volume: 52
Issue: 5
First page: 592
Last page: 606
Issue Date: 1-Jan-2003
Rank: M21
ISSN: 0018-9340
DOI: 10.1109/TC.2003.1197126
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: Autocorrelation functions | Decision diagrams | Linear transforms | Logic synthesis | Spectral techniques
Publisher: IEEE
Project: BSF, Grant 1998154
Academy of Finland, Finnish Center of Excellence Programme, Grant. No. 44876
EXSITE, Project No. 51520

Show full item record


checked on Jul 14, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.