CRC is a kind of Error Check technology and stands for Cyclic Redundancy Checksum. The way it is used can be illustrated as follows. More detailed explanation about the concept and application of CRC is described in CRC in Error Check page. However, I decided to create a separate page for this topic mainly to deal with some examples in very detail. I want to explain on these examples in more practical way rather than too much theoretical way (If you are interested in the theoretical background, you can look into 'division of polynomial in Galois Field 2').
- The green block is the Message, which is the data to be sent.
- The CRC Algorithm box takes that message and produces the yellow block, the CRC Checksum.
- The Codeword is the two of them together, message first and checksum last, and the codeword is what goes on the air.
Example 1 >
This example itself came from an example in Ref [1]. However, the way I explain on this would be pretty much different from the ref [1] or most of textbooks. I tried to write down every steps as I am calculating the checksum by hand.
Most of the CRC problems are given as follows. You will be given a generator polynomial and a message data from which you need to calculate the checksum bits
Before you jump into solving the problem, let's rewrite the given information into a little bit different format (as in red)
Once you get these information, build a binary division equation as follows (as you see, the dividend is created by combining the given message data and trailing zeros.
If you are familiar with binary operation (GF(2) polynomial division), just drawing the equation above would be enough and you may directly write down the solution as follows.
If you are not familiar with the GF2 division or you want to have the solution process in more like computer algorithm rather than mathematical formula, go through following steps. Just reading through these steps may confuse you. I would suggest you write down each and every steps shown here by paper and pencil.
With the checksum that was calculated above and the message data, you can create the codeword that is to be transmitted.
Two details in that procedure are worth stating plainly, because the step drawings use them without naming them.
The first is the arithmetic. Every subtraction in the division is an XOR, so no borrow passes between columns and no carry does either. That is what makes the division mod 2, and it is why two equal bits in a column always leave a zero. The GF(2) page covers the rule itself.
The second is the trailing zeros. Four of them were appended because the checksum is four bits long, and the checksum is four bits long because the generator polynomial has order 4. Appending them shifts the message left by four places, which leaves room at the end for the remainder to sit without disturbing the message.
The result is worth reading back off the drawing. The quotient comes out as 10101100 and the remainder as 0100, so the checksum is 0100 and the transmitted codeword is 11100101 followed by 0100. The quotient is then discarded, because only the remainder is ever sent.
Checking the codeword at the receiver
The steps above build the codeword. They say nothing about what the receiver does with it, and that half of the job is the shorter one. The receiver runs the same division, on the whole codeword rather than on the message alone.
Take the received bits, all twelve of them in this example, and divide them by the same generator 11011. No zeros are appended this time, because the checksum already occupies the last four places. A remainder of zero means the check passes.
The reason lies in the way the checksum was built. Appending the remainder to the shifted message produces a number that the generator divides exactly, so every codeword the transmitter can produce leaves a remainder of zero. A remainder that is not zero therefore means the received bits are not a codeword, and something changed on the way.
What happens next is the part CRC does not cover. A non zero remainder says that an error occurred and says nothing about where, so CRC detects rather than corrects. Correction is the job of the codes on the Coding page, and CRC usually runs after them as a final check.
One limit is worth carrying away. A remainder of zero means no error was detected, not that no error occurred. An error pattern that happens to be a multiple of the generator goes undetected, and a longer checksum makes that rarer. Four bits is a teaching size. 3GPP attaches 6, 11, 16 or 24 bit CRCs depending on what is being protected, and the 5G Channel Coding page shows which length goes where.
Reference :
[1] CRC Series, Part 3: CRC Implementation Code in C/C++