[comp.lsi] The 3 inverter problem

mark@mips.COM (Mark G. Johnson) (02/21/89)

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

cosell@bbn.com (Bernie Cosell) (02/21/89)

In article <13619@obiwan.mips.COM> mark@mips.COM (Mark G. Johnson) writes:
}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...
}
}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 problem predates this paper by a bit, since it was given as a problem
while I was at MIT, in '66.  The thing that is amusing was [I think
Minsky's] observation about the followon conclusion -- it is clear that if
you can invert three signals with two inverters, you can invert *ANY*NUMBER*
of signals with just.... TWO inverters.  Spoiler follows....

Build the above box with two inverters.  Use two of its inputs as the inverters to build another such box, use the third input to invert one of your signals.
Continue bootstrapping more three-out-of-two boxes until you've generated
enough "spares" to invert all of your real signals....

   __
  /  )                              Bernie Cosell
 /--<  _  __  __   o _              BBN Sys & Tech, Cambridge, MA 02238
/___/_(<_/ (_/) )_(_(<_             cosell@bbn.com

jdchrist@watcgl.waterloo.edu (Dan Christensen) (02/22/89)

In article <13619@obiwan.mips.COM> mark@mips.COM (Mark G. Johnson) writes:
>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".

If this is true, then from x inverters we can make any multiple-output
combinational function of 2^x-1 input variables.

Thus 2 inverters can generate 2^2-1=3 inverters.  Then couldn't those
3 inverters generate 2^3-1=7 inverters.  And then those 7 inverters could
generate 2^7-1=127 inverters.  And so on.

So from 2 inverters we can make any multiple-output combinational function
of _any_ number of variables, right?  Or am I missing something?

----
Dan Christensen, Computer Graphics Lab,	         jdchrist@watcgl.uwaterloo.ca
University of Waterloo, Waterloo, Ont.	         jdchrist@watcgl.waterloo.edu

badri@valhalla.ee.rochester.edu (Badri Lokanathan) (02/22/89)

> In article <13619@obiwan.mips.COM> mark@mips.COM (Mark G. Johnson) writes:
> >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".
> 
In article <8216@watcgl.waterloo.edu>,
jdchrist@watcgl.waterloo.edu (Dan Christensen) writes:
> If this is true, then from x inverters we can make any multiple-output
> combinational function of 2^x-1 input variables.
> 
> Thus 2 inverters can generate 2^2-1=3 inverters.  Then couldn't those
> 3 inverters generate 2^3-1=7 inverters.  And then those 7 inverters could
> generate 2^7-1=127 inverters.  And so on.
> 
> So from 2 inverters we can make any multiple-output combinational function
> of _any_ number of variables, right?  Or am I missing something?

Yes, you forgot the extremely generous use of AND/OR logic.
In any case, from the comp.lsi viewpoint, this is really quite a useless 
exercise since in most cases, inverted logic is the norm rather than the
exception.

On a rather risque note, it is about as useful as the reusable condom
puzzle: (Hit n if you are easily offended!)

3 men want to make love to 1 woman. Here are the assumptions:
(1) There should be no direct genital contact to avoid disease transmission.
(2) There is a supply of "reusable" condoms with the restriction that
    a dirtied surface may not be used by a different person.

What is the minimum number of condoms required?
Spoiler hint:

Simultaneous use of multiple condoms.
-- 
"I care about my fellow man              {) badri@ee.rochester.edu
 Being taken for a ride,                //\\ {ames,cmcl2,columbia,cornell,
 I care that things start changing     ///\\\ garp,harvard,ll-xn,rutgers}!
 But there's no one on my side."-UB40   _||_   rochester!ur-valhalla!badri

abali@parts.eng.ohio-state.edu (Bulent Abali) (02/22/89)

In article <1827@valhalla.ee.rochester.edu> badri@valhalla.ee.rochester.edu (Badri Lokanathan) writes:
>On a rather risque note, it is about as useful as the reusable condom
>puzzle: (Hit n if you are easily offended!)

>3 men want to make love to 1 woman. Here are the assumptions:
>(1) There should be no direct genital contact to avoid disease transmission.
>(2) There is a supply of "reusable" condoms with the restriction that
>    a dirtied surface may not be used by a different person.
>
>What is the minimum number of condoms required?
>Spoiler hint:

>Simultaneous use of multiple condoms.

The solution of the "condom-puzzle" at the EE bull-pan at Ohio State:

  Two condoms A and B are used (by using 2 at the same time) :


   +-------+             +-------+             +-------+
   |       |             |*******|             |*******|
   |  +-+  |             |*     *|             |**+-+**|
   |  |*|  |             |*     *|             |**| |**|
   |  |*|  |             |*     *|             |**| |**|
   |  |*|  |             |*     *|             |**| |**|
   |  |*|  |             |*     *|             |**| |**|
   A  B                  A                     A  B
(B dirty inside)      (A dirty inside)    ( B flipped inside out)

    Man 1                  Man 2                 Man 3

                                                         Q.E.D.


How about generalizing it to m men, w women, k condoms? Followups
to rec.puzzles.

Sincerely,
B. Abali  and  R. Daoud
(researchers extraordinaire)


-=-
Bulent Abali
Ohio State Univ., Dept.of Electrical Eng.
2015 Neil Av. Columbus, Ohio 43210
abali@baloo.eng.ohio-state.edu

dik@cwi.nl (Dik T. Winter) (02/22/89)

In article <8216@watcgl.waterloo.edu> jdchrist@watcgl.waterloo.edu (Dan Christensen) writes:
 > So from 2 inverters we can make any multiple-output combinational function
 > of _any_ number of variables, right?  Or am I missing something?
 > 
Yep.  In the original problem the three inversions are independent.  In the
solutions the inversions are not independent.  That is, outputs from some
inversions are used as (part of the) input to other inversions.
-- 
dik t. winter, cwi, amsterdam, nederland
INTERNET   : dik@cwi.nl
BITNET/EARN: dik@mcvax

mark@mips.COM (Mark G. Johnson) (02/22/89)

In article <36205@bbn.COM> cosell@BBN.COM (Bernie Cosell) writes:
> ... The thing that is amusing was [I think
>Minsky's] observation about the followon conclusion -- it is clear that if
>you can invert three signals with two inverters, you can invert *ANY*NUMBER*
>of signals with just.... TWO inverters.  Spoiler follows....
>Build the above box with two inverters.  Use two of its inputs as the
>inverters to build another such box, use the third input to invert one
>of your signals.
>Continue bootstrapping more three-out-of-two boxes until you've generated
>enough "spares" to invert all of your real signals....
>

But does this form a path with feedback?  Does it accidentally produce a
latch?  an oscillator?
-- 
 -- Mark Johnson	
 	MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
	...!decwrl!mips!mark	(408) 991-0208