Spectral Interpretation of Decision DiagramsDecision diagrams (DDs) are data structures for efficient (time/space) representations of large discrete functions. In addition to their wide application in engineering practice, DDs are now a standard part of many CAD systems for logic design and a basis for severe signal processing algorithms. "Spectral Interpretation of Decision Diagrams" derives from attempts to classify and uniformly interpret DDs through spectral interpretation methods, relating them to different Fourier-series-like functional expressions for discrete functions and a group-theoretic approach to DD optimization. The book examines DDs found in literature and engineering practice and provides insights into relationships between DDs and different polynomial or spectral expressions for representation of discrete functions. In addition, it offers guidelines and criteria for selection of the most suitable representation in terms of space and time complexity. The work complements theory with numerous illustrative examples from practice. Moreover, the importance of DD representations to the verification and testing of arithmetic circuits is addressed, as well as problems related to various signal processing tasks. |
Contents
Algebraic Structures for Signal Processing | 7 |
Spectral Techniques | 17 |
Fourier Analysis on Groups | 49 |
Spectral Interpretation of Decision Diagrams | 71 |
Advanced Topics in Decision Trees and Diagrams 89 | 88 |
Optimization of Decision Diagrams | 125 |
WordLevel Decision Diagrams 145 | 144 |
Spectral Interpretation of EdgeValued | 167 |
Spectral Interpretation of Ternary Decision Diagrams | 181 |
Group Theoretic Approach to Optimization | 235 |
Closing Remarks | 254 |
References | 261 |
List of Decision Diagrams | 279 |
Other editions - View all
Spectral Interpretation of Decision Diagrams Radomir Stankovic,Jaakko T. Astola Limited preview - 2006 |
Spectral Interpretation of Decision Diagrams Radomir Stankovic,Jaakko T. Astola No preview available - 2013 |
Spectral Interpretation of Decision Diagrams Radomir Stankovic,Jaakko T Astola No preview available - 2014 |
Common terms and phrases
addition algebraic algorithm applications arithmetic transform assigned assumed basic basis binary Boolean difference calculation coefficients columns complex Comput considered constant nodes corresponding decision diagrams decomposition rules defined definition denoted Design determined discrete domain dyadic elements equal Example EXOR-TDDs expansion expressions extended f in Example field Figure finite FNADDs Fourier function f Gibbs derivatives given Haar Haar functions identity integer inverse Kronecker labels logic matrix method MTBDDs MTDTs multiplication non-terminal nodes notation operations optimization outgoing edges partial particular paths performed permutation points polarity positive possible Proc processing properties QDDs reduction Reed-Muller relationships Remark representations represented respect rules shows signal spectral interpretation spectral transform spectrum Stankovic STDT structure switching functions Table TDDs theory tree truth-vector values values of constant variables vector Walsh functions weights word-level