Re: Special XOR for half-adder and full-adder

Posted by jonk on Mar 02, 2016; 5:43am
URL: http://nand2tetris-questions-and-answers-forum.52.s1.nabble.com/Special-XOR-for-half-adder-and-full-adder-tp4029600p4029604.html

Well, let me start with the reasoning behind the XOR's NAND-only structure where I'm only permitted NANDs to make an XOR, where XOR = (A)~(B) + ~(A)(B):

1)     XOR(A,B) = NAND(P,Q) = ~(P Q) = (~P) + (~Q) = (~A)(B) + (A)(~B)
2)     therefore, ~P = (~A)(B) and also ~Q = (A)(~B)
3)     but,
            ~P = (~A)(B) + (~B)(B) = (B)[(~A) + (~B)], and also
            ~Q = (A)(~B) + (A)(~A) = (A)[(~A) + (~B)]
4)     since (~A) + (~B) = NAND(A,B), things get real easy.

        XOR(A,B) = NAND(NAND(B,NAND(A,B)),NAND(A,NAND(A,B)))

So only four NANDs are required.

The above logic required the addition of (A)(~A) in one case and (B)(~B) in the other in order to "discover" the simplifying approach. This doesn't fall out of the usual K-map or Quine-McCluskey methods, both of which equally suggest using five NAND gates. It simply takes creativity, it seems, to apply (A)(~A) and (B)(~B) in order to "find" a possible simplification using NAND gates.

If you know of any software which will automatically find this, let me know. I haven't seen any yet.

The other wonderful aspect of this is, unlike the more obvious case where five NANDs are used with two of them as inverters, the NAND(A,B) output also works nicely as a NOT CARRY value. So a single XOR provides both a SUM and a NOT CARRY output, while at the same time using four gates instead of five.

Nice.

Now to the NOR case. Using four in the same topology I get:

  F = ~(~[B + ~(A + B)] + ~[A + ~(A + B)])
  F = [B + ~(A + B)] [A + ~(A + B)]
  F = [B + (~A)(~B)] [A + (~A)(~B)]
  F = (A)(B) + (~A)(~B)(A) + (~A)(~B)(B) + (~A)(~B)(~A)(~B)
  F = (A)(B) + (~A)(~B)

So the output is as if I had F = XNOR(A,B).

Too bad I don't have any NOR gates since this is a NAND class!

For all nine gates as NORs, I get the same output -- a full adder!

Jon