CRCkoder

CRCkoder, or CRC codes, are error-detecting codes used to identify accidental changes to data in digital networks and storage systems. They are based on cyclic redundancy check theory, typically computed as the remainder of a polynomial division over GF(2) using a specified generator polynomial. A message is augmented with its CRC value so that, upon transmission or storage, the receiver can perform the same division and verify that the remainder is zero, indicating no detectable error.

CRCs come in different widths, commonly 8, 16, or 32 bits, and a variety of generator polynomials. Examples include CRC-8, CRC-16-IBM, CRC-16-CCITT, CRC-32 (IEEE 802.3), and CRC-32C (Castagnoli). The choice of polynomial and initial and final XOR values affects the error-detection properties, including which error patterns are most likely to be detected.

They are widely implemented in both hardware and software. CRCs are used in Ethernet frames (CRC-32), USB, SATA, and many other communication standards. They also appear in data formats and storage systems to verify integrity, such as PNG and various archive formats that employ CRC checksums.

Properties and limitations: CRCs are particularly effective at detecting common error types, including single-bit and burst errors up to the length of the CRC. However, they do not correct errors and cannot guarantee detection for all possible error patterns. The probability of an undetected random error is about 2^-n for an n-bit CRC, though certain structured errors may go undetected depending on the chosen polynomial.

Implementation notes: CRCs can be computed streamingly, using bitwise methods or with lookup tables to improve speed. Hardware implementations often use linear feedback shift registers.