A recursive paradigm to solve Boolean relations

ABSTRACT

A recursive algorithm for solving Boolean relations is presented. It provides several features: wide exploration of solutions, parametrizable cost function and efficiency. The experimental results show the applicability of the method and tangible improvements with regard to previous heuristic approaches.

REFERENCES

• 1: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 2: R. Brayton and F. Somenzi. An exact minimizer for boolean relations. In Proc. Int. Conf. Computer-Aided Design (ICCAD), pages 316--319, Nov. 1989.
• 3: F. Brown. Boolean Reasoning: The Logic of Boolean Equations. Kluwer Academic Publishers, 1990.
• 4: O. Coudert, C. Berthet, and J. Madre. Verification of synchronous sequential machines using boolean functional vectors. In Proc. IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, pages 111--128, Nov. 1989.
• 5: O. Coudert and J. Madre. A unified framework for the formal verification of circuits. In Proc. Int. Conf. Computer-Aided Design (ICCAD), pages 126--129, Nov. 1990.
• 6: M. Damiani, J. Yang, and G. D. Micheli. Optimization of combinational logic circuits based on compatible gates. IEEE Transactions on Computer-Aided Design, 14(11):1316--1327, Nov. 1995.
• 7: A. Ghosh, S. Devadas, and A. Newton. Heuristic minimization of boolean relations using testing techniques. In Proc. International Conf. Computer Design (ICCD), Sept. 1990.
• 8: P. Hofstee and F. Alam. Design of high end processors for the consumer space, Nov. 2003. Talk at Sunday Workshop ICCAD.
• 9: Seh-Woong Jeong , Fabio Somenzi, A new algorithm for the binate covering problem and its application to the minimization of Boolean relations, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.417-420, November 1992, Santa Clara, California, United States
• 10: B. Lin and F. Somenzi. Minimization of symbolic relations. In Proc. Int. Conf. Computer-Aided Design (ICCAD), pages 88--91, Nov. 1990.
• 11: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 12: S. Minato. Fast generation of prime-irredundant covers from binary decision diagrams. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E76-A(6):967--973, June 1993.
• 13: H. Partovi. Clocked storage elements. In A. Chandrakasan, W. Bowhill, and F. Fox, editors, Design of High-Performance Microprocessor Circuits, chapter 11, pages 207--234. IEEE Press, 2001.
• 14: Ellen Sentovich , Daniel Brand, Flexibillity in logic, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
• 15: M. Stone. The theory of representations for Boolean algebras. Trans. Amer. Math. Soc., 40:37--111, 1936.
• 16: Y. Watanabe and R. Brayton. Heuristic minimization of multiple-valued relations. IEEE Transactions on Computer-Aided Design, 12(10):1458--1472, Oct. 1993.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
Boolean relations, decomposition, logic design