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?

  • $\begingroup$ There is a standard argument (e.g. in van Lint's GTM series book on coding theory) showing that if $V$ is a subspace of $F_{2^m}$ of dimension $k$ (over the prime field), then it gives rise to a code word of the BCH-code of weight $2^k-1$, if $r\le 2^{k-1}$. At first I felt that this answers your question in the affirmative, started typing the argument as an answer, but now I'm not sure. $\endgroup$ Dec 10, 2011 at 16:10
  • $\begingroup$ Opened that book now and found an affirmitive answer to my question in Corollary 6.6.14. Thanks for the reference @Jyriky. $\endgroup$
    – Jen
    Dec 10, 2011 at 16:52
  • $\begingroup$ 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 :-) $\endgroup$ Dec 10, 2011 at 22:03

1 Answer 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
    $\begingroup$ 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. $\endgroup$ Dec 15, 2011 at 16:29

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.