# Parity Check Polynomial of Non-cyclic Code

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

-
If I understand the definitions right, then ordinary CRC as usually applied for detection of non-malicious data corruption is not (despite the name) a cyclic code for most message lengths. –  Henning Makholm Jan 16 at 1:01
@Henning, that's correct. Typically payload+CRC bits form a cyclic code, when the total packet length is equal to the exact maximum of the designed range of packet lengths for the given CRC. –  Jyrki Lahtonen Jan 16 at 19:56

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$.

-
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)$.