A graph-based synthesis algorithm for AND/XOR networks

ABSTRACT

In this paper, we introduce a Shared Multiple Rooted XOR-based Decomposition Diagram (XORDD) to represent functions with multiple outputs. Based on the XORDD representation, we develop a synthesis algorithm for generalExclusive Sum-of-Product forms (ESOP). By iteratively applying transformations and reductions, we obtain a compactXORDD which gives a minimized ESOP. Our method cansynthesize larger circuits than previously possible. The compact ESOP representation provides a form that is easier to synthesize for XOR heavy multi-level circuit, such as arithmetic functions. We have applied our synthesis techniquesto a large set of benchmark circuits in both PLA and combinational formats. Results of the minimized ESOP forms obtained from our synthesis algorithm are also comparedto the SOP forms generated by ESPRESSO. Among the 74circuits we have experimented with, the minimized ESOP'shave fewer product terms than those of SOP's in 39 circuits.

REFERENCES

• 1: R.Brayton, R.Rudell, A.Sangiovanni-Vincentelli, and A.Wang, "MIS: A Multi-level Logic Optimization System," IEEE Transactions on CAD/ICAS, Vol. CAD-6, No. 6, November 1987, pp. 1062-1081.
• 2: 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]
• 3: Rolf Drechsler , Bernd Becker , Michael Theobald, Fast OFDD based minimization of fixed polarity Reed-Muller expressions, Proceedings of the conference on European design automation, p.2-7, September 19-23, 1994, Grenoble, France
• 4: 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]
• 5: H. Fleisher , M. Tavel , J. Yeager, A computer algorithm for minimizing Reed-Muller canonical forms, IEEE Transactions on Computers, v.36 n.2, p.247-250, Feb. 1987 [doi>10.1109/TC.1987.1676890]
• 6: G. Hachtel, M.Lightner, R.Jacoby, C.Morrison, P.Moceyunas, and D. Bostik, "Bold: The Bould optimal Logic Design System," Hawaii Int. Symp. on Systems Sciences, 1988.
• 7: U.Kebschull, E.Schubert, and W.Rosenstial, "Multilevel Logic Based on Functional Decision Diagrams," Proc. European Design Automation Conf., 1992, pp. 43-47.
• 8: S. Malik, A.R.Wang, R.K. Brayton, and A. Sangiovanni- Vincentelli, "Logic Verification using Binary Decision Diagrams," Proc. Intl. Conference on Computer-Aided Design., 1988, pp. 6-9.
• 9: A. Sarabi , M. A. Perkowski, Fast exact and quasi-minimal minimization of highly testable fixed-polarity AND/XOR canonical networks, Proceedings of the 29th ACM/IEEE conference on Design automation, p.30-35, June 08-12, 1992, Anaheim, California, United States
• 10: Marek A. Perkowski , Laszlo Csanky , Andisheh Sarabi , Ingo Schäfer, Fast Minimization of Mixed-Polarity AND/XOR Canonical Networks, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.33-36, October 11-14, 1992
• 11: R.Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued Minimization for PLA Optimization," IEEE transactions on CAD/ICAS, Vol. CAD-6, No. 5, September 1987, pp727-750.
• 12: T.Sasao, "EXMIN2: A Simplification Algorithm for Exclusive- OR-SUM-of Products Expressions for Multiple-Valued-Input Two-Valued-Output Functions," IEEE Trans. on Computer- Aided Design, Vol. 12, No. 5, May 1993, pp. 621-632.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory