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_{n1} * x^{n1} + bit_{n1} * x^{n2} + ... + bit_{0} * x^{0}
For example, for the sixteen bit number
10011011 00100001 the
polynomial (leaving out zero valued terms) would be:
x^{15} + x^{12} + x^{11} + x^{9} + x^{8} + x^{5} + x^{0}
This polynomial is calculated and then divided by another. The value
of this divisor polynomial is based on the type of CRC implemented.
