Electrical – Minimum number of NAND gates required to realize EXOR function

nand

While trying to minimize the number of NAND gates for realizing EXOR function,
\$A\overline{B} \ \cup \ \overline{A} B\$,
I used De Morgan's & got the expression
\$\overline{\overline{\left ( A\overline{B} \right )}\cdot \overline{\left ( \overline{A} B \right )}}\$
and hence ended up with \$5\$ NAND Gates.
But my book shows it can be done with \$4\$ Gates only.
What should be a good approach towards this minimization problem?
Should I avoid using De Morgan's Law here?

Best Answer

The 4-gate implementation of the XOR function requires the output of one of the gates to be used twice. As far as I know, there's no direct algorithmic way to come up with such solutions; they must be "discovered".

In a sense, you have to "de-optimize" the solution before optimizing it, and knowing what deoptimization step makes sense is a matter of intuition. In this case, it requires the observation* that

$$A\cdot\overline{B} = A\cdot\overline{(A\cdot B)}$$

and

$$\overline{A}\cdot B = \overline{(A\cdot B)}\cdot B$$

and then realizing that the \$\overline{(A\cdot B)}\$ term for both right-hand expressions can be generated by the same gate.

*The details:

Since \$A\cdot\overline{A} = 0\$, you can add this term to any expression without changing it:

$$A\cdot\overline{B} = A\cdot\overline{A} + A\cdot\overline{B}$$

Now, factor out the A

$$\ldots = A\cdot(\overline{A} + \overline{B})$$

and apply DeMorgan's:

$$\ldots = A\cdot\overline{(A\cdot B)}$$

Related Topic