wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: New Problem: Three Inverters From Two
        
(Message started by: Yournamehere on Aug 22^nd, 2002, 5:13pm)

Title: CS: New Problem: Three Inverters From Two
Post by Yournamehere on Aug 22^nd, 2002, 5:13pm

Here's another logic gate problem:

Construct a circuit which takes three binary inputs, a, b, c, and creates as outputs their complements, a', b', c', (NOT a, NOT b, NOT c) with the restriction that you may only use two inverters (NOT gates). You are allowed as many AND and OR gates as you wish, but no other gates, besides these and the two inverters, can be used.

A neat generalization of this problem is "how many inverters do you need to compute the complements of N inputs", but I do not know the answer to this (I don't even know if the answer is known).

Title: Re: CS: New Problem: Three Inverters From Two
Post by AlexH on Aug 22^nd, 2002, 6:38pm

I had the general case as a homework problem a few years ago. Won't spoil the solution but the formula for n bits is:

You need ceiling(log n+1) inverters to negate n bits

Title: Re: CS: New Problem: Three Inverters From Two
Post by jeremiahsmith on Aug 23^rd, 2002, 10:09pm

Did you get this from HAKMEM? :)

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item19

I first saw it there, and my brain decided to hurt for a long time afterwards. I still can't figure out the answer.

Title: Re: CS: New Problem: Three Inverters From Two
Post by Yournamehere on Aug 24^th, 2002, 7:46pm

on 08/23/02 at 22:09:53, jeremiahsmith wrote:

Did you get this from HAKMEM? :)

I first heard it from a friend, who received the puzzle in a logic design class. I've not seen another reference to the puzzle outside of HAKMEM, myself.

Title: Re: CS: New Problem: Three Inverters From Two
Post by AlexH on Aug 25^th, 2002, 10:21pm

In black below is a circuit for the 3 with 2 case. Its not the smallest possible such circuit but is written as a hint toward the more general case.

Its written in C code for easy verification.

#include <stdio.h> void main(){ int a,b,c,x,y,z,g,h,a1,b1,c1,x1,y1,z1; int i; for(i=0;i<8;i++){ // set up all possible inputs a,b,c a = i & 1; b = (i & 2) >> 1; c = (i & 4) >> 2; x = a & b & c; y = a & b | a & c | b & c; z = a | b | c; //Here are our 2 inverters g = !(y); h = !(x | g & z); x1 = g | h; y1 = g; z1 = g & h; a1 = b & c & x1 | (b | c) & y1 | z1; b1 = a & c & x1 | (a | c) & y1 | z1; c1 = b & a & x1 | (b | a) & y1 | z1; //print outputs to verify printf("%d-->%d %d-->%d %d-->%d\n",a,a1,b,b1,c,c1); } }

Title: Re: CS: New Problem: Three Inverters From Two
Post by jeremiahsmith on Aug 26^th, 2002, 9:52pm

Owwwwwwwwwwww. Thanks, Alex, you scared my brain away. :)

I'll try to root through that, and see if I can't represent all that as actual gates for the benefit of our C-illiterate readers. (And myself, because I've been wondering about this for a while. Heck, I was even considering submitting it a while ago.)

Title: Re: CS: New Problem: Three Inverters From Two
Post by jeremiahsmith on Aug 27^th, 2002, 12:33am

Okay, I drew a sketch of what -- HOPEFULLY -- is AlexH's logic gate circuit. If I screwed up, I'll have to draw it all again...grrr. Oh well. I drew it on paper and scanned it, as I wasn't about to crank this out in Paint. Anyways, inside each gate, I put the little logic expression for what it does (for example, an OR gate might say (a | b) in it, or next to it, if the expression is long), and at the bottom of the gate, I sometimes put a letter on its own (like x1, z1, etc, in AlexH's code) as a simplification of the expression.

I forgot if NOT gates are just triangles, or triangles with a little circle underneath. I did them without the circles. Forgive me. :D

http://www.wam.umd.edu/~xdt/inverter.JPG

Title: Re: CS: New Problem: Three Inverters From Two
Post by CONFUSED on Dec 8^th, 2002, 7:26pm

can't it be done using a single inverter (when we are allowed to use any number of and/or gates). goes like this.

1) x = a AND b AND c
2) y = NOT x
3) a1 = y AND b AND c
4) b1 = y AND a AND c
5) c1 = y AND a AND b

am i going wrong ?

Title: Re: CS: New Problem: Three Inverters From Two
Post by towr on Dec 10^th, 2002, 12:59am

