[Math] Generator matrix of a binary cyclic code

coding-theorycombinatoricsparitypolynomials

I need to find the Generator and Parity check matrix of a binary cyclic [9,2] code. If I calculated right, the Generator polynomial is x^7 + x^6 + x^4 + x^3 + x + 1 and the check polynomial is x^2 – x + 1. But how do I find the matrices of both of these? Any help would be much appreciated!

Here's what I have so far. How long do I keeps shifting the codewords?

|1 1 0 1 1 0 1 1|
|1 1 1 0 1 1 0 1|
|1 1 1 1 0 1 1 0|
|0 1 1 1 1 0 1 1|
|1 0 1 1 1 1 0 1|
|1 1 0 1 1 1 1 0|
|0 1 1 0 1 1 1 1|

Best Answer

For a cyclic code with generator polynomial $g(x) = g_0 + g_1 x + \ldots + g_r x^r$, the generator matrix is

$$G = \begin{pmatrix} g_0 & g_1 & \cdots & g_r & & & & \\ & g_0 & g_1 & \cdots & g_r & & & \\ & & g_0 & g_1 & \cdots & g_r & & \\ & & & \ddots & \ddots & \ddots & \ddots & \\ & & & & g_0 & g_1 & \cdots & g_r \\ \end{pmatrix}$$

where blank spaces represent $0$. The generator matrix has dimensions $k \times n$, where $k$ is the dimension of the code and $n$ is the length of the code.

A couple options for finding the parity check matrix:

  • If a code has generator matrix $G = \begin{pmatrix}I|A\end{pmatrix}$, it has parity check matrix $H = \begin{pmatrix}-A^T|I\end{pmatrix}$. You can use Gaussian elimination to get $G$ into the form $\begin{pmatrix}I|A\end{pmatrix}$.

  • Another way to find a parity check matrix is to realize that the check polynomial of your code is the generator polynomial of the dual code, so that if $h(x) = h_0 + h_1 + \ldots + h_k$, then

    $$H = \begin{pmatrix} h_0 & h_1 & \cdots & h_k & & & & \\ & h_0 & h_1 & \cdots & h_k & & & \\ & & h_0 & h_1 & \cdots & h_k & & \\ & & & \ddots & \ddots & \ddots & \ddots & \\ & & & & h_0 & h_1 & \cdots & h_k \\ \end{pmatrix}.$$

You should prove for yourself that both of these methods yield a parity check matrix for the code.

Related Question