Deinition of CRC Codes

Overview

CRC (Cyclic Redundancy Check) codes are extended Hamming codes. They are used to detect burst errors in communications systems of all kinds. Their generator polynomial is $g(x) = M_\alpha(x)(x+1)$ where $M_\alpha(x)$ is a minimal polynomial of the primitive element $\alpha$ of $GF(2^m)$. In other words, a primitive polynomial of degree m modulo 2. The parity check matrix is, $$ M = \left( \begin{array} { ccccc } \alpha & \alpha^2 & \ldots & \alpha^{2^m-2} \\ 1 & 1 & \ldots & 1 \\ \ldots & \ldots & \ldots & \dots \\ \ldots & \ldots & \ldots & \dots \\ \end{array} \right) $$

which has at least 3 independent columns, giving a minimum distance of $d^* \ge 4$

CRC codes are chosen so that $deg( g(x) ) = 12, 16, 24, 32, \ldots$ so that both parity bits and generator polynomial coefficients fit into one computer word. Encoding and decoding easy and fast in hardware linear feedback shift registers, since we can add modulo 2 using XOR and multiply using AND while shifting bits circularly within a word.

The code blocklength is $n = 2^m-1$ and the number of parity bits is $r = n - k$ where $m = deg(M_\alpha(x)) = deg(g(x))-1$ We can pick one of the $\frac{\phi(2^m-1)}{m}$ primitive polynomials of degree $m$, subject to the conditions discussed below.