Parity Check Polynomial of Non-cyclic Code

Question

I'm currently working on an exercise sheet in Discrete Mathematics which is about error-correcting codes. In this regard I'm wondering if it is generally possible to find a parity check polynomial for a NON-cyclic code?

Thanks in advance and best regards, Patrick

Answer 1

If we have a linear code with generator matrix $G$ (so our code is the row space of $G$), then there is a matrix $H$ such that our code is the null-space of $G$. The matrix $H$ is called a parity-check matrix, and always exists: if $$ G = \begin{pmatrix} I_k&G_0\end{pmatrix} $$ where $G_0$ is $k\times n-k$, then $$ H = \begin{pmatrix}-G_0^T& I_{n-k}\end{pmatrix} $$ But there is no parity-check polynomial in general.

Suppose $G$ is $k\times n$ (with linearly independent rows). Then $H$ will be $(n-k)\times n$. If $h$ is row of $H$ then the linear equation $h.x=0$ is a constraint that must be satisfied by any code word $x$, and so we have altogether $n-k$ linearly independent constraints which any code word must satisfy. If the code is cyclic, we can arrange things so that each row of $H$ is the cyclic shift of the one above it. In this case it makes sense to think of the first row of a $H$ as the coefficients of a polynomial $p(t)$, and then the remaining rows correspond to polynomials of the form $t^rp(t)$. If the code is not cyclic, this is impossible.

One advantage of cyclic codes is that the hardware needed for encoding and decoding is an order of magnitude simpler than that needed for a general linear code, basically because we only need one row of $G$ or $H$.

Answer 2

The thing that makes cyclic codes so nice is that they correspond exactly to the ideals of the ring $F[x]/(x^n-1)$.

Because this ring is a principal ideal ring, every ideal is generated by a single polynomial, its generating polynomial (call it $g(x)$). The parity check polynomial is given exactly by $(x^n-1)/g(x)$.

In general, noncyclic codes do not live in such nice rings, and have no relationship with polynomials to speak of, so there is no reason to expect there would be convenient polynomial representations of their parity check matrices.