A method to decompose multiple-output logic functions

ABSTRACT

This paper shows a method to decompose a given multiple-output circuit into two circuits with intermediate outputs. We use a BDD for characteristic function (BDD for CF) to represent a multiple-output function.Many benchmark functions were realized by LUT cascades with intermediate outputs. Especially, adders and a binary to BCD converter were successfully designed. Comparison with FPGAs is also presented.

REFERENCES

• 1: R. L. Ashenhurst, "The decomposition of switching functions," In Proceedings of an International Symposium on the Theory of Switching, pp. 74--116, April 1957.
• 2: Pranav Ashar , Sharad Malik, Fast functional simulation using branching programs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.408-412, November 05-09, 1995, San Jose, California, United States
• 3: Ting-Ting Hwang, R. M. Owens, M. J. Irwin, and Kuo Hua Wang, "Logic synthesis for field-programmable gate arrays," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., Vol. 13, No. 10, pp. 1280--1287, Oct. 1994.
• 4: Jie-Hong R. Jiang , Jing-Yang Jou , Juinn-Dar Huang, Compatible class encoding in hyper-function decomposition for FPGA synthesis, Proceedings of the 35th annual conference on Design automation, p.712-717, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277223]
• 5: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 6: S. Muroga, VLSI System Design, John Wiley & Sons, 1982, pages 293--306.
• 7: Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic Synthesis for Field-Programmable Gate Arrays, Kluwer Academic Publishers, Norwell, MA, 1995
• 8: J. Rose, R. J. Francis, D. Lewis, and P. Chow, "Architecture of field-programmable gate arrays: The effect of logic block functionality on area efficiency," IEEE Journal of Solid-State Circuits, Vol. 25, No. 5, pp. 1217--1225, Oct. 1990.
• 9: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 10: T. Sasao, M. Matsuura, and Y. Iguchi, "A cascade realization of multiple-output function for reconfigurable hardware," International Workshop on Logic and Synthesis, Lake Tahoe, CA, June 12-15, 2001, pp.225--230.
• 11: T. Sasao, "Design methods for multi-rail cascades," International Workshop on Boolean Problems, Freiberg, Germany, Sept. 19-20, 2002, pp. 123--132.
• 12: Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
• 13: Christoph Scholl , Paul Molitor, Communication based FPGA synthesis for multi-output Boolean functions, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.43-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224910]
• 14: http://www.synplicity.com
• 15: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 16: http://www.xilinx.com

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
BDD, FPGA, cascade, characteristic function