# Definition of the CRC Codes

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.

Some properties of CRC-CCITT are:

 Description CRC-CCITT, a standard 16 bit CRC code. Block Length $n = 2^{15}-1 = 32767$ Message Length $1 \rightarrow n-16 = 32751$ Number of Parity Bits $n-k = 16$ Error Locator Field $GF(2^m) = GF(2^{15})$ Error Correction Ability $t = 1$ Minimum Distance $d^* = 4$ Generator Polynomial $g(x) = x^{16} + x^{12} + x^5 + 1$ Random Error Detection Ability $d^* -1 = 3$ Probability of Undetected Error, burst length $b \le n-k = 16$ $0$ Probability of Undetected Error, burst length $b = n-k+1 = 17$ $\frac{1}{2^{n-k-1}} = \frac{1}{32767}$ Probability of Undetected Error, burst length $b > n-k+1=17$ $\frac{1}{2^{n-k}} = \frac{1}{65536}$