How to calculate BCH parameters?

Question

I recently got interested in BCH code, and there are two points that seems a little bit tricky for me. I made some research on internet, but I cannot find answers to my questions so I will try here, hoping they are not stupid questions.

First, how to calculate BCH parameters? For example, if I have a data of length $k$ and I need a correction capability of $t$, how do I know if it is possible and in this case, how many check bits $n-k$ do I need?

I Know that BCH code are defined as:

• Block length: $n = 2^m-1$
• Number of check bits $n-k \le mt$
• Minimum distance $dmin \ge 2t+1$
• With $m\ge3$ and $t<2^{m-1}$

However, I am not sure this is enough to determine check bits number. For instance, if I want to code a 4-bit data, with a correction capability of 2, I can use $m=3$ so that

• $n=2^3-1 = 7$
• $n-k=3 \le mt=6$

However, when I try this configuration with a C program (the-art-of-ecc.com/3_Cyclic_BCH/bch_bm.c), it says that it is an invalid configuration. Therefore, I need help to understand how it works and if anyone could help me this that would be great.

My second question is the following: what happen is there are more errors than the code is capable to correct? Does the algorithm is not capable of doing anything or does it try to correct the code but add additional errors, or even does it act another way?

Answer 1

You have wrong information about the number of required check bits. Usually the upper bound is tight. In other words, more often than not $$ n-k=mt. $$ When $n=7, k=4$ you can thus only correct a single error ($t=1$).

The mistake seems to be that you think that every $n,k,m,t$ combo satisfying those constraints is ok. Think about it for a second. The inequality $n-k\le mt$ surely holds when $n=k$. Implying that you would not need any check bits whatsoever! That is surely absurd.

There are exceptions to the tightness of $n-k\le mt$. Figuring out the exact number of check bits requires a little bit understanding of the finite fields. I can add a precise explanation if you are interested. Basically two factors come into play:

• Some powers $\alpha^{2j+1}, 0\le j<t$, of the chosen primitive element $\alpha$ belong to a proper subfield, and it saves a few check bits whenever that happens
• Some such powers share the same minimal polynomial implying that you get an extra error corrected free of charge. This happens whenever $2j+1$ and $2j'+1$ belong to the same cyclotomic coset for distinct $j,j'$ in the range $[0,t)$.