minimum number of NAND and NOR gates

Question

Is there any systematic approach to find the minimum number of two input NAND gates and two input NOR gates to be used to impelement a binary expression?

If there then please elaborate it for the function Y = A'B+B'C+CD' .

Answer 1

Step 1.

Check if the expression is minimized using K-Map. If it isn't minimized minimize it.(If we're trying to find minimum no. of NAND Gates obtain SOP form, else obtain POS form).

In this particular Example, the expression is already minimized.

Step 2.
We try to realize the expression using only AND and NOT by applying Demorgan's Law.

A'B+CD'+B'C

=C(B'+D')+A'B

=C(BD)'+A'B

=((C(BD)')'.(A'B)')'

So number of NAND Gates=1 [for (BD)'] + 1 [for (C(BD)')'] + 1 [for (A'B)'] + 1 [for ((C(BD)')'.(A'B)')'] + 1 [for A']=5

For number of NOR Gates the procedure is same, but instead of trying to realize the minimized expression (in case of NOR Gates which should be in POS form) using only AND and NOT we try to realize it only using OR and NOT.

Comments

I am not saying to expand the minimized expression, I am just saying to minimize the number of NAND gates required to perform complementation. For example, in the case of XOR, after performing double complementation, as you pointed out, we will require 5 NAND gates if we consider the expression directly.

2 NAND gates for A' and B' explicitly, but we can work around this problem by trying to avoid using A' and B' and to use (AB)', which brings down the total number of gates to 4.

actually, I think it depends on expression to expression, in the particular case of XOR the case is such that we can work around that, but not so much, for every other case.

---

Well, this is quite good method , some exceptions can be removed by analyzing...

thanx for your time :)

---

No problem at all. Hope it helps.

Answer 2

No, there is not a systematic algorithm to approach this problem as it is

 

“NP-HARD”

So, there are only approximate methods, two of which I know are:

1. SOP / POS one, followed by bubbling of gates concept.
2. Apply double complement of given expression and try to proceed by de-morgan’s law.

 

Approach:   NOR

1. Write minimized POS expression (see that there be only 2 literals in each SUM TERM!
2. Now each SUM TERM is realized by OR GATE
3. the product of each SUM TERM IS DONE by AND GATE
4. CHANGE each OR to NOR and AND to BUBBLED AND (NOR)
5. Change each GATE TO NOR GATE, you will see the functionality remains same!

NOW notice that : BUBBLED AND is NOR GATE.

OR followed by AND  IS exactly same as NOR followed by BUBBLED AND (NOR).

6. As a safe -side relaize it by purely OR and NOT  (DEMORGAN’S )

 

 

Plus a tip: If you are getting answer, more than the no. of literals in POS or SOP, recheck. And 5 is mostly wrong option 😅

Answer 3

Firstly there is no systematic approach to find the minimum number of Gates required, you have to be efficient in utilising the boolean algebra laws.

And one thing you can observe that for SOP implementation AND-OR implementation is used which is same as NAND-NAND implementation.

Now in the given function, f=a'b+ b'c+ cd'.

You can take c common from 2nd, 3rd term to get c(b'+d').

Again notice that b'+d' =(bd)' [by de-Morgans law]

Thus your given expression becomes f=a'b+ c(bd)'.

Now,

a' will take 1 NAND Gate.

feed a'b into 1 NAND gate. ---(1)

(bd)' will take 1 NAND gate.

Feed c(bd)' into 1 NAND gate.-----(2)

Lastly, feed  (1),(2) into 1 more NAND gate to obtain f.

Finally the minimum number of NAND gates require: 5