Cyclic Redundancy Check sequences (CRC): A Big Mystery?


[simple_series title=”CRC Tutorial”]

As mentioned in the section on ISBN check digits, a CRC can be coarsely approximated as a check digit in a sequence where each input digit is multiplied with a different weight. But the confusion starts when different people start talking about the different ways one can view the CRC calculation:

Hardware designers
…often think of CRC calculation as the repeated conditional
XOR as the data bitstream flows by.
Software engineers
…generally consider it to be something that you deal with unconditionally byte-per-byte using a table lookup.
Mathematicians
…prefer to explain it as the remainder in a polynomial division.
Cryptographers
…secretively mumble about operations in the Galois Field of order 2, obscurely abbreviating it as GF(2).

All of them do the same: They produce a weighted sum of all the bits in the data stream which, when joined with the “checksum”, will give a remainder of 0 after a division. To understand the process and the advantages of the different approaches, we look at the CRC problem from all four vantage points.

Besides the four ways of performing the calculations, there are also different values that control the calculation and thus the final error-detection properties of the “checksum”. This value has different names, depending on the viewpoint: generator function, generating
polynomial, or characteristic function. This value has a width b associated with it, which determines the number of bits of the resulting checksum.

 

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.