CRC : Cyclic Redundancy Check


1. Definition

Cyclic redundancy check is a coding technique coding to control errors that may occur when transmitting messages (frames) between a sender and a receiver.
The code itself does not contain an error control. If the recceiver detects an error in the massage, a request is done to retransmit the message again.

2. The rule

The sender and the receiver have agreed in advance on a generator polynome: G(x).
For each word in the message, the sender creates a set of extra bits to append to the message word; that is called Checksum.
Once the message word is received, the receiver performs the same rule to it; by computing the checksum. If the resulting checksum is nonzero, an error has occurred, and the sender will resend the message word. The error will be corrected by retransmissions. Computing and checking the checksum are generaly made in hardware level.

3. Example

the vector [1 1 0 1] represents the polynomial x3 + x2 + 1.
Let's consider the following polynomial:
F(x) = x4 + x2 + x
represented by the vector: [1 0 1 1 0]
And the polynomial:
G(x) = x2 + 1
represented by the vector: [1 0 1]

We can write:
F(x) x2 = Q(x)G(x) + R(x)
2 is the degree of G(x)

Then:
F(x) x2 = x6 + x4 + x3
F(x) x2 /G(x) = x4 + x; the remainder is x. Then :
F(x)x2 = G(x) (x4 + x) + x . Thus:
Q(x) = x4 + x, and
R(x) = x corresponding to [1 0] 0r [0 1 0] to have the length 3.
The following polynomial T(x) can be expressed as:
T(x) = F(x)x2 - x = G(x) Q(x)
T(x) is divisible by G(x). G(x) is called theGenerator Polynomial
T(x) is represented by:
[1 0 1 1 0] ^[0 1 0] = [1 0 1 1 0 0 1 0] That is the concatenation of the inputframe and the Checksum.

Remark that multiplying by xr corresponds to shifting the related vector by r bits to the left or append r zeros at the right.

The receiver will divide T(x) by G(x)( T(x) received it and G(x) knows it). If the reminder is zero, no error exist in the transmitted frame; otherwise, the sender will resend the message word.

4. CRC Algorithm

- F(x) corresponds to input binary data frame; - The vector corresponding to R(x) is called a Checksum. It cntains r bits to append to input frame (sent) to get output frame (received). The algorithm follows these three steps:
  1. Shift the input data frame by r bits and divide the corresponding polynomial by G(x),
  2. Set the checksum equal to the binary vector of length r, which correspoonds to the 1st step,
  3. Append the checksum to the input data frame to obtain the output frame.


5. Other example

Frame F: 101011110
G(x) (as a bit sequence): 11101
r = 4 → append 4 zeros, so F^ = 101011110 0000
Write the bit sequence 11101 and subtract modulo 2, that is use the bitwise XOR.

11101| 101011110 0000
   11101         
    10001        
    11101       
     11001      
     11101      
      01001     
      00000     
       10010    
       11101    
        1111 0   
        1110 1   
         001 10  
         000 00  
          01 100 
          00 000 
           1 1000
           1 1101
            0101


The remainder is 0101; that is the checksum. Now subtract it from F^.
Since subtracting and adding or equal to XOR, we can just write:
The transmitted frame T = F^ + Remainder = 101011110 0000 + 0101 = 101011110 0101 (or just append the checksum to the frame)

6. CRC-N Generator

The CRC-N Generator block generates cyclic redundancy code (CRC) bits for each input data frame and appends them to the frame. It is a simplified version of the General CRC Generator block in the sense that we can select the generator polynomial for the CRC algorithm from a list of commonly used.
N represents the degree of the generator polynomial.
CRC-N MethodGenerator PolynomialNumber of Bits
CRC-32 x32 + x26 + x23 + x22 + x16 + x12 + x11
+ x10 + x8 + x7 + x5 + x4 + x2 + x + 1		 32
CRC-24 x24 + x23 + x14 + x12 + x8 + 1 24
CRC-16 x16 + x15 + x2 + 1 16
ReservedCRC-16 x16 + x14 + x + 1 16
CRC-8 x8 + x7 + x6 + x4 + x2+1 8
CRC-4 x4 + x3 + x2 + x + 1 4

7. CRC-N Syndrome Detector

It detects errors in input data frames.
The CRC-N Syndrome Detector block computes the checksum for an input frame. It is a simplified version of the General CRC Syndrome Detector block, whereby we can select the generator polynomial from the list above.