Spectral Interpretation of Decision Diagrams

Front Cover
Springer Science & Business Media, Jun 16, 2003 - Computers - 285 pages
Decision 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
Copyright

Other editions - View all

Common terms and phrases