Heuristic switching expression simplification

ABSTRACT

One very profitable application of computer aided design is in the design and construction of digitial computers. 1 A classical problem in computer design is that associated with the simplification of Boolean switching expressions. Numerous algorithms exist for solving this problem, such as the Karnaugh or Veitch graph method, the Quine—McCluskey technique, the cubical complex approach of Roth,2 or the recently published procedure of Svoboda.3 In general, the classical minimization procedure consists first of generating all the canonical terms of a function, secondly of generating all of the prime implicants, and finally of selecting a minimal cover which consists of some subset of the set of prime implicants. For some techniques, these first two steps can be partially eliminated as illustrated by repeatedly applying the #-algorithm of Roth. The resulting solution usually represents a minimal diode or minimal gate two-level AND-OR or NAND representation of the given function. Many switching expressions encountered in the design of digital systems contain 20 or more variables. Usually they are obtained in one of two ways, i.e., either automatically by a logic generating system such as described by Gorman and Anderson, 4 or manually by a logic designer. In either case the equations are very seldom expressed in canonical form, but rather are usually in some near minimal normal form. Hence, it has generally been found to be impractical to spend hours of computation time to reduce a near minimal expression in order to save a few diodes or gates.

REFERENCES

• 1: M A BREUER General survey of design automation of digital computers Proc of the IEEE 54 1708-1721 (1966)
• 2: J P ROTH Algebraic topological methods for the synthesis of switching systems I Trans Am Math Soc 88 2 301-326 (1958)
• 3: A SVOBODA Ordering of implicants IEEE Trans on Electronic Computers EC-16 100-105 (1967)
• 4: D F GORMAN J P ANDERSON A logic design translator FJCC 86-92 (1962)
• 5: R W HOUSE T RADO Implementation of logic IRE Trans on Military Electronics MIL-6 3 297-302 (1962)
• 6: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 7: R E MILLER Switching theory combinational circuits (John Wiley and Sons Inc New York 1966) Vol I Cp 3 180-184

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

General Terms:
Algorithms, Theory