2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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}$? $\endgroup$ – Dilip Sarwate Nov 12 '14 at 15:05
  • $\begingroup$ Yes, i know how to compute the conjugates. $\endgroup$ – Lullaby Nov 12 '14 at 18:11
  • $\begingroup$ Good. Now, what is the definition of a binary BCH code? $\endgroup$ – Dilip Sarwate Nov 12 '14 at 19:49
  • 1
    $\begingroup$ Hint: $\alpha^5$ and $\alpha^9$ share the minimal polynomial. $\endgroup$ – Jyrki Lahtonen Nov 21 '14 at 20:48
1
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.