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 | 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: | 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
SCOPUSTM
Citations
31
checked on Sep 15, 2024
Page view(s)
5
checked on Sep 16, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.