Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Jyrki Lahtonen Dec 10 '11 at 16:10
    
Opened that book now and found an affirmitive answer to my question in Corollary 6.6.14. Thanks for the reference @Jyriky. –  Jen Dec 10 '11 at 16:52
    
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 :-) –  Jyrki Lahtonen Dec 10 '11 at 22:03
add comment

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer
    
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. –  Jyrki Lahtonen Dec 15 '11 at 16:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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