A cyclic redundancy check represents a bit string as a polynomial over the field with two elements and uses a polynomial remainder as checking information. Agree on a monic polynomial of polynomial degree with constant term . Under the basic systematic convention, a message polynomial produces
Here , and addition equals subtraction over the field with two elements, so divides the transmitted polynomial . The receiver tests the polynomial remainder on division by the same CRC generator polynomial.
For example, and give and . If an error polynomial changes to , the error is undetected exactly when divides . Thus the CRC generator polynomial controls which bit-error patterns the cyclic redundancy check detects. This basic convention fixes the mathematics; implementations can additionally specify initial register contents and bit-order conventions.
The CRC generator polynomial is the agreed divisor used in a cyclic redundancy check. In the basic binary convention it is a monic polynomial of polynomial degree with . A nonzero error polynomial goes undetected exactly when .
This algebra gives useful detection guarantees. A single changed bit has and cannot be divisible by when . More generally, suppose the first and last changed bits span at most consecutive positions. Write with and . Since and are coprime polynomials, would imply , contradicting the polynomial degree bound. Every such error pattern is therefore detected.
If divides , every error changing an odd number of bits is also detected: its error polynomial satisfies , whereas every multiple of has value zero at .

Articles by others on the same topic (2)

A Cyclic Redundancy Check (CRC) is an error-detecting code used to identify accidental changes to raw data. It is commonly employed in digital networks and storage devices to ensure data integrity. Here’s a breakdown of the key aspects of CRC: ### Functionality: 1. **Error Detection**: CRCs are primarily used to detect errors in data transmission or storage. They help verify that the data received is the same as the data sent.