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<<m	     m         m                    m

that operates on N binary arguments and has the value
"1" if  m  or more of its arguments have the value  1.
S (N)  is similar, except that it requires exactly  m

 m
of its  N  arguments to be  1  in order that the func-
tion be 1.  Figure 1 shows a graphic comparison of these
functions.  In context the actual circuit variables on
which these functions operate will always be clear even 
though they will usually not be written explicitly.
     The only other functions which will be used are
subscripted  H's  and  h's.  These have meaning which
will be explained in the analysis.
     Since the circuits of interest are composed of
similar "levels," a number in parentheses after a vari-
able or function will designate the level to which
that variable or function pertains.  Examples of this
are  x (5), H (3), .S (7), and T (127).  This does not

	3               3      1      0          4

comflict with the notation for the symmetric and thres-
hold functions discussed above because  T's  and  S's
operate (or appear to do so) on the inputs to a given
level, and a level is specified by the number of inputs
which it has.  Thus the number serves a dual purpose.

.T.h.e .B.a.s.i.c .C.i.r.c.u.i.t
     The formulation prosented here is based on a 
specific circuit encountered by the author in a course
                  
                                            
given by  Professor D.A. Huffman in the fall of 1962
at the Massachusetts Institute of Technology.  (The
person who originally devised this circuit is not
known.)  This circuit has the property that it will
complement  N  binary variables using only AND-OR
logic and  log
2

 N  (the next integer greater than
this) inverters.
     The general canonical form for this circuit is
shown in Figure 2.  The inputs x
1
 through  x
	N
  come
into the circuit on the right and go to a block of
logic which produces the threshold functions  T
1
(N),
T
2
(N),..., T
N
(N).  Note that this requires only AND-
OR logic and no inverters.  From the  T
i
(N) signals
another set  of functions  H
j
(N),  j = 1,2,...,L ,
where L  is the integer next greater than  log
2
 N,
are generated.  The  H
j
(N)  signals have the inter-
esting property that, if these signals are interp-
reted as a binary number of the form  H H H ...H ,

                                       1 2 3    L

this number will be exactly the number of inputs which
have the value  1.  By a process to be discussed later
the  H
j
(N)  are complemented by  L  inverters (on the
left side of the page) and returned to the circuit
labeled  h
j
(N).
     The method used to generate the  H
j
(N) is of par-
ticular importance in some of the work which follows.
Therefore it will be investigated more thoroughly.  On
any level  N,  H

1
(N)  is simply one of the threshold 
functions.  H
2
(N) is generated from a knowledge of
                           
                                                  
h
1
(N)  [ = .H
1
]  and the threshold functions.  Likewise
H
3
(N)  is the output of another block of combinational
logic which has as inputs  h
1
(N), h
2
(N), and the thres-
hold functions  T
i
(N).  In a similar manner any  H
j
(N)
is produced by AND-OR logic from a knowledge of  T
i
(N)
and  h
k
(N) with  k = 1,2,...,(j - 1).  This is shown in
Figure 2.
     Once the  h
j
(N) are obtained they may be combined
with the  T
i
(N) to form the pure symmetric functions
S
m
(N).  The outputs  z
i
(N)  are produced from a know-
ledge of the inputs  x
i
(N)  and the  S
m
(N).
     As an example the   N = 3  case is presented.  One
expects this to require  L = log
2
 N  = 2 inverters. The
steps are as follows (Refer to Figure 3.)_.

(1)	Generate the threshold functions  T
i
(N).
		T (3) = x (3) + x (3) + x (3)

		 1       1       2       3
		T (3) = x (3)x (3)+x (3)x (3)+x (3)x (3)

		 2       1    2     1    3     2    3
		T (3) = x (3)x (3)x (3)
		 3       1    2     >>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<<j
z (3) = S [H (7)]+S [H (7)][H (7)+H (7)]+S [H (7)][H (7)H (7)]

 1       0  j      1  j      2     3      2   >>75<<j      2    3
z (3) = S [H (7)]+S [H (7)][H (7)+H (7)]+S [H (7)][H (7)H (7)]

 2       0  j      1  j      1     3      2  j      1    3
z (3) = S [H (7)]+S [H (7)][H (7)+H (7)]+S [H (7)][H (7)H (7)]

 3       0   >>75<<j      1   >>75<<j      1     2      2  j      1     >>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<<These perform the indicated
andtogether A,B,C,D	    logical operationon the four
xortogether A,B,C,D	    specified arguments and the
			    result of the previous com-
			    putation.
readyand		    This loads the ac with a logical
				>>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<<N of the arguments are  1.
initialize		    This accepts inputs from the
			    typewriter and allows the cir-
			    cuit to stabilize initially.
setup		    This initializes SMAT.
cycle		    This allow the machine to cycle
			    until it stabilizes.
reserve A,B	    This tells SMAT where the symbols
			    are stored.  A is the first de-
			    fined symbol and B the last.
print A,B,C,D	    This types out the values of the
			    indicated variables.  Additional
			    characters rtn and spc provide for
			    carriage return and space.

     There are presently four primary inputs.  More can be
added by modifing the subroutine  sup.
     The address tags shown in the circuit description are
necessary and must be placed where they are shown.  Other
than this the program follows standard MACRO format.
     The output is a listing of the values of the arguments
of the print statements.  If the current value of a vari-
able is the same as its last value, it will be typed in
black.  If not, it will be shown in red.