2
$\begingroup$

I consider primitive BCH codes, which are constructed as follows:

Choose positive integers $m$ and $r$, set $n=2^m-1$. Let $\alpha$ be a generator of the cyclic group $\mathbb{F}_{2^m}^*$. For each $1 \leq i < n$, let $m_i(x)$ be the minimal polynomial of $\alpha^i$ over $\mathbb{F}_2$. Then I consider the BCH code generated by the polynomial $lcm(m_1,\dotsc,m_r)$ (working modulo $x^n-1$).

It is known that the distance of such code is at least $r+1$. Can we bound the distance from above as well?

Conjecture: The distance is no more than $2(r+1)$ (maybe $2$ should be replaced with another small constant). Is it true?

  • 0
    So glad to hear that it helped @Jen !! You might consider writing up a summary as an answer. That way we can comment on it, give you upvotes, and having an answer also prevents this question from getting periodically bumped to the front page. Only if you're happy with what you learned, of course :-)2011-12-10

1 Answers 1

1

The answer appears exactly in Introduction to Coding Theory by van Lint.

Theorem 6.6.13 there proves that if the designed distance is of the form $2^l-1$ for some $l$ then the distance equals the designed distance exactly.

Corollary 6.6.14 then takes an arbitrary primitive BCH code, finds the largest primitive BCH code of the form of Theorem 6.6.13 and uses the codeword with lowest hamming weight in this subcode to show that for a general BCH code we have $d \leq 2r-1$ ($d$ is the distance, $r$ is the designed distance).

Thus, in general, $r \leq d \leq 2r-1$.

(van Lint takes $g(x) := lcm(m_1(x),\dotsc,m_{r-1}(x))$ as a generator).

  • 1
    Well done, Jen! The exponent in my comment is "almost" off by one. I was simply looking at the degree of a symmetric function (here a power sum related to an odd exponent), and studied the characteristic polynomial of a subspace. That is not quite enough. I neglected to also use the fact that one factor of each term in Waring's formula must have odd degree, and that saves the day, because the first non-zero basic symmetric polynomial of an odd degree is of a higher degree.2011-12-15