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?
Best Answer
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.