Cyclic redundancy codes algorithm

The algorithm used by the cyclic redundancy check is the following:

Append r "0" to the right of the message (that is, as many zeros are added as the degree of the generating polynomial).

The obtained polynomial is divided by the generator polynomial. Division is done modulo 2, which is the same as binary division, with two exceptions:

• 1 + 1 = 0 (no stroke) and
• 0 - 1 = 1 (no stroke)

Which is equivalent to applying a bitwise exclusive OR (XOR) operation

Then the remainder of the division is added to the right of the original message.

The choice of the generator polynomial is essential if we want to detect most of the errors that occur. One of the most commonly used generator polynomials is the CCITT standard:

x¹⁶ + x¹² + x⁵ + 1.

This polynomial allows the detection of:

• 100% simple mistakes.
• 100% double errors (except the exceptional case that are exactly separated (2^16)-1 bits)
• 100% errors of an odd number of bits.
• 100% raffle errors (in a successive series of bits) of 16 or less bits.
• 99.99% errors in bursts of 18 or more bits.