Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 2: Randal E. Bryant , Yirng-An Chen, Verification of arithmetic circuits with binary moment diagrams, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.535-541, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217583]
• 3: E. M. Clarke , K. L. McMillan , X Zhao , M. Fujita , J. Yang, Spectral transforms for large boolean functions with applications to technology mapping, Proceedings of the 30th international conference on Design automation, p.54-60, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164569]
• 4: Drechsler, R. and Becker, B. Binary Decision Diagrams - Theory and Implementation. Kluwer Academic Publishers. 1998.
• 5: R. Drechsler , A. Sarabi , M. Theobald , B. Becker , M. A. Perkowski, Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams, Proceedings of the 31st annual conference on Design automation, p.415-419, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196444]
• 6: Falkowski, B. Forward and inverse transforms between Haar wavelet and arithmetic functions. Electronic Letters. 34, 10, (May 13, 1998), 1084-1085.
• 7: Falkowski, B. Relationship between arithmetic and Haar wavelet transforms in the form of layered Kronecker matrices. Electronic Letters. 35, 11, (May 28, 1999), 799- 800.
• 8: Bogdan J. Falkowski , Chip-Hong Chang, Forward and Inverse Transformations Between Haar Spectra and Ordered Binary Decision Diagrams of Boolean Functions, IEEE Transactions on Computers, v.46 n.11, p.1272-1279, November 1997 [doi>10.1109/12.644301]
• 9: Graham, A. Kronecker Products and Matrix Calculus: with Applications. Ellis Horwood Limited and John Wiley & Sons. 1981.
• 10: Jeffery P. Hansen , Masatoshi Sekine, Synthesis by spectral translation using Boolean decision diagrams, Proceedings of the 33rd annual conference on Design automation, p.248-253, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240564]
• 11: Stanley L. Hurst , Jon C. Muzio , D. Michael Miller, Spectral Techniques in Digital Logic, Academic Press, Inc., Orlando, FL, 1985
• 12: Kebschull, U., Schubert, E., and Rosenstiel, W. Multilevel logic synthesis based on functional decision diagrams. in European Conf. on Design Automation. (Brussels Belgium, March 1992), 43-47.
• 13: Kunz, W. and Pradhan, D. K. Recursive learning: a new implication technique for efficient solutions of cad problems: test, verification and optimization. IEEE Trans. on CAD. 13, 9, (September 1994), 1143-1158.
• 14: Miller, D. M. Graph algorithms for the manipulation of Boolean functions and their spectra. in Congressus Numerantium, (1987), 177-199.
• 15: Perkowski, M. A., Driscoll, M., Liu, J., Smith, D., Brown, J., Yang, L., Shamsapour, A., Helliwell, M., and Falkowski, B. Integration of logic synthesis and high-level synthesis into the diades design automation system. in Int'l. Symp. Circuits and Systems. (Portland OR, May 1989), 718-751.
• 16: Radecka, K. and Zilic, Z. Relating arithmetic and Walsh spectra for verification by implicit error modeling. in Int'l. Workshop on Applications of the Reed-Muller Expansion in Circuit Design. (Mississippi State MS, August 2001), 205- 214.
• 17: Somenzi, F. CUDD: CU Decision Diagram Package Release 2.3.0. http://www.vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html.
• 18: Stankovic, R. S. A note on the relation between Reed- Muller and Walsh transforms. IEEE Trans. on EMC. 24, 2, (February 1982), 68-70.
• 19: Stankovic, R. S. Sasao, T., and Moraga, C. Spectral transforms decision diagrams. in Sasao, T. and Fujita, M. (eds.), Representation of Discrete Functions. Kluwer Academic Publishers. 1996.
• 20: Susskind, A. K. Testing by verifying Walsh coefficients. IEEE Trans. on Comp. 32, 2, (February 1983), 198-201.
• 21: M. Thornton , R. Drechsler, Spectral decision diagrams using graph transformations, Proceedings of the conference on Design, automation and test in Europe, p.713-719, March 2001, Munich, Germany
• 22: Mitch Thornton , Rolf Drechsler , Wolfgang Guenther, A Method for Approximate Equivalence Checking, Proceedings of the 30th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2000), p.447, May 23-25, 2000
• 23: Mitchell Aaron Thornton , D. Michael Miller , Rolf Drechsler, Spectral Techniques in VLSI CAD, Kluwer Academic Publishers, Norwell, MA, 2001
• 24: Varma, D. and Trachtenberg, E. A. Design automation tools for efficient implementation of logic functions by decomposition. IEEE Trans. on CAD. 8, 8, (August 1989), 901-916.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Verification; Switching theory; Optimization

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Verification

Keywords:
data structures, decision diagrams, discrete functions, spectral methods