GATE 2022 IN Q.48: solution and answer

Official answer: BSource: Official answer key, GATE 2022 IN (IIT Kharagpur)

1. Complement is written with $\overline{}$. List the pairs with $A>B$, in decimal $(A,B)$: $(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)$. These are the 6 minterms of $F(a_1,a_0,b_1,b_0)$.

2. Comparator logic, MSB first: $A>B$ if $a_1>b_1$, or if $a_1=b_1$ and $a_0>b_0$. $$F=a_1{\overline{b}}_1+(a_1\odot b_1)a_0{\overline{b}}_0=a_1{\overline{b}}_1+a_1{b}_1{a}_0{\overline{b}}_0+{\overline{a}}_1{\overline{b}}_1{a}_0{\overline{b}}_0$$

3. K-map grouping: $a_1{\overline{b}}_1$ ($A\in \{2,3\}$, $B\in \{0,1\}$) is a quad covering $(2,0),(2,1),(3,0),(3,1)$. Two minterms are left: $(3,2)=a_1{a}_0{b}_1{\overline{b}}_0$ and $(1,0)={\overline{a}}_1{a}_0{\overline{b}}_1{\overline{b}}_0$.

4. Make each leftover's group as large as possible. $(3,2)$ pairs with $(3,0)$ to give $a_1{a}_0{\overline{b}}_0$. $(1,0)$ pairs with $(3,0)$ to give $a_0{\overline{b}}_1{\overline{b}}_0$. Neither pair can grow: dropping any literal brings in a 0-cell such as $(1,2)$, $(2,2)$, $(3,3)$, $(0,0)$ or $(1,1)$. So both are prime implicants.

5. One group cannot cover both leftovers. The only literals they share are $a_0{\overline{b}}_0$, and that term is also 1 at $A=1,B=2$, where $F=0$. Also, $a_1{\overline{b}}_1$ is the only prime implicant covering $(2,0)$, $a_1{a}_0{\overline{b}}_0$ the only one covering $(3,2)$, and $a_0{\overline{b}}_1{\overline{b}}_0$ the only one covering $(1,0)$. All three are essential, so the minimal form is $$F=a_1{\overline{b}}_1+a_1{a}_0{\overline{b}}_0+a_0{\overline{b}}_0{\overline{b}}_1$$

6. Check the other options. (A) is 0 at $(1,0)$ because $a_1=0$ there, so it misses that minterm. (C) is 0 at $(2,0)$ and $(2,1)$ because $a_0=0$ there. In (D), the term $a_0{\overline{b}}_0{b}_1$ is 1 at $A=1,B=2$, a false 1, and (D) also misses $(1,0)$. Only (B) is correct.