GATE CS 2004 Q58 — Combinational Circuits

To find the minimum number of gates required, let the 4-bit input representing the decimal digits $0$ to $9$ be $A, B, C, D$ (where $A$ is the MSB and $D$ is the LSB).

Since the input represents a decimal digit, the values from $10$ to $15$ ($1010$ to $1111$) do not occur and are treated as don't care conditions ($d$).

The output $Y$ must be $1$ if the digit is $\ge 5$ (i.e., $5, 6, 7, 8, 9$).

1. K-Map Simplification

We map the minterms and don't cares onto a 4-variable K-map:

• Minterms ($m$): $5, 6, 7, 8, 9$
• Don't cares ($d$): $10, 11, 12, 13, 14, 15$

From the K-map, we can form the following groups:

1. An 8-cell group combining rows $11$ and $10$: $\text{Term} = A$
2. A 4-cell group covering cells $(5, 7, 13, 15)$: $\text{Term} = BD$
3. A 4-cell group covering cells $(6, 7, 14, 15)$: $\text{Term} = BC$

Thus, the simplified Boolean expression is: $$Y = A + BD + BC$$ Factoring out $B$ gives: $$Y = A + B(C + D)$$

2. Gate Count Analysis

We can implement the expression $Y = A + B(C + D)$ using the following gates:

1. One 2-input OR gate to compute $G_1 = C + D$.
2. One 2-input AND gate to compute $G_2 = B \cdot G_1$.
3. One 2-input OR gate to compute $Y = A + G_2$.

No $\text{NOT}$ gates are required since all variables are in their uncomplemented forms.

Therefore, the minimum number of gates required is $3$.