How to minimize the gates in implementation?

Question

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?

Answer 1

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.

Answer 2

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)')'

^{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