GATE 2025 EC Q.33: solution and answer

GATE 2025 · ECQ.33 · 1 mark · NAT

The generator matrix of a (6,3) binary linear block code is given by G = [[1,0,0,1,0,1],[0,1,0,0,1,1],[0,0,1,1,1,0]]. The minimum Hamming distance d_min between codewords equals _____ (answer in integer).

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$d_{min} = 3$

Official answer: 3Source: Official answer key, GATE 2025 EC (IIT Roorkee)

For a linear block code the minimum Hamming distance equals the minimum weight of a nonzero codeword, because the distance between two codewords is the weight of their sum, and that sum is itself a codeword. The code has $2^{3} = 8$ codewords, so there are 7 nonzero ones to check.
The rows of $G$ , with all arithmetic over GF(2), are $g_{1} = 100101$ , $g_{2} = 010011$ , $g_{3} = 001110$ .
Single-row codewords: $w (g_{1}) = 3$ , $w (g_{2}) = 3$ , $w (g_{3}) = 3$ .
Sums of two rows: $g_{1} \oplus g_{2} = 110110$ with weight $4$ ; $g_{1} \oplus g_{3} = 101011$ with weight $4$ ; $g_{2} \oplus g_{3} = 011101$ with weight $4$ .
Sum of all three rows: $g_{1} \oplus g_{2} \oplus g_{3} = 110110 \oplus 001110 = 111000$ with weight $3$ .
The weights of the seven nonzero codewords are $3, 3, 3, 4, 4, 4, 3$ , so the smallest is $3$ .
Hence $d_{min} = 3$ .

KEY IDEA

In a linear block code, $d_{min}$ is the minimum weight among the nonzero codewords. Enumerate the $2^{k} - 1$ nonzero combinations of the rows of $G$ over GF(2).

WATCH OUT FOR

Checking only the rows of $G$ (all weight 3) and not the sums of rows. The sums can have a lower weight, so every combination must be checked. Here the three-row sum happens to have weight 3 again, so the answer stays 3. A second mistake is adding rows with ordinary arithmetic instead of mod 2.

From the GATE 2025 EC paper. Every question of this paper · Download the full paper · All 5 Error control questions, with notes

GATE 2025 EC Q.33: solution and answer

Answer and solution

More Error control questions