Search

   
0.12.3 Cyclic Redundancy Checks

While checksums are good at detecting errors in data they can be     fooled by transposition or complimenting changes. Weighted checksums do a better job of detecting transposition but are limited by the size of the data which they are being used to verify. For numbers   longer than about fifteen digits, the powers used to generate the positional values become too large to handle with C's basic types. While writing an extended number representation is one option to rectify this shortcoming, another method called a cyclical redundancy check (CRC) is another.  

A CRC computes a result based on both the value and position of individual bits in a block of data. To do so it uses individual bit values as exponents in a special polynomial:  

bit_n-1 * x^n-1 + bit_n-1 * x^n-2 + ... + bit₀ * x⁰

For example, for the sixteen bit number 10011011 00100001 the polynomial (leaving out zero valued terms) would be:

x¹⁵ + x¹² + x¹¹ + x⁹ + x⁸ + x⁵ + x⁰

This polynomial is calculated and then divided by another. The value of this divisor polynomial is based on the type of CRC implemented.