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

Copyright © 1986-2017 by Sean Erik O'Connor. All Rights Reserved. last updated 10 Nov 17.