Skip to main content
main-content

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
Motivation for the consideration of the use of spectral methods in VLSI CAD methods is given, and a brief history of important research results is also included. The prerequisite mathematical background for easily understanding this book is outlined and this chapter concludes with a description of the organization of the remainder of the text
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

2. The Boolean Domain

Abstract
Definitions and notation used throughout the remainder of this book are introduced here. In addition, basic concepts of Boolean functions as used throughout this book are also reviewed. Output probabilities which are used extensively in later chapters are introduced and results relating them to Boolean functions are also presented
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

3. The Spectral Domain

Abstract
The fundamental structures and properties of spectral transforms and the resulting spectra of Boolean functions is presented here. We restrict ourselves to the mathematical foundations necessary for the development and understanding of the techniques introduced in later chapters. Those wishing a more in-depth and rigorous mathematical treatment of the subject should consult the literature [1, 5, 97, 90, 92]. Matrix based computation of the spectra is considered as are “fast” transform techniques derived from the matrix structures. Alternative spectral computation methods, in particular those based on DDs, are discussed in Chapter 5
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

4. Decision Diagrams

Abstract
This chapter focuses on the use of various forms of Decision Diagrams (DDs) for the representation of the spectra of Boolean functions. Several DD variants will be described with their unique characteristics discussed followed by a description of their usage in representing Boolean functions in the binary as well as the spectral domains
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

5. Computation of Spectral Coefficients

Abstract
The advances in DD representations for discrete valued functions in terms of computational efficiency can be exploited in the calculation of the spectra of Boolean functions. The fundamental matrix approach and the fast transforms derived from the matrix structures were discussed in Chapter 3. This chapter begins with a review of cube list based approaches for computing spectral coefficients after which the computation of spectral coefficients based on output probabilities is considered in some depth. Implementation of all these approaches using DDs is then addressed. A recent method based on Cayley graphs for the computation of the Walsh spectrum is discussed. The chapter concludes with a discussion of incompletely-specified functions and the calculation of their spectra
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

6. BDD Minimization

Abstract
Binary Decision Diagrams (BDDs) are a powerful tool and are frequently used in many applications in VLSI CAD, such as logic synthesis and verification. However, these data structures are very sensitive to variable ordering and their resulting size often becomes intractable for practical implementation. Several techniques for variable (re-)ordering have been proposed. (For an overview see [43])
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

7. Logic Synthesis

Abstract
Logic synthesis is generally considered to be a mature technology and is uti lized to some extent in the design of all modern integrated circuit devices. The most popular approach for logic synthesis is the use of methods in the Boolean domain. However, many logic synthesis operations can be carried out in the spectral domain, and some tasks such as Boolean matching and function decomposition are actually easier to perform in the spectral rather than the Boolean domain for many cases. This chapter will present some spectral-based techniques for performing logic synthesis
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

8. Logic Verification

Abstract
Logic verification is to check the correct behavior of a given circuit against its specification. This specification can be given in the form of another circuit at some higher level of abstraction or as a description of properties that the circuit is to obey. In this chapter a review of some “classical” approaches for verification is given followed by a discussion of a spectral based technique for equivalence checking [154]. For more detailed surveys of verification methodologies see [31, 79, 88, 99]
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

9. Concluding Remarks

Abstract
In this book, we have explored spectral techniques with a view to applications in VLSI CAD. In particular, it has been shown that the use of decision diagrams allows spectral techniques, which previously have been computationally quite limited, to be applied to realistic problems
Mitchell Aaron Thornton, Rolf Drechsler, D. Michael Miller

Backmatter

Weitere Informationen