GATE 2017 CS (CS1) – Question 31
Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0.
[Karnaugh map with columns $ba$ = 00, 01, 11, 10 and rows $dc$ = 00, 01, 11, 10. The cells with 1 are ($dc$ = 01, $ba$ = 00), ($dc$ = 11, $ba$ = 00) and ($dc$ = 11, $ba$ = 10). The cells with X are ($dc$ = 00, $ba$ = 01), ($dc$ = 00, $ba$ = 11), ($dc$ = 01, $ba$ = 10), ($dc$ = 10, $ba$ = 01) and ($dc$ = 10, $ba$ = 11).]
Assume for all inputs $(a, b, c, d)$, the respective complements $(\bar{a}, \bar{b}, \bar{c}, \bar{d})$ are also available. The above logic is implemented using 2-input NOR gates only. The minimum number of gates required is ________.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1
Explanation
Read the 1-cells from the map. The columns are $ba$ and the rows are $dc$, so a cell is written $(d,c,b,a)$:
- $(dc=01,\ ba=00)$: $d=0,c=1,b=0,a=0$
- $(dc=11,\ ba=00)$: $d=1,c=1,b=0,a=0$
- $(dc=11,\ ba=10)$: $d=1,c=1,b=1,a=0$
All three have $c=1$ and $a=0$. The four cells with $c=1,\ a=0$ are these three 1's and the cell $(dc=01,\ ba=10)$, which is a don't-care. So the don't-care lets us use the whole block of four:
$$f=c\,\bar a.$$
Because both $a$ and $\bar c$ are available, use De Morgan's law:
$$c\,\bar a=\overline{\bar c+a}=\mathrm{NOR}(\bar c,\ a).$$
That is **one** 2-input NOR gate.