- Tutorial: Cyclic Redundancy Check (CRC) Computation
- Background: Asynchronous Serial Communications (RS-232C)
- Parity Bits
- Intermission: Classes of errors
- Check Digits
- Error Correction Codes (ECC)
- Cyclic Redundancy Check sequences (CRC): A Big Mystery?
- CRC Hardware Operation
- Software CRC Computation
- Mathematical Background
Now you should have a general feeling of what happens in a CRC operation and what can or cannot be done. This will help you when we change to a slightly more formal description of the behavior. The figure on the left shows how the CRC calculation is done when we compare it to pen-and-pencil division. In this discussion, we represent XOR as either + or -, to closer match standard division.
In stage A, we try to see whether we can subtract a multiple of the generator from the topmost 5 bits. As we work on binary numbers, the only two multiples are 0 (resulting in no subtraction, represented by
the light blue background) and 1 (resulting in subtraction of the generator, indicated by dark blue background). Subtraction (recall, this is XOR in this section) of the generator is possible if it makes the number smaller. With XOR, this is the case when the MSB is 1.
Our number, 011 0111 00002 divided by 100112 using XOR instead of addition/subtraction, results in 01100102. This can be determined in the usual way. Here,
you can also look at the light (0) vs. dark (1) blue, with the line in step A corresponding to the MSB and stage H delivering the LSB). This division results in a remainder of 01102.
By using this analogy, we can also use many of the arithmetic transformations known from school. For example, it also becomes obvious why the replacement of the zero-fill with the CRC results in a zero remainder after passing: Recall that the CRC is the remainder after dividing the padded message by the generator. Instead of padding with zeros, we want to pad with a bit sequence that makes the padded message evenly divisible by the generator (i.e., no remainder). In normal arithmetic, you would subtract the remainder from the padded message. This would result in changing the message unless the remainder was zero, as the subtraction would cause the borrow to be carried from the padding bits into the message. As XOR is addition/subtraction with neither carry nor borrow, CRCs do not have this problem. (Even in normal arithmetic, it could be overcome by adding the generator again for nonzero remainders.) Here, we do the same, except that our subtraction is XOR. Thus, we are guaranteed to have the CRC-padded message evenly divisible by the generator.
Footnotes [ + ]
|1.||↑||This would result in changing the message unless the remainder was zero, as the subtraction would cause the borrow to be carried from the padding bits into the message. As XOR is addition/subtraction with neither carry nor borrow, CRCs do not have this problem. (Even in normal arithmetic, it could be overcome by adding the generator again for nonzero remainders.)|