# Existence of a BCH-code?

I would like to ask about existence of a $[31,11,12]$ binary BCH-code. How to prove its existence, if it does i have to find the generator polynomial? Can i use some specific bound that could show or deny the existence of this code?

Since the BCH-codes are cyclic codes, we have dimension $11$, so the degree of the generator polynomial must be $20$.

Can anybody help me with this problem, please? Thank you in advance!

• Do you know the definition of a BCH code? Do you know how to determine the conjugates of $\alpha^i$ where $\alpha$ is a primitive element of $GF(32)$ a.k.a. $\mathbb F_{2^5}$? – Dilip Sarwate Nov 12 '14 at 15:05
• Yes, i know how to compute the conjugates. – Lullaby Nov 12 '14 at 18:11
• Good. Now, what is the definition of a binary BCH code? – Dilip Sarwate Nov 12 '14 at 19:49
• Hint: $\alpha^5$ and $\alpha^9$ share the minimal polynomial. – Jyrki Lahtonen Nov 21 '14 at 20:48

A restrictive but mostly adequate definition of a binary BCH code of designed distance $2t+1$ is of a cyclic code of length $n$ whose generator polynomial $g(x)$ has roots $\alpha, \alpha^2, \ldots, \alpha^{2t}$ where $\alpha$ is an $n$-th root of unity in some extension field GF$(2^m)$ (also called $\mathbb F_{2^m}$) of GF$(2)$ or $\mathbb F_2$. Since $g(x) \in \mathbb F_2[x]$, the conjugates of these $2t$ elements also are roots of $g(x)$. If we proceed systematically, beginning by making a list of the conjugates of $\alpha$ (which are $\alpha^2, \alpha^4, \cdots$), we see that some elements that we would take up later have already been accounted for.
The generator polynomial of a binary BCH code of length $31$ with designed distance $11$ has roots $\alpha, \alpha^2, \alpha^3, \ldots, \alpha^{10}$ and so we start listing the conjugates as
$$\underline{\alpha},\quad \underline{\alpha^2},\quad \underline{\alpha^4},\quad \underline{\alpha^8},\quad \alpha^{16}\\ \underline{\alpha^3}, \quad \underline{\alpha^6}, \quad \alpha^{12}, \quad \alpha^{24},\quad\alpha^{17}\\ \underline{\alpha^5}, \quad \underline{\alpha^{10}}, \quad \alpha^{20}, \quad \underline{\alpha^{9}},\quad\alpha^{18}\\ \underline{\alpha^7}, \quad {\alpha^{14}}, \quad \alpha^{28}, \quad {\alpha^{25}},\quad\alpha^{19}$$
where the elements on the $2t$ list are underlined. Note that we would have ended up with the same result if we had been looking for a code with minimum distance $9$; the fact that $\alpha^9$ is a conjugate of $\alpha^5$ (as Jyrki noted) and so the designed distance works out to be $11$ instead of $9$ is a serendipitous bonus that we were not seeking.
We conclude that $\deg(g(x)) = 20$ and so there does exist a $[n,k,d] = [31,11,11]$ BCH code, but not a $[31,11,12]$ code. There is a $[31,10, 12]$ BCH code which is a subcode (consisting of the even-weight codewords) of the $[31,11,11]$ BCH code described above. (It is a BCH code under a more general definition of BCH code, where any $d-1$ successive powers of $\alpha$ as roots of $g(x)$ gives a code of designed distance $d$: just include $\alpha^0 = 1$ as a root of $g(x)$ in the list displayed above).