Cyclic Redundancy Check (CRC) in a nutshell

Given:        

•     A message M of k-bits

•     A polynomial P of (n+1) bits

Problem

    Calculate F (n-bits) such that MF, i.e. F appended to M, consisting of (k+n) bits is exactly divisible by P

Solution

    F is the remainder when M * 2ⁿ is divided by P.

Note: 

1. The most and next most significant bit of the polynomial must be '1'. A polynomial P = 1101 means 1*2³ + 1*2² + 0*2¹ + 1*2⁰

2. The subtraction in division will be bit wise XOR, not the normal subtraction.

Let our message be M = 11101 and the polynomial is P = 1101. The steps are:

1. Append 'n' 0's to M to get the dividend D = 11101000

2. Divisor is P = 1101

3. Perform CRC division [D / P] keeping in mind the XOR subtraction

4. The remainder is F

1101 ) 11101000 ( 10101

           1101

          ------------

             0111

             0000

          ------------

               1110

               1101

          ------------

                 0110

                 0000

          ------------

                   1100

                   1101

          ------------

                      001

Thus F is "001".

11101001 [MF] is fully divisible by 1101 [P]. Convince yourself.

How is CRC related to networking?

CRC is used for error detection in Medium Access Sublayer. The transmitter and receiver agrees on a common polynomial and data block size (k) that will be used. The transmitter has the message M. It calculates F, appends F to M, and puts the whole thing (k+n bits) on the wire. On receiving the k+n bits, receiver divides them with P. If the polynomial based on the received k+n bits is fully divisible by P, then the receiver is satisfied that there was no error in transmission.

The hardware used for CRC calculation is illustrated at http://www.rad.com/networks/1994/err_con/crc_hard.htm The same hardware is used for finding F at transmitter end and testing divisibility at the receiver end. The hardware is dependent on the polynomial. Different polynomial will require different hardware.

CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial, CRC Cyclic Redundancy Check Tutorial,