Spectral Techniques in Vlsi CAD

by Thornton, Mitchell Aaron; Drechsler, Rolf; Miller, D. Michael

• ISBN13: 9780792374336
• ISBN10: 0792374339
• Format: Hardcover
• Copyright: 2001-07-01
• Publisher: Kluwer Academic Pub

Summary

Spectral Techniques in VLSI CAD have become a subject of renewed interest in the design automation community due to the emergence of new and efficient methods for the computation of discrete function spectra. In the past, spectral computations for digital logic were too complex for practical implementation. The use of decision diagrams for spectral computations has greatly reduced this obstacle allowing for the development of new and useful spectral techniques for VLSI synthesis and verification. Several new algorithms for the computation of the Walsh, Reed-Muller, arithmetic and Haar spectra are described. The relation of these computational methods to traditional ones is also provided. Spectral Techniques in VLSI CAD provides a unified formalism of the representation of bit-level and word-level discrete functions in the spectral domain and as decision diagrams. An alternative and unifying interpretation of decision diagram representations is presented since it is shown that many of the different commonly used varieties of decision diagrams are merely graphical representations of various discrete function spectra. Viewing various decision diagrams as being described by specific sets of transformation functions not only illustrates the relationship between graphical and spectral representations of discrete functions, but also gives insight into how various decision diagram types are related. Spectral Techniques in VLSI CAD describes several new applications of spectral techniques in discrete function manipulation including decision diagram minimization, logic function synthesis, technology mapping and equivalence checking. The use of linear transformations in decision diagram size reduction is described and the relationship to the operation known as spectral translation is described. Several methods for synthesizing digital logic circuits based on a subset of spectral coefficients are described. An equivalence checking approach for functional verification is described based upon the use of matching pairs of Haar spectral coefficients.

Table of Contents

Preface	xi
Introduction	1	(6)
Motivation	1	(1)
Background and History	2	(2)
Mathematical Requirements	4	(1)
Organization	5	(2)
The Boolean Domain	7	(12)
Boolean Functions	7	(3)
Pseudo-Boolean Functions	10	(1)
Output Probability	11	(7)
Summary	18	(1)
The Spectral Domain	19	(32)
Spectra of Logic Functions	19	(2)
Spectral Transforms	21	(10)
Transform Procedures	31	(10)
Relationships Between the Transforms	41	(5)
Spectral Properties	46	(4)
Summary	50	(1)
Decision Diagrams	51	(32)
Decision Diagram Definitions	51	(1)
Decision Diagram Varieties	52	(2)
Bit-level Decompositions	54	(3)
Word-level Decompositions	57	(6)
Edge-valued Decision Diagrams	63	(17)
Summary	80	(3)
Computation of Spectral Coefficients	83	(34)
Cube List Approaches	83	(7)
Methods Based on BDD Paths and Disjoint Cubes	90	(1)
Spectral Computation Using Decision Diagrams	91	(18)
Computation Based on Cayley Graphs	109	(5)
Spectra of Incompletely-specified Functions	114	(2)
Summary	116	(1)
BDD Minimization	117	(40)
BDD Variable Ordering Techniques	118	(2)
Probability Based Minimization	120	(9)
Linear Transformations	129	(23)
Summary	152	(5)
Logic Synthesis	157	(44)
Spectral Translation	157	(2)
Maximum Correlation Iterative Approach	159	(17)
Synthesis Using Spectral Heuristics	176	(14)
Technology Mapping	190	(9)
Summary	199	(2)
Logic Verification	201	(30)
Classical Approaches	201	(1)
Signature Methods	202	(2)
Subsets of Haar Coefficients for Equivalence Checking	204	(25)
Summary	229	(2)
Concluding Remarks	231	(2)
References	233	(14)
Index	247