Functionally linear decomposition and synthesis of logic circuits for FPGAs

ABSTRACT

This paper presents a novel logic synthesis method to reduce the area of XOR-based logic functions. The idea behind the synthesis method is to exploit linear dependency between logic sub-functions to create an implementation based on an XOR relationship with a lower area overhead. Experiments conducted on a set of 99 MCNC benchmark (25 XOR based, 74 non-XOR) circuits show that this approach provides an average of 18.8% area reduction as compared to BDS-PGA 2.0 and 25% area reduction as compared to ABC for XOR-based logic circuits.

REFERENCES

• 1: Tsutomu Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers, Norwell, MA, 1999
• 2: Stanley L. Hurst , Jon C. Muzio , D. Michael Miller, Spectral Techniques in Digital Logic, Academic Press, Inc., Orlando, FL, 1985
• 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: M. Karpovsky, "Harmonic analysis over finite commutative groups in linearization problems for systems of logical functions," Inf. Contr., vol. 33, no. 2, Feb. 1977, pp. 142--165.
• 5: Congguang Yang , Maciej Ciesielski , Vigyan Singhal, BDS: a BDD-based logic optimization system, Proceedings of the 37th conference on Design automation, p.92-97, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337323]
• 6: Navin Vemuri , Priyank Kalla , Russell Tessier, BDD-based logic synthesis for LUT-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.501-525, October 2002 [doi>10.1145/605440.605442]
• 7: M. Perkowski and S. Grygiel, "A Survey of Literature on Function Decomposition," A Final Report for Summer Faculty Research Program, Wright Laboratory, Sponsored by Air Force Office of Scientific Research, Bolling Air Force Base, DC and Wright Laboratory, September 1994.
• 8: Wei Wan , Marek A. Perkowski, A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping, Proceedings of the conference on European design automation, p.230-235, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 9: T. Sasao and J. T. Butler, "A Design Method for Look-up Table Type FPGA by Pseudo-Kronecker Expansion," Proc. Of 24^th Int. Symp. On MV Logic, 1994, pp. 97--106.
• 10: Chien-Chung Tsai , Malgorzata Marek-Sadowska, Multilevel logic synthesis for arithmetic functions, Proceedings of the 33rd annual conference on Design automation, p.242-247, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240563]
• 11: 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]
• 12: BDD Decomposition for Efficient Logic Synthesis, Proceedings of the 1999 IEEE International Conference on Computer Design, p.626, October 10-13, 1999
• 13: H. Anton and C. Rorres, Elementary Linear Algebra, Applications Version, 7^th Edition, Published by John Wiley & Sons Inc., 1994, ISBN 0-471058741-9.
• 14: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 15: Berkeley Logic Synthesis Group, ABC: A System for Sequential Synthesis and Verification, December 2005 Release. URL: http://www.eecs.berkeley.edu/~alanmi/abc.
• 16: TT Hwang, R. M. Owens, and M. J. Irwin, "Exploiting Communication Complexity for Multilevel Logic Synthesis," IEEE Trans. On CAD, vol. 9, No. 10, Oct 1990, pp. 1017--1027.
• 17: Ajay K. Verma , Philip Brisk , Paolo Ienne, Progressive decomposition: a heuristic to structure arithmetic circuits, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278585]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
Gaussian elimination, decomposition, linearity, logic synthesis