Some Methods for Simplifying Switching Circuits Using “Don't Care” Conditions

ABSTRACT

Several methods for simplifying switching circuits using “don't-care” conditions are suggested. One of the methods uses the following procedure: Let the given circuit be represented by the truth function F. Let the given “don't-care” conditions be denoted byD = 0. (For example, if x1 = 1 and x2 = 0 represent the combination of input signals which never takes place, then D = x1x2.) Generate all the irredundant disjunctive and conjunctive forms which are equivalent toF wheneverD = 0. From these forms, the simplest ones may then be chosen according to a given measure of simplicity. They correspond to the simplest two-level AND/OR or OR/AND switching circuits which, under the “don't-care” conditions, perform the same function as the given circuit. Several methods for generating the equivalent irredundant forms are suggested. They are generalizations of those due to Quine, Ghazala and Mott, and may be programmed for use on computers. Alternative simplification methods are also given.

REFERENCES

• 1: ABI4YAN:KAR, S. Minimal "sum of products of sums" expressions of Boolean functions IRE Trans Electr Comput. EC-7 (1958), 268-276.
• 2: A~aYAN~AR, S. Absolute minimal expressions of Boolean functions. IRE Trans. Electr. Compu~. F~C~8 (1959), 3-8.
• 3: Gm~zx~,~, M.J. Irredundant disjunctive and conjunctive forms of a Boolean function. IBM J. Res. Dev. I (1957), 171-176.
• 4: McCL~zSKEr, E. j., J~. Minimization of Boolean functions. Bell System Tech. J. 8~ (1956), 1417-1444
• 5: Mow% T. H., JR. Determination of the irredundant normal forms of a truth function by iterated consensus of the }.)rime implicants. IRE Trans. Electr. Comput. EC-9 (1960).
• 6: MoT% T. H., JR. Simplest normal forms of incomplete truth functions. AIEE Conference paper CP t123, Oct. 1959.
• 7: N~T.SON, R. J. Weak simplest normal truth functions. J. Symbolic Logic ~0 (1955), 232-234.
• 8: PEI'mcK, S.R. A direct determination of the irredundant forms of a Boolean function from the set of prime implicants. AFCRC-TR-56-110, AFCRC, Cambridge, Mass., Apr. 1956.
• 9: QUINE, W.V. A problem of simplifying truth functions. Amer. Math. Month. 59 (1952), 521-531.
• 10: QUINE, W.V. A way to simplify truth functions. Amer. Math. Month. 65 (1955), 627- 631.
• 11: ROTH, J. P. Algebraic topological methods for the synthesis of switching systems, I. Trans. Amer. Math. Soc. 88 (1958), 301-326.
• 12: ROWH, J.P. Algebraic topological methods in synthesis. Proceeding8 of an International Symposzum on the Theory of Sw~tchzng, pp. 57-73; Harvard University Press, Cambridge, Mass., 1959.
• 13: ROTH, J P., ~ND WANNER, E. G. Algebraic ~opological methods for the synthesis of switching systems, P~ III: Minimization of nonsingular Boolean trees. IBM J. Res. Dev. 3, No. 4 (1959), 326-344.
• 14: U~BANO~ R. H., AN9 MVEL~,ER, R. K. A topological method for the determination of the minimal forms of a Boolean function. IRE Trans. Etectr. Comput EC-5 (1956), 126-132.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Measurement, Performance, Theory, Verification