Behavioral synthesis of combinational logic using spectral-based heuristics

ABSTRACT

A prototype system developed to convert a behavioral representation of a Boolean function in OBDD form into an initial structural representation is described and experimental results are given. The system produces a multilevel circuit using heuristic rules based on properties of a subset of spectral coefficients. Since the behavioral description is in OBDD form, efficient methods are used to quickly compute the small subset of spectral coefficients needed for the application of the heuristics. The heuristics guide subsequent decompositions of the OBDD, resulting in an iterative construction of the structural form. At each stage of the translation, the form of the decomposition is chosen in order to achieve optimization goals.

REFERENCES

• 1: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 2: BRAYTON, R. K., RUDELL, R., SANGIOVANNI-VINCINTELLI, A. L., AND WANG, A. R 1987. Mis: A multiple-level logic optimization system. IEEE Trans. CAD CAD-6, 6, 1062-1081.
• 3: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 4: CHOW, C. K. 1961. On the characterization of threshold functions. In IEEE Special Publication. 34-38.
• 5: 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]
• 6: DAVIO, M., DESCHAMPS, J.-P., AND THAYSE, A. 1978. Discrete and Switching Functions. McGraw-Hill, London, UK.
• 7: EDWARDS, C. R. 1977. The design of easily tested circuits using mapping and spectral techniques. Radio Electrical Eng. 47, 7, 321-342.
• 8: Stanley L. Hurst , Jon C. Muzio , D. Michael Miller, Spectral Techniques in Digital Logic, Academic Press, Inc., Orlando, FL, 1985
• 9: Mark Karpovsky, Finite Orthogonal Series in Design of Digital Devices, John Wiley & Sons, 2006
• 10: Shin-ichi Minato , Nagisa Ishiura , Shuzo Yajima, Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.52-57, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123225]
• 11: S. Muroga , Y. Kambayashi , H. C. Lai , J. N. Culliney, The Transduction Method-Design of Logic Networks Based on Permissible Functions, IEEE Transactions on Computers, v.38 n.10, p.1404-1424, October 1989 [doi>10.1109/12.35836]
• 12: Dhiraj K. Pradhan, Fault-tolerant computing: theory and techniques; vol. 1, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 13: RUDELL, R. AND SANGIOVANNI-VINCINTELLI, A. L. 1985. Espresso-mv: Algorithms for multiplevalued logic minimization. In Proceedings of the IEEE Conference on Custom Integrated Circuits. IEEE Computer Society, New York, NY, 230-234.
• 14: SHANNON, C. E. 1938. Symbolic analysis of relay and switching circuits. Trans. AIEE 57, 713-723.
• 15: THORNTON, M. A. AND NAIR, V. S. S. 1995. Parity function detection and realization using a small set of spectral coefficients. In Proceedings of the ACM/IEEE International Workshop on Logic Synthesis (May 1995). ACM Press, New York, NY.
• 16: THORNTON, M. A. AND NAIR, V. S. S. 1995. Efficient calculation of spectral coefficients and their applications. IEEE Trans. CAD/ICAS 14, 11 (Nov.), 1328-1341.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

General Terms:
Design

Keywords:
automatic synthesis, decision diagrams, design aids, logic design, spectral methods