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
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