For any binary \((n, h)\) linear code with minimum distance \((2t+1)\) or…
2017
For any binary \((n, h)\) linear code with minimum distance \((2t+1)\) or greater \(n-h \geq \log_2 \bigg[ \sum \limits_{i=0}^{\alpha} \begin{pmatrix} n \\ i \end{pmatrix} \bigg]\) where α is :
- A.
\(2t+1\) - B.
\(t+1\) - C.
\(t−1\) - D.
\(t\)
Attempted by 319 students.
Show answer & explanation
Correct answer: D
Answer: α = t
Reasoning:
A code with minimum distance d = 2t+1 can correct up to t errors (because floor((d−1)/2) = t).
The sphere-packing (Hamming) bound requires that the total number of distinct error patterns within the correctable radius does not exceed the number of syndromes: 2^{n−h} ≥ Σ_{i=0}^{α} C(n,i).
Since the code corrects all error patterns of weight up to t, the sum must run up to t. Therefore α = t.
Common pitfalls:
Choosing 2t+1 confuses the minimum distance with the maximum error weight included in the Hamming bound sum.
Choosing t+1 would require a larger minimum distance (2t+3) to guarantee correction of t+1 errors, which is not given.
Choosing t−1 underestimates the error-correcting capability implied by distance 2t+1.