5

I want to show that a binary , narrow-sense BCH code of length $n=2^m-1 $ and designed distance $ \delta=2t+1 $ has minimum distance $ \delta$ , given that $ \sum_{i=0}^{t+1} \binom{2^m-1}{i}> 2^{mt} $.

We know that:

A BCH code with designed distance $ \delta $ has minimum distance at least $ \delta $.

So we have that $ d \geq \delta $.

In order to show that the minimum distance is $\delta $,we have to find a codeword with Hamming-weight $\delta $.

How can we use the given inequality in order to show the existence of such a codeword?

EDIT: Also how can we show that the distance of the code has to be odd?

Evinda
  • 1,460

1 Answers1

3

Hints:

  1. The sum $\sum_{i=0}^{t+1}\binom n i$ counts the number of points at a distance $\le t+1$ from any given point $\in\Bbb{F}_2^n$.
  2. The dimension of your BCH code is at least $n-mt$, so it has at least $2^{n-mt}$ distinct words.
  3. Compare with the derivation of the sphere packing bound.

[Added after Evinda spotted a gap] We can conclude that that minimum distance $d$ of this code is thus at most $2t+2$. But we can show that $d$ is always odd. This is because if $d$ were $2t+2$, then this would also be the minimum distance of the extended BCH code of length $n+1=2^m$. But that code has a transitive automorphism group, so it has words of minimum weight $2t+2$ such that the extended bit is also $1$. The claim follows.

Alternatively we can see this using finite field arithmetic. The existence of a word of weight $d=2t+2$ means that there exists a subset $S\subseteq \Bbb{F}_{2^m}\setminus\{0\}$ of size $|S|=d$ such that for all integers $1\le j\le 2t$ we have $$ \Sigma(S,j):=\sum_{x\in S}x^j=0. $$ Because $d$ is an even number it follows that $\Sigma(S,0)=0$ also. Let $s\in S$ be a fixed element. Let $S+s=\{x+s\mid x\in S\}$, so $0=s+s\in S+s$. The binomial formula tells us that $$ \Sigma(S+s,j)=\sum_{x\in S}(x+s)^j=\sum_{k=0}^j\binom j k s^{k-j} \Sigma(S,j)=0 $$ for all $j$ in the range $1\le j\le 2t$. This means that the set $S+s\setminus \{0\}$ is the support of a word of this BCH-code also. But it has only $2t+1$ elements.

Jyrki Lahtonen
  • 133,153
  • 1
    Then if $d$ is odd we get that $\frac{d-1}{2} \leq \frac{\delta-1}{2}$. And since $d \geq \delta$ we have that $\frac{d-1}{2} \geq \frac{\delta-1}{2}$. So we have that $d=\delta$. But how can we show that the distance of the code has to be odd? @JyrkiLahtonen – Evinda Apr 28 '16 at 17:57
  • Well spotted, @Evinda ! Sorry about missing that step. That step was a bit tricky. At least the way I did it. Does this argument look at all familiar? I hope there's a simpler one, but I couldn't come up with one :-( – Jyrki Lahtonen Apr 28 '16 at 21:28
  • Does the fact that the code has a transitive automorphism group mean that we can interchange the values of two elements? i.e. we take the codeword with the minimum weight , add a zero at the end and then interchange 0 with some 1 from an other position? Have I understood it right? @JyrkiLahtonen – Evinda Apr 28 '16 at 21:58
  • 1
    Yes, @Evinda. That's roughly the idea. But we usually need to permute many positions (such as translate the entire finite field, which is what I did in my answer). The upshot is that using an automorphism we can move one of the $1$s of an even weight word to the extended position, and get a word of the unextended code of weight one less. The other $1$s go God knows where, but we don't really care. – Jyrki Lahtonen Apr 28 '16 at 22:02
  • I understand... Thank you very much!!! I have also an other question: http://math.stackexchange.com/questions/1763384/find-minimum-distance-of-the-code @JyrkiLahtonen – Evinda Apr 28 '16 at 22:16
  • @Evinda Other users have flagged your comments like the one above (asking somebody to take a look at another question). Many view of them as mildly rude. – Jyrki Lahtonen Apr 29 '16 at 03:43