Decision Diagrams and Spectral Techniques
Chrestenson Spectrum Computation Using Cayley Color Graphs
Mitchell A. Thornton, D. Michael Miller, and Whitney J. Townsend
32nd IEEE International Symposium for Multiple-Valued Logic
pp. 123-128, Boston, MA, May 15-18, 2002
Abstract
A method based on eigenvalue computations is formulated for computing the Chrestenson spectrum of a discrete p-valued function. This technique is developed by considering an extension to the same approach of computation of the Walsh spectrum for a two-valued function and is then generalized to the p-valued case. Algebraic groups are formulated that correspond to Cayley color graphs based on the function of interest whose adjacency matrices have spectra equivalent to the Walsh or Chrestenson spectrum of the function under consideration. Because the transformation matrix is not used in any of these computations, the method provides an alternative approach for spectral computations.
pdf
Computing Walsh, Arithmetic, and Reed-Muller Spectral
Decision Diagrams Using Graph Transformations
Whitney J. Townsend, Mitchell A. Thornton, Rolf Drechsler, and D. Michael Miller
12th ACM/IEEE Great Lakes Symposium on VLSI
pp. 178-183, New York City, NY, April 18-20, 2002
Abstract
Spectral techniques have found many applications in computer-aided design, including synthesis, verification, and testing. Decision diagram representations permit spectral coefficients to be calculated via graph-based algorithms. In this paper, algorithms are described for transforming multi-output functions to produce Walsh, arithmetic, and Reed-Muller spectral decision diagrams and the experimental results of those implementations are presented.
pdf
presentation pdf
Partial Binary Decision Diagrams
Whitney J. Townsend and Mitchell A. Thornton
34th IEEE Southeastern Symposium on System Theory
pp. 422-425, Huntsville, AL, March 18-19, 2002
Abstract
Decision diagrams provide compact representations for discrete functions. There are some functions for which binary decision diagrams reach exponential size. Presented here is a method of representing Boolean functions as multiple partial decision diagrams.
pdf
Walsh Spectrum Computations Using Cayley Graphs
Whitney J. Townsend and Mitchell A. Thornton
44th IEEE Midwest Symposium on Circuits and Systems
vol. 1, pp. 110-113, Dayton, OH, August 14-17, 2001
Abstract
The Walsh spectrum for a Boolean function has found many uses in VLSI CAD. A graph-based approach to calculating this spectrum using Cayley graphs is extended here to include alternate encoding, direct computation of the spectrum for the inverse of a function and a "fast" method of calculation for the adjacency matrix of a graph.
pdf
presentation pdf