Binary BCH code with given distance and rate

Question

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.

Answer 1

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 (as 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 checked 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.