if a,b,c=0 then a',b',c'=0 in your solution.. so it's wrong...

Title: Re: CS: New Problem: Three Inverters From Two
Post by James Fingas on Dec 10^th, 2002, 12:03pm

I have no idea how AlexH got his solution, but here's mine:

My solution for this is based on the principle of counting the number of active inputs. With the inputs A, B, and C, we will generate the following two outputs (one inverter is required for each):

X - true when zero or one of the inputs are high
Y - true when zero or two of the inputs are high

You can see that with this information, we can form an output:

A' = XY + X(B + C) + YBC
= XY + XB + XC + YBC (This is the logic I'll use to actually generate the output)

Now how do we generate X and Y? First we get X:

X = !(AB + BC + CA) (there are zero or one inputs high when there aren't two or three inputs high)

Y is a little trickier:

X = !(ABC + X(A + B + C)) (there are zero or two inputs high when there aren't one or three inputs high)

Now we execute an intermediate step of AND logic, generating the following signals: XY, XA, XB, XC, YAB, YAC, YBC.

Last, we execute a final step of OR logic, generating the results!

This method will work as long as you have at least log₂N inverters for N-1 signals you wish to invert. For instance, you could invert seven signals with three inverters. However, note that you don't actually need three inverters, since you could make three out of two.

Therefore, you can make any number of inverters out of exactly two inverters. This would actually be useful if inverters were difficult to make. Considering that the inverter is the simplest CMOS gate, this problem is not particularly helpful in the real world.

Getting seven inverters out of three:

X - zero, one, two, or three inputs are high
Y - zero, one, four, or five inputs are high
Z - zero, two, four, or six inputs are high

X = !(ABCD + ABCE + ABCF + ABCG + ABDE + ABDF + ABDG + ABEF + ABEG + ABFG + ACDE + ACDF + ACDG + ACEF + ACEG + ACFG + ADEF + ADEG + ADFG + AEFG + BCDE + BCDF + BCDG + BCEF + BCEG + BCFG + BDEF + BDEG + BDFG + BEFG + CDEF + CDEG + CDFG + CEFG)

Y = !(X(AB + AC + AD + AE + AF + AG + BC + BD + BE + BF + BG + CD + CE + CF + CG + DE + DF + DG + EF + EG + FG) + ABCDEF + ABCDEG + ABCDFG + ABCEFG + ABDEFG + ACDEFG + BCDEFG)

Z = !(XY(A + B + C + D + E + F + G) + X(ABC + ABD + ABE + ABF + ABG + ACD + ACE + ACF + ACG + ADE + ADF + ADG + AEF + AEG + AFG + BCD + BCE + BCF + BCG + BDE + BDF + BDG + BEF + BEG + BFG + CDE + CDF + CDG + CEF + CEG + CFG + DEF + DEG + DFG + EFG) + Y(ABCDE + ABCDF + ABCDG + ABCEF + ABCEG + ABCFG + ABDEF + ABDEG + ABDFG + ABEFG + ACDEF + ACDEG + ACDFG + ACEFG + ADEFG + BCDEF + BCDEG + BCDFG + BCEFG + BDEFG + CDEFG))

A' = XYZ + XY(B + C + D + E + F + G) + XZ(BC + BD + BE + BF + BG + CD + CE + CF + CG + DE + DF + DG + EF + EG + FG) + X(BCD + BCE + BCF + BCG + BDE + BDF + BDG + BEF + BEG + BFG + CDE + CDF + CDG + CEF + CEG + CFG + DEF + DEG + DFG + EFG) + YZ(BCDE + BCDF + BCDG + BCEF + BCEG + BCFG + BDEF + BDEG + BDFG + BEFG + CDEF + CDEG + CDFG + CEFG + DEFG) + Y(BCDEF + BCDEG + BCDFG + BCEFG + BDEFG + CDEFG) + Z(BCDEFG) (The other outputs, B', C', etc. are similar)

This is probably harder than the other method of making seven inverters out of three, which is to make three out of two of the three, giving four, then make six out of the four, and then make up to nine out of the six. However, it will have shallower logic, so it would likely execute faster (although with 35-input OR gates and such, I'm not going to guarantee anything).

I won't even get into how you make 127 inverters out of 7 ;) In fact, I don't think anyone in their right mind would ever try to do better than 7 inverters from 3, since the number of gates you need goes up exponentially. 15 from 4 would have 6435-input OR gates. That's perhaps a little excessive.