Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to construct a binary cyclic code of length $257$ with rate strictly greater than $\frac{1}{2}$ and distance $18$ or more.

I read about general BCH codes and implemented it.

The multiplicative order of $2$ modulo $257$ is $16$. So, I realize $\text{GF}(2^{16})$ as $\text{GF}(2)[t]/(t^{16}+t^5+t^3+t^2+1)$. I choose a $257$-primitive root of unity in $\text{GF}(2^{16})$. It is $\alpha=t^7+t^6+t^2+1$. Denote the $\text{LCM}$ of the minimal polynomials of $\alpha^{74},\dotsc,\alpha^{74+18-2}$ by $g(x)$. Then $\text{deg}(g(x))=128$.

So, the cyclic code of length $257$ generated by $g(x)$ has rate $\frac{129}{257}>\frac{1}{2}$ and distance at least $18$.

  1. Did I follow the steps of constructing a BCH code correctly?
  2. Are my calculations correct? (I used Sage, but I am very new to it and may have bugs).
  3. Given a generating polynomial, is there an efficient algorithm to check if the cyclic code it generates has at least a given distance? That would be handy for sanity-checks.
share|cite|improve this question
up vote 2 down vote accepted
  1. Yes. Those exponents fall into eight disticnt cyclotomic cosets modulo $257$, so the degree of the l.c.m. of their minimal polynomials is, indeed, $8\cdot 16=128$.
  2. That primitive polynomial was a surprise to me. I usually use 8as does MATLAB) $x^{16}+x^{12}+x^3+x+1.$ Of course, there are several primitive polynomials to choose from, but I had assumed that to be simplest (lexicographically first among polynomials of weight 5 or something like that). Anyway, I check with Mathematica that it is, indeed, a primitive polynomial. Sage is wiser! Also the element you mentioned is, indeed, a primitive root of unity of order $257$.
  3. The short answer is "No!" It is known that the question, whether a code with a given generator matrix (here generator polynomial) has a word of weight below a given a bound is in one of those nasty classes in the NP-hierarchy. So if you figure out how to do this in general, you will become famous. The same problem restricted to the class of cyclic codes is easier, but I am not aware of an algorithmic ways of verifying the minimum distance. Some algorithms for checking that the BCH-bound is exceeded exist. For example, the parameter set used in the construction may fit the Hartmann-Tseng bound. I recall having once reviewed a paper, where the authors introduced an algorithm for proving other similar improvements to the BCH-bound. They were more efficient than brute force, but not guaranteed to give the true minimum distance.
share|cite|improve this answer

Your Answer


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.