Digital Logic

Question

To design n input NOR gate, the number of 2  input NOR gate =2n - 3.

 

 

 

Somebody please verify and explain with example ( diagram).

Comments

The result is based on a recurrence.

First I am showing you the example for understanding and then prove it.

Suppose, you have to design $3$-input NOR gate. So, $n=3.$ Suppose, inputs are $A,B,C$ and So, result would be:

$\overline{A+B+C} = \overline{\overline{\overline{A+B}}+C}$

Here, $\overline{A+B}$ requires one 2-input NOR gate, Now, $\overline{\overline{A+B}}$ requires total two 2-input NOR gates (1 NOR gate from previous $\overline{A+B}$) and finally, $\overline{\overline{\overline{A+B}}+C}$ requires total threee  2-input NOR gates (2 NOR gates from previous $\overline{\overline{A+B}}$).

So, you can verify $3$ is actually $2*3-3.$

Now, Based on this, you can prove the result as:

Suppose,

 $ \overline{A_1+A_2+A_3+…+A_n} = \overline{\overline{\overline{A_1+A_2+A_3+...+A_{n-1}}}+A_n} $

Let, $T_n$ be the minimum number of two-inputs NOR gates. Then, you can write the recurrence as:

$T_n = T_{n-1} + 1 + 1$

i.e. $T_n = T_{n-1} + 2$ with $T_2 = 1$

Hence, $T_n = 2n-3$

---

Thank you

But how you written(last two line) the equation after:-

Tn = Tn-1 + 2 with T2= 1

Tn = 2n -3.

---

Let, $T_{n}$ be the number of two-input NOR gates for $\overline{A_1+A_2+A_3+...+A_{n-1}+A_n},$ So,

$T_{n-1}$ be the number of two-input NOR NOR gates for $\overline{A_1+A_2+A_3+...+A_{n-1}}$ and So,

$T_{n-1} +1 $ be the number of two-input NOR gates for $\overline{\overline{A_1+A_2+A_3+...+A_{n-1}}}$ and So,

$T_{n-1} +1 +1 $ be the number of two-input NOR gates for $\overline{\overline{\overline{(A_1+A_2+A_3+...+A_{n-1})}} + A_n}$

Since, $\overline{\overline{\overline{(A_1+A_2+A_3+...+A_{n-1})}} + A_n}$ is same as $\overline{A_1+A_2+A_3+...+A_{n-1}+A_n},$

So, $T_n = T_{n-1} + 1 + 1$

When $n=2$ then you will get one two-input NOR for $\overline{A_1 + A_2}$

So, $T_2=1,$ You could also take, $T_3=3$  (This is your base condition)

Hence, $T_n = T_{n-1} + 2$ with $T_2 = 1$

When you solve this recurrence, you will get, $T_n = 2n-3$

You can also understand all these things from the example which I have given and then generalize it.