Fog Creek Software
Discussion Board




XOR gate using NAND gates

This question was actually part of an interview I had with Intel slightly over two years ago.

It's a fairly straightforward approach using boolean algebra as our guide, mainly making use
of the following boolean relations:

1. not(A . B)  = notA + notB,
2. not(notA) = A, and
3. notA . A = 0

We may then begin expanding A xor B:

(eq 1)    A xor B = (A . notB) + (notA . B)

(eq 2)    A xor B = not(not((A . notB) + (notA . B)) =
(eq 3)    not((not (A . notB) . (not(notA . B)))) =
(eq 4)    not((notA + B) . (A + notB))

Thus, (eq 4) may be representative of the output of a NAND gate with the two inputs (not A + B) and (A + notB).

In order to obtain the two terms in (eq 4) as themselves outputs of NAND gates, we may break down the terms much like the original expression in (eq 1).

(eq 5)    notA + B = not (not(notA + B)) =
(eq 6)    not(A . notB)

and

(eq 7)    A + notB = not(not(A + notB)) =
(eq 8)    not(notA . B)

Where the expressions in (eq 6) and (eq 8) may themselves
be outputs of respective NAND gates.

That's three NAND gates so far.  Only remaining question
is how to obtain the expressions in (eq 6) and (eq 8)
without using an inverter or "cheating" by connecting
NAND gates as inverters (which would be a rather awkward
and non-elegant solution).

If we expand the expressions in (eq 6) and (eq 8), we
get, respectively

(eq 9)    not(A . notB) = not((notA . A) + (A . notB)) =
(eq 10)  not(A . (notA + notB)) =
(eq 11)  not(A . (not(A . B)))

and


(eq 12)  not(notA . B) = not((notB . B) + (notA . B)) =
(eq 13)  not(B . (notB + notA)) =
(eq 14)  not(B . (not(A . B)))

As we can see from (eq 11), (eq 6) may be obtained as the output
of a nand gate whose inputs are A and not(A . B), the latter itself
being the output of a NAND gate whose inputs are A and B.
Similarly, from (eq 14), (eq 8) may be obtained as the output
of a nand gate whose inputs are B and not(A . B), the latter
again the output the NAND gate whose inputs are A and B.

Thus, by substituting (eq 11) and (eq 14) into (eq 4), we
may obtain:

A xor B = not ((not (A . (not (A . B) ) )) . (not (B . (not (A . B) ) )) )
          ^^^  ^^^      ^^^                ^^^      ^^^
        NAND4  NAND2    NAND1              NAND3    NAND1

             
That's four NAND gates in all.

Tamas Kovacs
Monday, July 12, 2004

IMO, using a '1' input isn't cheating, since the problem statement expressly noted its availability. Moreover, what seems academically elegant may or may not be physically elegant when comes time to build something.

Aesthetics aside, here's a similar solution using a (hopefully self-explanatory) notation that might be simpler to absorb:

A^B = A~B + B~A (by defiinition)
A^B = ~~[A~B + B~A ] (double inversion)
A^B = ~[~(A~B) ~(B~A) ] (DeMorgan's theorem)

This represents a pair of NAND gates driving a NAND gate output. Note: all gates are dual input. It remains to generate ~B and ~A with NAND gates.  We could tie one input 'high' ( ~B = ~(B1) ) or tie both inputs together( ~B = ~(BB) ).  If we tie inputs together to generate ~A and ~B, we get a 5-gate solution:

A^B = ~{ ~[A ~(BB)]  ~[B ~(AA)] }

where braces and brackets replace some parentheses for clarity. 

If minimum gate count is a design goal, then one gate can be eliminated as follows:

Consider the '~(A~B)' gate inputs.  When the 'A' input is 0, It doesn't matter what appears at the '~B' input; all we require is for that input resolve to ~B whenever A is 1. Math wise,

~(A~B) = ~(A~B + A~A)
(this is the math equivalent of cheating by using a '0' input to a NOR gate)
~(A~B) = ~(A (~B + ~A) )
~(A~B) = ~(A ~(BA) )

i.e., using ~(BA) instead of ~B  is preserves logical behavior.

Likewise, one can use ~(AB) in place of the ~A input to the sibling NAND.

Since ~(AB) = ~(BA), one of these NAND gates is redundant and the final equation becomes:

A^B = ~{ ~[A ~(AB)] ~[B ~(AB)] }

Personally, I find a graphical presentation using gates and bubbles easier to comprehend.

:)

Chuck Boyer
Thursday, August 05, 2004

Actually, in this case the emphasis was not on elegance per se, academic or otherwise, though it was mentioned.  It was on using only NAND gates, and as few NAND gates as possible.  Also note that "cheating" appears in quote marks, thus not to be taken literally.

In the end the solutions are the same.

I am not very good at ASCII art so I couldn't provide gates and bubbles.  I do have a .pdf file of the diagram available should anyone need it. 

Cheers!

Tamas Kovacs
Thursday, August 19, 2004

I want it plant

Marwa Aly
Monday, October 11, 2004

Please provide us the logic circuit for implementing XOR gate using NAND and NOR gate.

Senthil Murugan
Thursday, October 14, 2004

You guys are genius !!!

G
Thursday, November 04, 2004

*  Recent Topics

*  Fog Creek Home