Determining the Number of Paths in Decision Diagrams by Using Autocorrelation Coefficients

作者：Keren Osnat^*; Levin Ilya; Stankovic Radomir S

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(1): 31-44.

DOI：10.1109/TCAD.2010.2069290

• Autocorrelation function
• binary decision diagram (BDD)
• linear transform
• logic synthesis
• spectral technique

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.

• 出版日期2011-1