Thornton M.A., Drechsler R. Spectral Techniques in VLSI CAD

Springer, 2001. — 259 p.The application of spectral techniques in digital systems design is not new and many results have been presented in conference proceedings and archival journal papers. There are also several excellent books on this and related subjects. Nevertheless, a central reference volume fully devoted to developments in the use of spectral techniques in conjunction with the now popularly used Decision Diagram (DD) data structure has previously not been available. Our objective in writing this book has been to provide such a reference and, in particular, to bring together results on the use of DDs in the computation, representation, analysis and application of a variety of Boolean function spectra.
DDs have revolutionized many areas of digital circuit design and are the basis for a multitude of new algorithmic and Very Large Scale Integration (VLSI) Computer-Aided Design (CAD) methods. A common phenomenon is that CAD algorithms that are reformulated to use DD data structures often result in techniques with practical computational resource requirements. Many times these methods were previously computationally limited and thus could not be applied to the size of problems encountered in the VLSI circuit design arena. A major theme of this book is to show that DDs bring a level of practicality to spectral techniques that, without their use, has not previously been available. The intended audience for this book is CAD tool developers and, users, graduate students and researchers with an interest in the practical application of spectral techniques to VLSI and digital systems design.
In the past VLSI CAD practitioners may not have found interest in spectral methods due to the typical presentation of these techniques where heavy reliance on linear algebra and other mathematical constructs is included. One of our main goals in writing this book has been to present spectral methods in a manner that is easy to understand in the context of DDs and DD-based algorithms. Hence, this book is not intended to present a formal theoretical basis for these techniques. Rather we have chosen to include theory only to the level necessary to understand the applications of the practical methods presented.
The book begins with a description of necessary background information on Boolean functions, spectral techniques and DDs. The computation of a variety of spectra of Boolean functions is considered using matrix methods, so-called fast transform techniques, and DD-based methods derived from those traditional approaches. The interrelations between various spectral domains and the Boolean domain are given.
The vitally important area of DD minimization is examined in detail with emphasis on spectral DDs and on expediting spectral computations. A summary of some methods for automated synthesis using spectral techniques is presented and the application of spectral methods to the verification problem is described. It is our hope that this work will shed new light on the practicality of spectral techniques in VLSI CAD and will both promote the use of these techniques and inspire others to pursue further research in spectral methods.The Boolean Domain
The Spectral Domain
Decision Diagrams
Computation of Spectral Coefficients
BDD Minimization
Logic Synthesis
Logic Verification
Concluding Remarks