GATE 2022 EC Q.62: solution and answer

GATE 2022 · ECQ.62 · 2 marks · NAT

Consider communication over a memoryless binary symmetric channel using a (7, 4) Hamming code. Each transmitted bit is received correctly with probability $(1 - ϵ)$ , and flipped with probability $ϵ$ . For each codeword transmission, the receiver performs minimum Hamming distance decoding, and correctly decodes the message bits if and only if the channel introduces at most one bit error. For $ϵ = 0.1$ , the probability that a transmitted codeword is decoded correctly is ________ (rounded off to two decimal places).

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The probability that a codeword is decoded correctly is about 0.85.

Official answer: 0.84 to 0.86Source: Official answer key, GATE 2022 EC (IIT Kharagpur)

A $(7, 4)$ Hamming code has $d_{m i n} = 3$ , so minimum-distance decoding corrects every pattern of at most one bit error. The question states that the message is decoded correctly if and only if the channel introduces at most one error in the 7 transmitted bits.
The channel is memoryless, so the 7 bit flips are independent, each with probability $ϵ$ . The number of errors $k$ in a codeword is binomial: $P (k) = (k 7) ϵ^{k} (1 - ϵ)^{7 - k}$ .
$P_{correct} = P (0) + P (1) = (1 - ϵ)^{7} + 7 ϵ (1 - ϵ)^{6}$
For $ϵ = 0.1$ : $P (0) = 0. 9^{7} = 0.478297$ .
$P (1) = 7 (0.1) (0.9)^{6} = 0.7 \times 0.531441 = 0.372009$ .
$P_{correct} = 0.478297 + 0.372009 = 0.850306 \approx 0.85$

KEY IDEA

Decoding is correct exactly when the block has 0 or 1 bit errors, so add the first two terms of a Binomial(7, 0.1) distribution.

WATCH OUT FOR

Keeping only the no-error term $(0.9)^{7} \approx 0.48$ and forgetting that the Hamming code also corrects every single-bit error. Another slip is using $(1 7)$ without the factor $(1 - ϵ)^{6}$ for the six correct bits.

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

GATE 2022 EC Q.62: solution and answer

Answer and solution

More Error control questions