How the CRC algorithm works

The CRC algorithm works above the binary field. The algorithm treats all bit streams as binary polynomials. Given the original frame, the transmitter generates the FCS for that frame. The FCS is generated so that the resulting frame (the cascade of the original frame and the FCS), is exactly devisable by some pre-defined polynomial. This pre-defined polynomial is called the devisor or CRC Polynomial.

For the formal explanation we will define the following :

M - The original frame to be transmitted, before adding the FCS. It is k bits long.
F - The resulting FCS to be added to M. It is n bits long.
T - The cascading of M and F. This is the resulting frame that will be transmitted. It is k+n bits long.
P - The pre-defined CRC Polynomial. A pattern of n+1 bits.

Click here to see an example:

The main idea behind the CRC algorithm is that the FCS is generated so that the reminder of T/P is zero. Its clear that

(1) T= M * x^n + F

This is because by cascading F to M we have shifted T by n bits to the left and then added F to the result. We want the transmitted frame, T, to be exactly divisible by the pre-defined polynomial P, so we would have to find a suitable Frame Check Sequence (F) for every raw message (M).

Suppose we divided only M*x^n by P, we would get:

(2) M*x^n / P = Q + R/P

There is a quotient and a reminder. We will use this reminder, R, as our FCS (F). Returning to Eq. 1:

(3) T= M*x^n + R

We will now show that this selection of the FCS makes the transmitted frame (T) exactly divisible by P:

(4) T/P = (M*x^n + R)/P = M*x^n / P +R/P = Q + R/P + R/P = Q + (R+R)/P

but any binary number added to itself in a modulo 2 field yields zero so:

(5) T/P = Q, With no reminder.

Following is a review of the CRC creation process:

1. Get the raw frame
2. Left shift the raw frame by n bits and the divide it by P.
3. The reminder of the last action is the FCS.
4. Append the FCS to the raw frame. The result is the frame to transmit

And a review of the CRC check process:

1. Receive the frame.
2. Divide it by P.
3. Check the reminder. If not zero then there is an error in the frame.

It can be easily seen that the CRC algorithm must compute the reminder of the division of two polynomials. The process is described in the following documents:

• Implementing the CRC algorithm in hardware
• Implementing the CRC algorithm in software