[Math] Generator matrix of a BCH code

coding-theorydiscrete mathematics

The task is the following:

Create a 6-length, 1-error correcting BCH code, using $\alpha = \overline{x+1}$ of the group $\mathbb{Z}_2[x] / \langle x^3 + x + 1 \rangle$.
Furthermore, calculate the generator matrix of the code.

My question is, what is the general method in order to solve a task like this?

Best Answer

It is not clear from the question as to whether the codeword symbols are to be in the field $\mathbb{Z}_2[x] / \langle x^3 + x + 1 \rangle = \mathbb F_{2^3}$ or the binary field $\mathbb{Z}_2$, and in this latter case, the only reason to introduce $\mathbb{Z}_2[x] / \langle x^3 + x + 1 \rangle$ is so that the element $\alpha$ can be identified as the equivalence class of $x+1$ in $\mathbb{Z}_2[x] / \langle x^3 + x + 1 \rangle$.

$\alpha$ happens to be a primitive element of $\mathbb{Z}_2[x] / \langle x^3 + x + 1 \rangle$, and a common definition of a $1$-error-correcting BCH code is a cyclic code of length $\mathsf{ord}(\alpha) = 7$ with the property that its generator polynomial $g(y)$ has as zeroes both $\alpha$ and $\alpha^2$.

  • If the codeword symbol field is $\mathbb{Z}_2$, then $g(y)\in \mathbb{Z}_2[y]$ and hence has $\alpha^4$ as a zero also (because of the conjugacy constraints). Hence, $g(y) = (y-\alpha)(y-\alpha^2)(y-\alpha^4)$ is the minimal polynomial of $\alpha$ over $\mathbb{Z}_2$. Note that $\deg(g(y)) = 3$.
  • If the codeword symbol field is $\mathbb{Z}_{2^3}$, then $g(y) \in \mathbb{Z}_{2^3}[y]$ and since there are no conjugacy constraints, it follows that $g(y) = (y-\alpha)(y-\alpha^2)$ and $\deg(g(y)) = 2$.

A length $6$ code is then a shortened version of the cyclic BCH code. It is not a cyclic code, and its (nonsystematic) generator matrix can be taken to be $$G = \left[\begin{matrix}g_0&g_1&g_2&g_3 &0 &0\\ 0 &g_0&g_1&g_2&g_3 &0\\0 &0 &g_0&g_1&g_2&g_3 \end{matrix}\right] \quad \text{or}\quad G = \left[\begin{matrix}g_0&g_1&g_2 &0 &0 &0\\ 0 &g_0&g_1&g_2&0 &0\\0 &0 &g_0&g_1&g_2&0\\ 0 &0 &0 &g_0&g_1&g_2 \end{matrix}\right]$$ depending on which field the codeword symbols are assumed to be in.

Related Question