ntroduction

The CRC is a very powerful but easily implemented technique to obtain data reliability. The CRC technique is used to protect blocks of data called Frames. Using this technique, the transmitter appends an extra n- bit sequence to every frame called Frame Check Sequence (FCS). The FCS holds redundant information about the frame that helps the transmitter detect errors in the frame. The CRC is one of the most used techniques for error detection in data communications. The technique gained its popularity because it combines three advantages:

• Extreme error detection capabilities.
• Little overhead.
• Ease of implementation.

The following sections will explain the CRC more in depth:

• How the CRC algorithm works
• Implementing the CRC algorithm in hardware
• Implementing the CRC algorithm in software
• The Most used CRC polynomials

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.

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.

Implementing the CRC algorithm in hardware
The hardware CRC implementation is shown in the next figure. The Implementation shown is for a specific set of parameters:

Message M=1010001101
Pattern P=110101
FCS F=1110 (to be calculated)

The circuit is implemented as follows:

1. The register contains n bits, equal to the length of the FCS
2. There are up to n XOR gates
3. The presence or absence of a gate corresponds to the presence or absence of a term in the divisor polynomial P(X)

The same circuit is used for both creation and check of the CRC. When creating the FCS, the circuit accepts the bits of the raw frame and then a sequence of zeros. The length of the sequence is the same as the length of the FCS. The contents of the shift register will be the FCS to append. When checking the FCS, the circuit accepts the bits of the received frame (raw frame appended by FCS and perhaps corrupted by errors). The contents of the shift register should be zero or else there are errors.
Implementing the CRC algorithm in software

The simplest way of implementing the CRC algorithm in software is to take the hardware implementation and write the appropriate code, replacing the shift register with a variable and the XOR gates with the xor operator. This method is the easiest to implement and consumes very little memory. It’s performance, however is poor.

When the time of the CRC process is of importance, faster software algorithms should be used. Those algorithms process one byte at a time and not one bit at a time like the hardware implementation does. Those algorithms have one main disadvantage: they have to keep tables in memory and so need more memory than the bitwise algorithm does.
The Most used CRC polynomials
Following is a list of the most used CRC polynomials

• CRC-12: X^12+X^11+X^3+X^2+X+1
• CRC-16: X^16+X^15+X^2+1
• CRC-CCITT: X^16+X^12+X^5+1
• CRC-32: X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1

The CRC-12 is used for transmission of streams of 6-bit characters and generates 12-bit FCS. Both CRC-16 and CCRC-CCITT are used for 8 bit transmission streams and both result in 16 bit FCS. The last two are widely used in the USA and Europe respectively and give adequate protection for most applications. Applications that need extra protection can make use of the CRC-32 which generates 32 bit FCS. The CRC-32 is used by the local network standards committee (IEEE-802) and in some DOD applications.