Distance of bch code

1.2k Views Asked by At

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?

1

There are 1 best solutions below

6
On BEST ANSWER

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.