Efficient prime factorization of logic expressions

ABSTRACT

The set of multivariate Boolean functions over the variables &khgr;1 …, &khgr;m is considered as the set of multilinear polynomials with coefficients in [0,1] over the literals {&khgr;1, &khgr;1, …, &khgr;m, &khgr;m}. We denote this set of polynomials as B[@@@@], and call the set of polynomial operations over them algebraic operations. It is shown that these polynomials, called logic expressions, have a unique algebraic prime factorization. An &Ogr;(n log2 n) algorithm to find this factorization is presented. An improvement to the algorithm is presented which may reduce its average-case complexity to &Ogr;(n).

REFERENCES

• 1: R. K. Brayton. Algorithms for Multi-Level Logic Synthesis and Organization. In NATO Advanced Study Institute on Logic Synthesis and Silicon Compilation for VLSI Design, 1986.
• 2: R. K. Brayton and C. T. McMuilen. The Decomposition and Factorization of Boolean Functions. In Internal Symposium on Circuits and Systems, 1982.
• 3: R. K. Brayton and C. T. McMullen. Synthesis and Optimization of Multistage Logic. In IEEE International Conference on Computer Design, 1984.
• 4: R. K. Brayton et. al. Multiple-Level Logic Optimization System. In IEEE International Conference on Computer-Aided Design, 1986.
• 5: J. Fraleigh. A First Course in Abstract Algebra. Addison-Wesley, Reading, MA, 1976.
• 6: P. C. McGeer and {{. K. Brayton. Efficient, Stable Algebraic Operations on Logic Expressions. In International Conference on VLSJ, 1987.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Design, Experimentation, Theory