Dtyjlui

In general, what is the strategy for obtaining a generator polynomial (and a check polynomial) given a parity check matrix $H$ for a binary cyclic code?

Things I know:

• Each codeword $c(x)$ satisfies $c(x)h(x)=0$


• $deg g(x)=N-k$


• $g(x) | x^N+1$


• $(g(x))$ is an ideal that generates the whole thing.

The natural domain for the algebra of binary cyclic codes of length $N$ is the quotient
ring $R_N=mathbb{F}_2[x]/langle x^N+1rangle$.

The key observation is that if we turn a sequence $c$ of $N$ bits into a polynomial $c(x)in R_N$ of degree $le N-1$ in the usual way, then the binary "inner product" of two vectors $c$ and $c'$, $langle c,c'rangle$, is equal to the constant term of the product $c(x)c'(x^{-1})$ in the ring $R$.

If $h$ is any row of the check matrix, then this implies that for all codewords $c$ the product $c(x) h(x^{-1})$ should have a vanishing constant term. But the products $x^jc(x)in R_N$ is the polynomial we associate with the cyclic shifts of the word $c$, $j=1,2,ldots, N-1$ by $j$ positions. As the cyclic shifts of $c$ are also codewords, the constant terms of all the products (in $R_N$) $x^jc(x)h(x^{-1})$ must vanish. As $j$ ranges from $0$ to $N-1$, all the terms of the product $c(x)h(x^{-1})$ occur as constant terms for some choice of $j$. Therefore we must have $c(x)h(x^{-1})=0$ in $R_N$.

Let us call any polynomial $h(x)$ with the property that $c(x)h(x^{-1})=0$ for all codewords $c$ a dual polynomial. If $h(x)$ and $h'(x)$ are dual polynomials, then so are
all the polynomials of the form $x^jh(x)+x^ih'(x)$ as well as longer linear similar combinations. We see that the dual polynomials form an ideal of $R_N$ as well as of the polynomial ring $mathbb{F}_2[x]$, so for example the gcd of two dual polynomials is a dual polynomial. Also $x^N+1$ is a dual polynomial. We want to find a generator for this ideal. As all the rows of the parity check matrix yield dual polynomials, we get the following general method:

1. Turn all the rows of the check matrix into polynomials $h_i(x)in R_N$.


2. Compute the greatest common divisor ${tilde h}(x)=gcd(h_1(x),h_2(x),ldots,h_{N-k}(x),x^N+1)$ in the ring $mathbb{F}_2[x]$.


3. The reciprocal polynomial of this ${tilde h}(x)$ is the check polynomial $h(x)=x^N{tilde h}(x^{-1})$ (I multiplied it with $x^N$ to turn it into a polynomial in $x$. In the ring $R_N$ we have $x^N=1$, so this does not affect the algebra at all).


4. Compute the polynomial $g(x)=(x^N+1)/h(x)$.

The validity of this algorithm for finding the polynomials $h(x)$ and $g(x)$ follows from the preceding discussion as well as from the general theory of cyclic codes (telling us in advance that a prescribed polynomial $h(x)$ of degree $N-k$ exists). I am not inclined to reproduce all of it here.