[Math] Obtaining a generator polynomial from a parity check matrix for a binary cyclic code

abstract-algebracoding-theorygenerating-functionsparity

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.

Best Answer

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+1\rangle$.

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.

Related Question