Xref: utzoo sci.math:5767 rec.puzzles:2874 comp.lsi:648 sci.electronics:5263
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!apple!vsi1!wyse!mips!mark
From: mark@mips.COM (Mark G. Johnson)
Newsgroups: sci.math,rec.puzzles,comp.lsi,sci.electronics
Subject: The 3 inverter problem
Message-ID: <13619@obiwan.mips.COM>
Date: 21 Feb 89 02:08:50 GMT
Reply-To: mark@mips.COM (Mark G. Johnson)
Organization: MIPS Computer Systems, Sunnyvale, CA
Lines: 71

In article <1750003@hprnd.HP.COM>, clw@hprnd.HP.COM (Carl Wuebker) writes

 $    Given two inverters and as many AND and OR gates as you need, synthesize
 $    the function F:
 $
 $                           -----------
 $                   A ---> |         | ----> NOT A
 $                          |         |
 $                   B ---> |    F    | ----> NOT B
 $                          |         |
 $                   C ---> |         | ----> NOT C
 $                          -----------
 $
 $     which is usually implemented simply with 3 inverters...
 $
 $     Oh, by the way -- I've lost the solution.  Please don't email me asking
 $     for it -- it might take me days to solve!
 $
 $ Carl Wuebker * clw@hprnd * HP Roseville Networks Division * (916) 785-4296
 $

This appeared quite a while ago -- 1968.   The published paper begins:
"An interesting problem which has recently been making the rounds among
switching theorists is that of synthesizing the circuit [above] using
just __two__ inverters".

The author goes on to say that _any_ multiple-output combinational function
block of  n  input variables can be synthesized using ceil( log2(n+1) )
inverters (!!).   So, for example, it's possible to invert 100 variables
using just 7 inverters.  "This dramatic reduction in the number of inverters
is achieved only through an extremely generous use of AND/OR logic".

Reference:	Sheldon B. Akers, "On Maximum Inversion with Minimum
		Inverters", IEEE Transactions on Computers, vol. C-17,
		no. 2, pp. 134-135, February 1968.   {warning: the
		discussion in the paper makes use of Threshold Logic to
		simplify the figures}

The canonical solution to the 3-inverter problem uses 12 AND gates, 9 OR
gates, and 2 inverters.   However, a couple of related questions remain, at
least to me :-), unanswered:

(1)	Construct a 3-inversions-from-2-inverters circuit.  Assume
	that each AND, OR, and INVERT gate has a delay of one unit.
	Hook up the three inversions as a ring oscillator.  (There are
	two such ways to do this: {A2, B3, C1}, {A3, B1, C2}).  Under
	the asssumption of inertial, unit delays, does either circuit
	configuration oscillate?   Can it be made to oscillate by
	adding arbitrarily many 1-input-OR-gates (i.e. unit delays)
	in certain branches?

(2)	Hook up two of the three "inveters" back-to-back as a flipflop.
	(There are three ways to do so).  This flipflop should NOT oscillate
	because, theoretically, it contains an even number of inversions.
	{I guess you also get to state whether the third input is hooked
	to logic-1 or to logic-0}.  Do any of the 3 configurations oscillate?
	How about if you add unit delays to certain paths?

(3)	Hook up one of the three "inverters" with its output connected to
	its input.  Connect the other two inputs to whichever logic state
	you desire.  Does this single-inverter circuit oscillate?  How
	about if you add unit delays?

(4)	Construct 3 boxes, each of which implements three-inversions-from-
	-2-inverters.  Wire them up in series, with the 3 outputs of the first
	box connected to the 3 inputs of the 2nd box, etc.   Does any part
	of this configuration oscillate?
-- 
 -- Mark Johnson	
 	MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
	...!decwrl!mips!mark	(408) 991-0208