GATE 2018 EC Q.16: solution and answer

GATE 2018 · ECQ.16 · 1 mark · NAT

Consider a binary channel code in which each codeword has a fixed length of 5 bits. The Hamming distance between any pair of distinct codewords in this code is at least 2. The maximum number of codewords such a code can contain is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum number of codewords is 16.

Official answer: 16Source: Official answer key, GATE 2018 EC (IIT Guwahati)

We need the largest binary code of length $n = 5$ with minimum Hamming distance $d_{m i n} \geq 2$ .
Upper bound: delete the last bit of every codeword. Two distinct codewords differ in at least 2 positions, so after deleting one position they still differ in at least $2 - 1 = 1$ position. The shortened 4-bit words are therefore all distinct.
There are only $2^{4} = 16$ binary words of length 4, so the number of codewords satisfies $M \leq 16$ .
Achievability: take all 5-bit words of even weight (the single parity-check code). Two different even-weight words differ in an even number of positions, and in at least one, so in at least 2. Hence $d_{m i n} \geq 2$ .
The number of even-weight words of length 5 is $(0 5) + (2 5) + (4 5) = 1 + 10 + 5 = 16$ .
The upper bound is met, so the maximum number of codewords is $2^{n - 1} = 2^{4} = 16$ .

KEY IDEA

A minimum distance of 2 means the code detects single-bit errors. Deleting one coordinate keeps all codewords distinct, so the size is at most $2^{n - 1}$ , and the even-parity code reaches that bound.

WATCH OUT FOR

Using the Hamming bound or the Singleton bound incorrectly, or picking 32 because 5 bits give 32 words. Distance 2 forbids two codewords from differing in only one bit, so only half the words can be used.

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

GATE 2018 EC Q.16: solution and answer

Answer and solution

More Error control questions