GATE CS 2003 Q45 — Minimization (K-Maps etc.)

The Karnaugh map given in the question has the following cell values (with rows representing $AB$ and columns representing $CD$):

1. Sum-of-Products (SOP) Minimization:
We group the $1$s using the don't cares ($X$):

• Quad 1: Cells $(5, 7, 13, 15) ightarrow BD$ (2 literals)
• Quad 2: Cells $(6, 7, 14, 15) ightarrow BC$ (2 literals)
• Pair 1: Cells $(1, 5) ightarrow A'C'D$ (3 literals)
• Pair 2: Cells $(12, 13) ightarrow ABC'$ (3 literals)

$$ext{SOP} = BD + BC + A'C'D + ABC'$$

Total SOP literal count = $2 + 2 + 3 + 3 = 10$.

2. Product-of-Sums (POS) Minimization:
We group the $0$s using the don't cares ($X$):

• Quad 1: Cells $(8, 9, 10, 11) ightarrow (A' + B)$ (2 literals)
• Quad 2: Cells $(2, 3, 10, 11) ightarrow (B + C')$ (2 literals)
• Quad 3 (Corners): Cells $(0, 2, 8, 10) ightarrow (B + D)$ (2 literals)
• Pair 1: Cells $(0, 4) ightarrow (A + C + D)$ (3 literals)

$$ext{POS} = (A' + B)(B + C')(B + D)(A + C + D)$$

Total POS literal count = $2 + 2 + 2 + 3 = 9$.

Thus, the minimum literal counts for POS and SOP are $9$ and $10$ respectively.