On the minimization of SOPs for bi-decomposition functions

ABSTRACT

A function f is AND bi-decomposable if it can be written as f (X1,X2) = h1(X1)h2(X2). In this case, a sum-of-products expression (SOP) for f is obtained from minimum SOPs (MSOP) for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for f. We show an incompletely specified function of n(n-1) variables that requires at most n products in an MSOP, while 2(n-1) products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for f . We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.

REFERENCES

• 1: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 2: R. S. Michalski and Z. Kulpa, "A system of programs for the synthesis of switching circuits using the method of disjoint stars," Proceedings of IFIP Congress, pp. 61-65, April 1971.
• 3: A. Odlyzko, "On covering a product of sets with products of subsets," Discrete Mathematics, pp. 373-380, 1973.
• 4: W. J. Paul, "Realizing Boolean functions on disjoint set of variables," Theoretical Computer Science 2, pp. 383-396, 1976.
• 5: R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization," IEEE Trans. Computer- Aided Design, vol. CAD-6, No. 5 pp. 727-749, September 1987.
• 6: T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," 1998 International Workshop on Logic Synthesis, Lake Tahoe, pp. 471-477, June 1998.
• 7: Bernd Voigt , Ingo Wegener, A Remark on Minimal Polynomials of Boolean Functions, Proceedings of the 2nd Workshop on Computer Science Logic, p.372-383, October 03-07, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Performance, Theory