Cyclic redundancy check (CRC): polynomial checksum for error detection

Basic idea and properties

Conceptually, CRC computation treats a sequence of message bits as the coefficients of a polynomial with binary coefficients (0 or 1). A fixed generator polynomial — chosen in advance and agreed by sender and receiver — acts as the divisor. The transmitter divides the augmented message polynomial by that divisor and appends the remainder as the CRC bits. On receipt, the same division should produce a zero remainder if the data and CRC arrived unchanged.

• Error detection: CRCs are excellent at detecting common accidental errors such as single-bit flips, double-bit errors, odd numbers of bit errors (with some generator choices), burst errors up to a certain length, and other patterns depending on the polynomial.
• Not cryptographic: CRCs are not designed to resist deliberate tampering; they are easy to forge if an attacker can modify both data and CRC.
• Variants: CRC families are named by the width of the remainder, e.g., CRC-8, CRC-16, CRC-32. Different standards specify different generator polynomials and initial/final processing rules.

How it is computed (conceptual steps)

1. Choose a generator polynomial of degree r; reserve r bits for the CRC.
2. Append r zero bits to the message and perform polynomial division (binary modulo-2 arithmetic) using the generator.
3. Take the remainder (r bits) and append them to the original message; this combined block is transmitted or stored.
4. The receiver divides the received block by the same generator. A non-zero remainder indicates an error.

In practice the division is performed with bitwise operations: shifts and exclusive-or (XOR). Implementations vary from simple bit-by-bit hardware linear-feedback shift registers (LFSRs) to high-performance software techniques such as table-driven lookups and slicing-by-n methods.

History and standardization

The mathematical foundations of cyclic codes and polynomial representations were developed in the mid-20th century and adopted quickly in digital systems as electronic communications expanded. Over time, particular CRC variants became standardized for well-known technologies: for example, specific 16-bit and 32-bit CRCs are specified for certain network protocols, file formats, and storage media. The choice of polynomial and processing rules is an important part of such standards because it determines which error patterns the CRC will detect reliably.

Common uses and examples

• Network frames: Many link-layer protocols append a CRC to frames so hardware can quickly detect transmission errors (for example, Ethernet frames include a 32-bit CRC in many implementations).
• File and archive formats: Data formats such as PNG and ZIP use CRCs to verify the integrity of compressed data blocks or archives.
• Storage devices: Disk controllers and file systems use CRC-like checks to detect corruption on media or in memory.
• Embedded and industrial systems: Small CRCs (e.g., 8-bit or 16-bit) are used where minimal overhead is required.

Implementation notes and limitations

Implementations must agree on several details beyond the polynomial itself: initial register values, whether input and output bits are reflected (bit-order reversed), and final XOR values. These parameters affect compatibility: the same polynomial with different processing rules yields incompatible CRCs. While CRCs are highly effective at catching accidental corruption, they can be beaten by deliberately crafted modifications; for authenticity or strong integrity guarantees, cryptographic hashes or message authentication codes should be used instead.

For deeper technical background, see general material on checksums and error detection, resources describing polynomial arithmetic over GF(2), and protocol-specific documentation such as guides for network and file-format CRC use at standardization or technical reference sites.

Notable facts: hardware CRC engines can compute checks in parallel with bit transfer and are widely implemented in NICs and storage controllers; software libraries offer optimized routines for different CPU architectures. Choosing the right CRC width and polynomial balances overhead and the level of error detection required for a given application.