Author |
Topic: CS:XOR FROM NAND (Read 11352 times) |
|
Bl@ke
Guest
|
Assuming that there are two inputs and no other constant inputs, you can create an XOR gate using NAND gates by:
C = (A NAND B)
D = (C NAND C) NAND C
XOR = ((A NAND D) NAND B) NAND ((B NAND D) NAND A)
...or ...
((A NAND (((A NAND B) NAND (A NAND B)) NAND (A NAND B))) NAND B) NAND ((B NAND (((A NAND B) NAND (A NAND B)) NAND (A NAND B))) NAND A)
Testing the NAND gates
==============================================
A = 0
B = 0
C = (A NAND B)
=> (0 NAND 0)
=> 1
D = (C NAND C) NAND C
=> (1 NAND 1) NAND 1
=> 0 NAND 1
=> 1
XOR = ((A NAND D) NAND B) NAND ((B NAND D) NAND A)
=> ((0 NAND 1) NAND 0) NAND ((0 NAND 1) NAND 0)
=> ((1) NAND 0) NAND ((1) NAND 0)
=> (1 NAND 1)
=> 0
==============================================
A = 0
B = 1
C = (A NAND B)
=> (0 NAND 1)
=> 1
D = (C NAND C) NAND C
=> (1 NAND 1) NAND 1
=> 0 NAND 1
=> 1
XOR = ((A NAND D) NAND B) NAND ((B NAND D) NAND A)
=> ((0 NAND 1) NAND 1) NAND ((1 NAND 1) NAND 0)
=> ((1) NAND 1) NAND ((0) NAND 0)
=> (0 NAND 0)
=> 1
==============================================
A = 1
B = 0
C = (A NAND B)
=> (1 NAND 0)
=> 1
D = (C NAND C) NAND C
=> (1 NAND 1) NAND 1
=> 0 NAND 1
=> 1
XOR = ((A NAND D) NAND B) NAND ((B NAND D) NAND A)
=> ((1 NAND 1) NAND 0) NAND ((0 NAND 1) NAND 1)
=> ((0) NAND 0) NAND ((1) NAND 1)
=> (1 NAND 0)
=> 1
==============================================
A = 1
B = 1
C = (A NAND B)
=> (1 NAND 1)
=> 0
D = (C NAND C) NAND C
=> (0 NAND 0) NAND 0
=> 1 NAND 0
=> 1
XOR = ((A NAND D) NAND B) NAND ((B NAND D) NAND A)
=> ((1 NAND 1) NAND 1) NAND ((1 NAND 1) NAND 1)
=> ((0) NAND 1) NAND ((0) NAND 1)
=> (1 NAND 1)
=> 0
==============================================
|
|
 IP Logged |
|
|
|
Ryan
Guest
|
15 NAND gates? Good lord...I don't think so.
This can be done in 5 quite easily, if you go through a better design approach.
Start with the truth table for an XOR gate:
A B | Z
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
Now write that in boolean AND-OR form for the 1s (since we are designing with NAND gates):
(/A * B) + (A * /B)
Apply a double negation to the above expression, thus not changing it:
// { (/A * B) + (A * /B) }
Apply DeMorgan's theorem with one of the negations across the OR:
/ { / (/A * B) * / (A * /B) }
Now the entire expression is in term of NANDs. Inversion is easily achieved by feeding the value to both inputs of a NAND gate. This gives 3 layers of logic.
Layer 1 (inversion only):
A NAND A = /A
B NAND B = /B
Layer 2 (logic inside parentheses):
/A NAND B = C (placeholder)
A NAND /B = D (placeholder)
Layer 3 (final logic):
C NAND D = Z, which is the output
That's how a computer ENGINEER designs an XOR gate from NAND gates.
|
|
IP Logged |
|
|
|
imAtWork
Guest
|
Hey Bl@ke, what school do you come from?
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
 |
Re: CS:XOR FROM NAND
« Reply #3 on: Jul 30th, 2002, 11:43am » |
 Quote  Modify
|
Whats weird about this is that Bloke had the obvious 5 gate solution except for this really bizarre C, D business.
C is only used to form D, and
D = (C NAND C) NAND C = /C NAND C = 1
So, if you allow 1 input NANDs then just go through and trim D out of everything, otherwise replace it with 1 or with whatever variable is on the other side of the NAND.
|
|
IP Logged |
|
|
|
Ryan
Guest
|
I wasn't trying to be an ass by that last comment. My point was that this type of question is very typical of design I've done as a computer engineer....it doesn't strike me as a computer science question. I imagine many CSC people have never worked at the level of truth tables and individual gates. I can image how this could be tricky if you came at it from a purely logical and abstract standpoint, which he did.
|
|
IP Logged |
|
|
|
AFamiliarFace
Guest
|
I can name that XOR gate in four NAND gates:
!(AB) represents A NAND B
A B | C = !(AB) | D = !(CA) | E = !(CB) | XOR = !(DE)
0 0 | 1 | 1 | 1 | 0
0 1 | 1 | 1 | 0 | 1
1 0 | 1 | 0 | 1 | 1
1 1 | 0 | 1 | 1 | 0
I'm also a CS guy and arrived at this one by playing with the truth tables. I figured !(AB) was a good way to start, then permuted its output with A and B. I was going to keep combining stuff until I recognized two inputs that would leed to the answer. Luckily it was sooner instead of later.
|
|
IP Logged |
|
|
|
Ryan
Guest
|
In your workthrough
D = /A NAND B
E = A NAND /B
And then that goes into the final NAND....looks good. Nice optimization. I figured there was a way to consolidate the inversion and the first NAND level....I see I must act quicker around here.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: CS:XOR FROM NAND
« Reply #7 on: Jul 31st, 2002, 11:44pm » |
Quote Modify
|
Oops. I was so amused by bl@ke's response that I didn't check Ryan's solution. Yea, this is a standard textbook logic circuit.
Here's an exercise a colleague of mine suggested: reduce Bl@ke's solution to the optimal 5 gate implementation using only Boolean algebra. All those parentheses are making his eyes hurt.
Sorry, I guess I'm being kinda mean. Heehee.
|
| « Last Edit: Aug 1st, 2002, 1:12am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
BobTheGreat
Guest
|
Forgive me if I'm wrong, but when you say "optimal 5 gate solution..." And I look at that image and only see 4 gates.... maybe I'm losing my mind.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove