Why the dimension of bch code is unknown?

Question

My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $\delta$, and I asked for it dimension.

The output file ALWAYS ends with a $p^{m+1}$ code of dimension $1$ then there are no code of dimension less then $p+1$ so there are a "jump" of $p$. in fact the "jump" is ALWAYS a divisor of $m$ and there are a certain number of those. and things get nicer when $m$ is prime.

There is well behaved pattern here but I'm not too smart to tell a general formula. But I believe it can be done.

So my question is: Why the dimension of bch code still unknown?

Answer 1

This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.

The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.

There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.

There is a nice survey by Ruud Pelikaan here.

Answer 2

There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.

• Whenever you increase the designed distance of a BCH-code, you can't immediately tell whether the code changes at all because the new zeros of the generator polynomial may not come from the smallest elements in their cyclotomic coset (in which case there will be no new zeros at all).
• Also, even if you get a new cyclotomic coset, its size is not immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).

The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).