Error Correction Code

Cyclic Redundancy Check (CRC)

Terminology

• degree of polynomial: the highest power of the variable in the polynomial:

  • e.g., degree of is 3

• burst error: a contiguous sequence of bits that are erroneous (flipped from 0 to 1 or from 1 to 0)

Construction of frame

Let’s say we want to transmit frame that contains a data block of length bits. The idea of CRC is to append a checksum (CRC bits) of length bits to the end of data block before transmission.

In fact, both data block and checksum can be viewed as polynomials over the finite field of integer modulo 2, that is:

• each coefficient is either 0 or 1
• addition and subtraction are performed modulo 2 (equivalent to XOR operation)

For example, data block can be represented as polynomial:

So if we describe the generation of frame mathematically, we have:

similarly, we can describe it in binary format:

Generating CRC bits

To generate CRC bits , both sender and receiver agree on a generator polynomial of degree (which means has bits). The generator polynomial is usually chosen to have good error-detection properties. Then, the sender computes CRC bits such that the following condition holds:

which means is divisible by . Recall that polynomial division can be written in the form of:

we can rewrite the condition as:

which means the remainder of dividing by is :

and hence we can obtain by performing polynomial division of by and taking the remainder.

Selection of generator polynomial

There two major direction in selecting generator polynomial :

• where is the primitive polynomial of degree over , which is irreducible and allow data blocks of maximum length bits

• where is the primitive polynomial of degree over :

  • can also detect all burst errors of length bits
  • can detect all odd number of bit errors (parity check)
  • can only handle data blocks of maximum length bits

Parity check

If contains the factor , then CRC can detect all odd number of bit errors. This is because:

If we substitute , we have:

The are actually equivalent to counting the number of 1 bits in , and recall that the calculation is done in module 2, so means there are even number of 1 bits in