MINIMUM INVERSION COMPLEXITY
IN SWITCHING CIRCUITS
by
William Wharton Plummer
SUBMITTED IN PARTIAL FULFILLMENT OF THE
REQUIREMENTS FOR THE DEGREE OF
BACHELOR OF SCIENCE
at the
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
June, 1963
Signature of Author . . . . . . . . . . . . . . . . . . .
Department of Electrical Engineering
Certified by . . . . . . . . . . . . . . . . . . . . . . .
Thesis Supervisor
Accepted by . . . . . . . . . . . . . . . . . . . . . . .
Chairman,Departmental Senior Thesis Committee
.A.C.K.N.O.W.L.E.D.G.E.M.E.N.T
I would like to extend my thanks
to all those who aided me with
their useful suggestions. Special
appreciation is devoted to my
advisor Professor David A. Huffman
whose guidance and assistance made
this work possible.
.A.b.s.t.r.a.c.t
A method of complementing any number of binary
variables using AND-OR logic and only two inver-
ters is presented here. This is done by cascading
special circuits which complement N variables
using log
2
N inverters. It is shown that such a
cascade system has a unique equilibrium for each
combination of inputs.
In addition a computor program for simulating
sequential circuits is included.
.T.a.b.l.e .o.f .C.o.n.t.e.n.t.s
Introduction page 1
Notation page 1
Basic Circuit page 2
Problem of Cascading page 8
Analysis page 11
Conclusions page 17
Appendix page 20
MINIMUM INVERSION COMPLEXITY IN SWITCHING CIRCUITS
.I.n.t.r.o.d.u.c.t.i.o.n
The purpose of this work is to examine a method of
synthesizing switching circuits in a manner which uses
"AND-OR" logic elements and only two inverters. The
possibility exists that any circuit, regardless of how
complicated it may be, can be put in this form.
In papers by Markov
1.
and Gilbert
2.
the question
of inversion complexity is considered with the result
of an upper limit on the number of inverters necessary
to realize a given function or system of functions.
Therefore the formulation presented here will not con-
flict with the work of those authors.
.N.o.t.a.t.i.o.n
Before proceeding with the actual analysis, the
notation to be used is presented. According to stand-
ard practice, the inputs to a given circuit will be
designated by subscripted x's. Likewise, the outputs
will be shown as subscripted z's.
. . . . . . . . . . . . . . . . . . . . . . . .
1. Markov, A.A.,"On the Inversion Complesity of a
System of Functions," originally in
.D.o.k.l.a.d.y .A.c.a.d. .N.a.u.k .S.S.S.R, Vol 116, 1957,
pp. 917-9
2. Gilbert, E.N.,"Latice Theoretic Properties of
Frontal Switching Functions," .J. .M.a.t.h
.P.h.y.s., 33,57(1954)
Two types of functions which occur frequently are
the threshold and symmetric functions which appear as
T (N) and S (N) respectively. T (N) is a function
m >>75<<>>75<<>>75<<>>75<<>>75<>75<<3
(2) Select H(3) = T (3)
1 1 2
(3) Form H (3) = T (3)h (3) + T (3)
2 2 1 1 3
(4) From h (3) and h (3) [the complements of
1 2
H (3) and H (3)] along with the T (3),
>>75<<>>75<<>>75<<1 2 i
the symmetric functions are produced as follows_.
S (3) = h (3)h (3)
0 0 1 2
S (3) = h (3)T (3)
1 1 1
S (3) = h (3)T (3)
2 2 2
(5) Combine the Sm(3) with the x
i
(3) to get the
outputs.
z (3) = S (3) + S (3)[x (3) + x (3)] + S (3)[x (3)x (3)]
1 0 1 2 3 2 2 3
1 0 1 2 3 2 2 3
z (3) = S (3) + S (3)[x (3) + x (3)] + S (3)[x (3)x (3)]
2 0 1 1 >>75<<3 2 1 3
z (3) = S (3) + S (3)[x (3) + x (3)] + S (3)[x (3)x (3)]
3 0 1 1 2 2 >>75<<1 2
Algebraically this process is perfectly sound for
any N. The equations for N=3 are shown in Figure 3,
while those for N=7 are in Figure 4. The realizations
for these two cases are drawn Figures 5 and 6.
.T.h.e .P.r.o.b.l.e.m .o.f .C.a.s.c.a.d.i.n.g
Now the actual problem is approached -- given that
one can build a circuit which will supply the complements
of N variables using only L = log
2
N inverters, can
another similar circuit be used to replace the L inver-
ters in the first circuit? If so, only log
2
(log
2
N)
inverters would be needed to complement N binary sig-
nals. Can this process be repeated so that an arbitrarly
large number of signals can be complemented using only
two inverters? Figure 7 shows a system using this idea
which should complement one hundred twenty-seven vari-
ables.
.A.n.a.l.y.s.i.s
There are two ways in which a cascade circuit could
fail to function properly. One way is misoperation due
to delays in the logic. If it is assumed that ideal,
delayless elements are used, this problem does not exist.
The other possibility is that feedback loops may be
formed when two of these circuits are cascaded. This
might cause the overall circuit to "lock-up" in a
wrong mode of operation, or the circuit may just go into
the wrong stable state(s) and give the wrong output(s).
Consider the first type of fault. This will
give insight into the circuit operation and the results
will be valuable in the analysis of the second kind of
fault. Examine the N=3 case first and assume that the
delays are lumped as shown in Figure 8. Now the cir-
uit can be viewed as an ordinary sequential one and
the conventional flow table and output matrix written.
These tables are also shown in Figure 8 along with
a table of the symmetric functions as functions of the
inputs x
i
(3) and the secondary variables h
j
(3). It
is important to notice that the flow table has only one
stable entry for each input combination. This is also
true of the N=7 case as shown in Figure 9. In add->>75<<
ition there are no critical races -- these circuits
will always "settle down" in the proper stable state.
As a consequence, the secondary delays can be removed
and the circuits will still function properly. Of
course this is expected because these circuits are really
combinational. However, if the case of cascading circuits
built with real elements is considered interesting, these
tables, showing possible transient outputs, are import-
ant. Before this can be followed to its conclusion, the
problem of feedback loops must be resolved.
Prior to considering the feedback possibility, the
loops must be located. Since any level of a cascade
system is purely combinational, it can not contain any
closed loops. Consequently, all closed paths which arise
from the interconnection of two levels must cross the
boundary between these two levels.
If delays are inserted in every h lead, there will
be no feedback loops that do not pass through a delay,and
the total cascade circuit may be analyzed in the conven-
tional way. In particular consider the connection of
the N=3 and N=7 circuits as shown in figure 10. The
states variables are h (3),h (3),h (7),h (7), and h (7).
1 2 1 >>75<<2 >>75<<3
The corresponding secondary excitation functions are
H (3) = T [ H (7) ]
1 2 j
H (3) = h (3)T [ H (7)] + T [ H (3) ]
2 1 1 j >>75<<3 >>75<>75<>75<>75<>75<<2
These functions were plotted in Figure 11 with the
aid of the flow tables obtain when the first type of fault
was considered. Again in the cascade circuit there is only
one stable configuration for each combination of inputs,
and there are no critical races. Therefore, the order
in which the secondary variables change is not important.
The whole circuit is guaranteed to come to rest in the
proper state and give the appropriate outputs. During
the transitions between states, however, there may be
false, transient outputs.
.C.o.n.c.l.u.s.i.o.n.s
It has been demonstrated that a circuit can be con-
structed which will complement several variables using only
AND-OR logic and two inverters. There does not seem to
be any reason that this scheme cannot be extended such
that any number of inputs can be complemented using just
two inverters.
Economically, this method is highly impractical, given
present-day technology, because of the large number of
gates required to replace relatively few inverters.
It was hoped that this construction could be used
to make the maximum number of amplifiers needed to build
a sequential circuit two. This is not possible because
the two inverters do not form a cut set of the circuit.
_x
As an initial attempt to gain familiarity with th
circuits discussed her
.A.p.p.e.n.d.i.x
As an initial attempt to gain familiarity with the
circuits discussed here, a computor program which simu-
lates the N=4 case was written for the Digital Equip-
ment Corporation PDP-1 computor. The results obtained
were inconclusive due to the restrictions on the delay
of the elements. However >>75<<, the central part of the pro-
gram may be useful to others and therefore it will be dis-
cussed briefly.
A typical simulation consists of two parts, SMAT
and the circuit description. SMAT itself is a collection
of macroinstructions that define a convenient language,
while the circuit description makes use of this language.
The instructions are listed below.
save A and recall A These instructions are used for
remembering variables and simu-
lating delays.
complement A This complements is indicated
variable.
ortogether A,B,C,D >>75<>75<<>>75<<>>75<<>>75<<>>75<<>>75<<>>75<< one.
readyor and readyxor A logical zero is put in the ac.
greater N,A,B,C,D Produces a 1 if greater than
>>75<