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.