Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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 '13 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 '13 at 19:56

2 Answers 2

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.