September 25, 2009

4 NAND Gate design of an XOR Gate

I bought a few books lately on Amazon - one of them is The Elements of Computing Systems: Building a Modern Computer from First Principles - at the end of Chapter 1 it asks you to design all the gates you're going to use starting with primitive NAND gates (but you can use gates you've already designed). I started reading the book because I wanted to more deeply understand assembly language, which I'm trying to pick up again.
In designing the gates, I think I'm taking the wrong approaches, because my designs are not as minimalist as they could be first out of the box. When I designed my OR gate, my first design used 3 NOT gates (basically one NAND gate with the inputs tied to one pin) and an AND gate (2 NAND gates). That design, when I drew it out - it was immediately obvious that I had two redundant NOT gates (as the AND gate ends with a NOT gate), showing me that the correct design is 3 NAND gates for OR.
The doubts are starting to creep in - my first attempt at XOR design came up with a non-symmetrical drawing of 6 NAND gates (based on the logic of using one OR and one NAND and ANDing the result). Looking on the web, though, 4 NAND gates are needed, not 6, and looking at my design, I still can't SEE the redundancy. I'm hoping that something will click and I'll keep staring the problem down until I really GROK where that redundancy is...perhaps I'll go redraw my original circuit symmetrically and that will help.

1 comment:

Unknown said...

Hi!
XOR(a, b) = NAND(d, e), where c = NAND(a, b), d = NAND(a, c), and e = NAND(b, c)