Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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} $$"

Please help me solve this question.

share|improve this question
    
Any suggestion is appreciated –  Math Geek Jan 10 '13 at 19:59
    
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. Also, many find the use of imperative ("Prove", "Show", etc.) to be rude when asking for help; please consider rewriting your post. –  TMM Jan 10 '13 at 20:08
    
@TMM 5 : so i have a really rude teacher...i changed the question BTW.thanks for tips –  Math Geek Jan 10 '13 at 20:15
2  
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

1 Answer 1

Completing the hint by Dilip Sarwate to an answer.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.