# Problem about narrow sense BCH-Code

I have an homework to do and i have no idea where to start. The question is:

"Show that a narrow-sense binary BCH-code of length $n=2^m-1$ and designed distance $2t+1$ has minimum distance $2t+1$, provided that $$\sum_{i=0}^{t+1}\binom{2^{m}-1}{i}>2^{mt}$$"

-
Any suggestion is appreciated – Math Geek Jan 10 '13 at 19:59
Hint: to prove $A\Rightarrow B$, you can choose to prove $\neg B \Rightarrow \neg A$. If the code does not have minimum Hamming distance $2t+1$, then its minimum Hamming distance is $2t+3$ or more, and so all error patterns of Hamming weight $t+1$ or less are correctable error patterns. The left side of the inequality is the number of binary vectors of length $2^m-1$ that have Hamming weight at most $t+1$. So..... – Dilip Sarwate Jan 11 '13 at 2:28
Continuing Dilip Sarwate's hint: ... and the number of binary check equations is $mt$ (or less, if there happen to be accidental linear dependencie*), so the number of distinct syndromes is... – Jyrki Lahtonen Jan 11 '13 at 7:52
Let $S$ be the set of all binary vectors of length $n$ and weight at most $t+1$. Then $$|S|=\sum_{i=0}^{t+1}{2^m-1\choose i}.$$ Let $H$ be the parity check matrix. If $x$ is any binary vector of length $n$, then the syndrome $Hx^T$ has $mt$ binary components. The inequality $|S|>2^{mt}$ tells us that there are (at least) two distinct vectors $x_1$ and $x_2$ in $S$ such that their syndromes are equal, i.e. $Hx_1^T=Hx_2^T$. Then $H(x_1-x_2)^T=0$, so $x_1-x_2$ is a codeword.
But $x_1-x_2$ has weight at most $2(t+1)$, so the minimum distance of this code cannot be higher than $2t+2$. But we also know (have you covered this?) that the minimum distance of a narrow sense binary BCH-code cannot be even. This follows for example from the fact extended binary BCH-codes have a transitive automorphism group (translations by an element of $GF(2^m)$). Therefore the extended BCH-code has words of minimum weight with one of the 1s at position zero. This is the position that is deleted when going back from the extended code to the unextended version.