Author |
Topic: CS: New Problem: Three Inverters From Two (Read 11039 times) |
|
Yournamehere
Guest
|
 |
CS: New Problem: Three Inverters From Two
« on: Aug 22nd, 2002, 5:13pm » |
 Quote  Modify
 Remove
|
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).
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #1 on: Aug 22nd, 2002, 6:38pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #3 on: Aug 24th, 2002, 7:46pm » |
Quote Modify
Remove
|
on Aug 23rd, 2002, 10:09pm, 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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #4 on: Aug 25th, 2002, 10:21pm » |
Quote Modify
|
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);
}
}
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #5 on: Aug 26th, 2002, 9:52pm » |
Quote Modify
|
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.)
|
| « Last Edit: Aug 26th, 2002, 10:00pm by Jeremiah Smith » |
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #6 on: Aug 27th, 2002, 12:33am » |
Quote Modify
|
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. 
http://www.wam.umd.edu/~xdt/inverter.JPG
|
|
IP Logged |
|
|
|
CONFUSED
Guest
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #7 on: Dec 8th, 2002, 7:26pm » |
Quote Modify
Remove
|
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 ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #8 on: Dec 10th, 2002, 12:59am » |
Quote Modify
|
if a,b,c=0 then a',b',c'=0 in your solution.. so it's wrong...
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: CS: New Problem: Three Inverters From Two
« Reply #9 on: Dec 10th, 2002, 12:03pm » |
Quote Modify
|
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 log2N 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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print