[simple_series title=”CRC Tutorial”]

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 0000₂ divided by 10011₂ using XOR instead of addition/subtraction, results in 0110010₂. 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 0110₂.

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. ^[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.) 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.