0
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ It can be done by 4. But it's a weird simplification. \$\endgroup\$ Jan 9, 2016 at 21:19
  • \$\begingroup\$ Can we reduce 5 gate circuit to a 4 circuit directly or it requires re-simplification from scratch? \$\endgroup\$
    – Romy
    Jan 9, 2016 at 21:22
  • \$\begingroup\$ I did once derive it, and from what I remember it was a bit convoluted - I think it requires making it far less simple first but it was about 5 years ago when I studied it, so can't remember off the top of my head. \$\endgroup\$ Jan 9, 2016 at 21:51

1 Answer 1

6
\$\begingroup\$

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)}$$

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.