4
$\begingroup$

I solved bunch of questions which give some function and then ask to implement it with minimum number of gates of specific type, each having specific number inputs. I was making mistakes in all those problems by not implementing given function with minimum number of gates.

Let me give those problems one by one and explain my point.


Problem 1

What is minimum number of two input NAND gates required to implement the function:
$f=\overline A \overline C+\overline A\overline B+\overline B \overline C$

I translated the function directly to the circuit as follows:

enter image description here

Then I converted this to NAND-only implementation as follows:

enter image description here

But when I checked the answer, it was saying lesser NAND gates. So I tried something different. I solved equation as follows:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}$
$=\overline{\overline{\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}}}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

And realized that I will need seven NAND gates for following:

  • $\overline{A}$
  • $\overline{B}$
  • $\overline{C}$
  • $\overline{(\overline{A}.\overline{C})}$
  • $\overline{(\overline{A}.\overline{B})}$
  • $\overline{(\overline{B}.\overline{C})}$
  • $=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

But then I checked detailed solution and found that the solution has come up with following equation:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}\overline{C}$
$=\overline{A}.\overline{C}+\overline{B}(\overline{A}+\overline{C})$
$=\overline{A}.\overline{C}+\overline{B}\overline{(\overline{A}.\overline{C})}$
$=\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

This requires six NANDs:

  • $\overline{A}$
  • $\overline{B}$
  • $\overline{C}$
  • $\overline{(\overline{A}.\overline{C})}$ (used twice in the equation)
  • $\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}$
  • $\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

So I was wrong twice!!!


Problem 2
Another problem gave truth table of the function and asked to implement it with NOR gate. I prepared truth table for it and grouped zeroes as follows:

enter image description here

Knowing that I have to use NOR, I thought I should form product of sum equation of this and then take double negation to get NOR friendly equation. So, I formed equation for it as follows:

$f=(x+\overline y)(\overline x + y)$
$=\overline{\overline{(x+\overline y)(\overline x + y)}}$ (taking double complement)
$=\overline{\overline{(x+\overline y)}+\overline{(\overline x + y)}}$

Now this looks perfect NOR equation as thought and it requires five NORs. But when I checked the solution, I came to know that this is indeed ExNOR equation. The solution formed sum of product equation of K map:

$xy+\overline x \overline y$

and then implemented ExNOR with four NORs, something like this:

enter image description here


Doubt

I have solved many other problems. It almost always turned out that I have followed one approach and the solution followed another to further reduce the GATE count. I feel there should be some steps / methods to get idea how many minimum number of gated are required. I know this problem is NP complete. However I feel that there has to some definite patterns on k map which can lead us / give direction / provide hint to correct final answer.

Can there be any such method? trick?

$\endgroup$
2
$\begingroup$

There is no trick. There is no efficient method. The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-hard, too. That should tell you that there is no systematic approach that always works and is reasonably efficient. Instead, you will have to use heuristics and trial-and-error. For instance, you might have to try multiple methods and take the best circuit you can find among all of them.

$\endgroup$
  • $\begingroup$ hmmm....so the key is "try multiple methods" while such problem appears in the exam....? $\endgroup$ – anir Aug 18 '18 at 15:37

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.