5
\$\begingroup\$

I am a computer science student, and several times have been asked to implement an expression with the minimum number NAND or NOR gates. I could never get the exact procedural thinking about it and always guessed the solution sometimes leading to the wrong answer.

Can you tell me how we can we take it as a procedural problem? Or is it just practice and guess for such questions? As an example how can an XOR gate be implemented with 4 minimum NAND gates, how would I approach that question?

\$\endgroup\$
3
\$\begingroup\$

There are a few formal methods of approaching this problem and are well documented. One of them is the K-Map or the Karnaugh Maps, and the other is the Quine-McCluskey algorithm. There was another method which was quite tedious which I had learnt, unfortunately I don't remember it now.

But these two methods should serve your needs most of the time (not all). Quine-McCluskey method offers better results but is longer and iterative, but scalable. K-Map is a graphical method which is quite simple but gets tedious as the number of inputs increase.

But in all cases, they are better than plain guessing, the latter having a certain edge.

Edit: After having a minimal expression, it is usually through algebra and practice that you obtain NAND and NOR implementations. Now I've not looked beyond my text books, and hence am not aware if there are any formal procedures.

\$\endgroup\$
2
  • \$\begingroup\$ Espresso. Haven't gotten around to that one myself. \$\endgroup\$ – Ignacio Vazquez-Abrams Oct 8 '13 at 6:51
  • \$\begingroup\$ yeah i also think NAND NOR implementation or through practice only.. we can minimize procedurely for AND OR implementation.. \$\endgroup\$ – user1766481 Oct 8 '13 at 6:56
3
\$\begingroup\$

Your looking for Boolean algebra. Below are the key formulas as well as a schematic diagram (drawing out the steps can help visualize). Wikipedia goes into detail will more rules such as Monotone laws and Nonmonotone laws

Basic Rules:

  • BUF : A=(A')'=AA=A+A = A+(BB')=A(B+B')
  • NOT : A'=((A')')'
  • AND : AB=((AB)')'=(A'+B')' (AND: inverted output NAND or invented inputs NOR)
  • OR : A+B=((A+B)')'=(A'B')'(OR: inverted output NOR or invented inputs NAND)
  • XOR : A^B=A'^B'=((A^B)')'=(A^B')'=AB'+A'B=(A+B)(AB)'=((A(AB)')'(B(AB)')')'
  • XNOR : (A^B)'=((A'^B')')'=(A^B)'=A^B'=AB+(A+B)'=((AB)'(A+B))'=((A+(A+B)')'+(B+(A+B)')')'

Other Common:

  • AB+CD = ((AB)'(CD)')'
  • (A+B)(C+D) = ((A+B)'+(C+D)')'

schematic

simulate this circuit – Schematic created using CircuitLab

Method to represent XOR as four NAND gates:

A^B =       AB' +  A'B     // add forms of 0, BUF rule
    =   AA'+AB' +  A'B+BB' // factor out A and B, algebra
    =  A(A'+B') + (A'+B')B // represent (A'+B') as C :: Reminder (A'+B')=(AB)'
    =        AC + CB       // represent AC as X and CB as Y
    =         X + Y        // substitute  X+Y as (X'Y')', OR rule
    =         (X'Y')'      // restore X and Y to original values
    =      ((AC)'(CB)')'   // restore C as (AB)', equivalent to (A'+B')
    = ((A(AB)')'((AB)'B)')'// DONE, XOR as 4 NAND gates, sharing the (AB)' line

Another method to do the same:

A^B =       (A+B)(AB)'     // represent (AB)' as C
    =       (A+B)C         // Distribute C
    =         AC+BC        // represent AC as X and BC as Y
    =          X+Y         // substitute  X+Y as (X'Y')', OR rule
    =         (X'Y')'      // restore X and Y to original values
    =      ((AC)'(BC)')'   // restore C as (AB)', equivalent to (A'+B')
    = ((A(AB)')'(B(AB)')')'// DONE, XOR as 4 NAND gates, sharing the (AB)' line
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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