Authors: | Keren, Osnat Levin, Ilya Stanković, Radomir |
Title: | Determining the number of paths in decision diagrams by using autocorrelation coefficients | Journal: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems | Volume: | 30 | Issue: | 1 | First page: | 31 | Last page: | 44 | Issue Date: | 1-Jan-2011 | Rank: | M21 | ISSN: | 0278-0070 | DOI: | 10.1109/TCAD.2010.2069290 | Abstract: | This paper deals with the number of paths in multiterminal binary decision diagrams (MTBDDs) and shared binary decision diagrams (SBDDs) representing a set of Boolean functions. It is shown that the number of paths in an MTBDD (SBDD) can be uniquely determined by values of specific weighted-autocorrelation coefficients. An analytical expression for the number of paths as a linear function of the values of the weighted-autocorrelation coefficients is presented. Based on this expression, a method of minimization of the number of paths is proposed. The method is based on replacing the initial set of input variables with their linear combinations. By using this method, a deterministic paths-reduction procedure, which provides MTBDDs and SBDDs with a reduced number of paths, is presented. The efficiency of the suggested approach is demonstrated on benchmark functions. |
Keywords: | Autocorrelation function | Binary decision diagram (BDD) | Linear transform | Logic synthesis | Spectral technique | Publisher: | IEEE |
Show full item record
SCOPUSTM
Citations
8
checked on Dec 2, 2024
Page view(s)
14
checked on Dec 1, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.