Cyclic Redundancy Check (CRC) Example

Sean E. O'Connor

artifex@seanerikoconnor.freeservers.com

Abstract

We go through a complete example of CRC encoding and decoding.

1. An Example with CRC-16

The CRC-16 generator polynomial is

Let a sample message be , which we will encode as the coefficients of the polynomial,

Let's assume we are encoding the message bit stream .  The binary digits will be the coefficients of our message polynomial i(x), with the least significant bit being the constant term of the polynomial:

Enter the code's blocklength n and message length k, and compute the the number of parity bits n-k.

For systematic encoding, the parity is p(x) = [- mod g(x) where we do modulo 2 arithmetic on the polynomial coefficients.

Writing the polynomial coefficients in binary we get the parity,
0011 0101 1100 1111=35CF

Compute the systematically encoded codeword
c(x) =   + p(x).

Compute the shifted syndrome s'(x) = [ mod g(x), modulo 2 on the polynomial coefficients.  We should get zero.

Add error to the codeword.

Compute the shifted syndrome s'(x) = [ mod g(x) modulo 2 on the polynomial coefficients.  We should get a non-zero answer.

On the other hand, if we add a multiple of a codeword, we won't see the error.

2. An Example with CRC-32Q

Let a sample message be