1
$\begingroup$

I want to show that the minimum distance of a narrow-sense BCH code over $\mathbb{F}_q$ with length $n$ and designed distance $\delta$ is equal to $\delta$ provided that it holds that $\delta \mid n$.

It holds that a BCH code with designed distance $\delta$ has minimum distance at least $\delta$.

So we need to show that there is a codeword with Hamming weight $\delta$.

How do we deduce the existence of such a codeword from the fact that $\delta \mid n$ ?

Can we consider that the length of the code is of the form $q^m-1$ ?

If so, then we could use the fact that a $q$-ary bch code of length $q^m-1$ with designed distance $\delta$ has dimension at least $q^m-1-m(\delta-1)$, couldn't we?

Then from the sphere packing bound and the above proposition we get that $\sum_{i=0}^{\lfloor \frac{d-1}{2} \rfloor} \binom{n}{i}(q-1)^i \leq q^{m(\delta-1)}$.

But does this help?

Or isn't the idea right?

$\endgroup$
3
2
$\begingroup$

The Peterson theorem: if $n=\delta b$, then the distance of narrow-sense BCH with designed distance $\delta$ is equal to $\delta$

Proof: Let $\alpha$ has the order $n$ and $\alpha,\alpha^2,...,\alpha^r$ is a BCH-chain for $r=\delta-1$. Not hard to see $$x^n-1=(x^b-1)(1+x^b+...+x^{rb}).$$ Since $\alpha^{ib}\ne1$ for $i=1,...,r$ then all of chain elements are roots of $h(x)=1+x^b+...+x^{rb}$. So, $h(x)$ is a word of weight $\delta$.

$\endgroup$
12
  • $\begingroup$ What do you mean with BCH-chain? $$$$ Do you mean the sequence of powers of $\alpha$ such that $c(\alpha^b)=c(\alpha^{b+1})=\dots+ c(\alpha^{b+\delta-2})=0$ if $c$ is a codeword? $\endgroup$
    – Evinda
    Apr 29 '16 at 8:13
  • $\begingroup$ I mean by "BCH-chain" the chain of elements $\alpha,\alpha^2,...,\alpha^r$ from which we construct the code. Since $h(\alpha)=h(\alpha^2)=...=h(\alpha^r)=0$ then $h(x)$ is a codeword $\endgroup$ Apr 29 '16 at 8:30
  • $\begingroup$ Is $h$ a word of weight $\delta$ since it has $\delta$ roots? $$$$ If so, we know that it holds that $$ c(x) \in C \Leftrightarrow c(\alpha^b)=c(\alpha^{b+1})=\dots=c(\alpha^{b+\delta-2})=0$$ Wouldn't this mean that all the words of a BCH code have Hamming weight $\delta$ ? Or am I wrong? $\endgroup$
    – Evinda
    Apr 29 '16 at 9:31
  • $\begingroup$ How to construct BCH code of the length $n$ over the field $GF(q)$ with designed distance $r$. We have to choose 1) $Q=GF(q^l)$ an extension of the field $GF(p)$ 2) $\alpha\in Q$ an element of order $n$ 3) a system $\alpha^s,\alpha^{s+1},...,\alpha^{s+r-1}$ (chain) Further, $g(x)$ be a minimal polynomial which annihilate any of $\alpha^i$. So, the cyclic code over $P$ with generating polynomial $g(x)$ is our BCH-code. Your case is narrow-sense, i.e. $s=1$. Any of codewords $c(x)$ can be represented in the form $$c(x)=g(x)t(x)(\mathrm{mod\ }(x^n-1))$$ $\endgroup$ Apr 29 '16 at 9:47
  • $\begingroup$ So $h(x)$ is word of weight $\delta$ since weight of $(h_r,...,h_1,h_0)=(1,...,1,1)$ is equal to $\delta$. So any of codewords $c(x)$ should have at least $\delta$ roots but it's weight can be greater than $\delta$ $\endgroup$ Apr 29 '16 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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