Cyclic Redundancy Check

Domain	Definition
Computing	Cyclic redundancy check (CRC or "cyclic redundancy code") A number derived from, and stored or transmitted with, a block of data in order to detect corruption. By recalculating the CRC and comparing it to the value originally transmitted, the receiver can detect some types of transmission errors. A CRC is more complicated than a checksum. It is calculated using division either using shifts and exclusive ORs or table lookup (modulo 256 or 65536). The CRC is "redundant" in that it adds no information. A single corrupted bit in the data will result in a one bit change in the calculated CRC but multiple corrupted bits may cancel each other out. CRCs treat blocks of input bits as coefficient-sets for polinomials. E.g., binary 10100000 implies the polynomial: 1x^7 + 0x^6 + 1x^5 + 0x^4 + 0x^3 + 0x^2 + 0x^1 + 0x^0. This is the "message polynomial". A second polynomial, with constant coefficients, is called the "generator polynomial". This is divided into the message polynomial, giving a quotient and remainder. The coefficients of the remainder form the bits of the final CRC. So, an order-33 generator polynomial is necessary to generate a 32-bit CRC. The exact bit-set used for the generator polynomial will naturally affect the CRC that is computed. Most CRC implementations seem to operate 8 bits at a time by building a table of 256 entries, representing all 256 possible 8-bit byte combinations, and determining the effect that each byte will have. CRCs are then computed using an input byte to select a 16- or 32-bit value from the table. This value is then used to update the CRC. Ethernet packets have a 32-bit CRC. Many disk formats include a CRC at some level. (1997-08-02). Source: The Free On-line Dictionary of Computing.
Math	(1) A method to detect and correct errors by adding bits derived from a block or string of bits to the block. (2) An algorithm to compute bits characteristic of a block based on the algebra of polynomials over the integers, modulo 2. (3) The characteristic bits of a block. (references)
Source: compiled by the editor from various references; see credits.

Specialty Definition: Cyclic redundancy check

A cyclic redundancy check (CRC) is the result of a type of calculation made upon data, such as network traffic or computer files, in order to detect errors in transmission or duplication. CRC's are calculated before and after transmission or duplication, and compared to confirm that they are the same. The most widely used CRC calculations are constructed in ways such that anticipated types of errors, e.g., due to noise in transmission channels, are almost always detected. CRC's cannot, however, be safely relied upon to verify data integrity--i.e., that no changes whatsoever have occurred--since through intentional modification it is possible to cause changes that will not be detected through the use of a CRC; cryptographic hash functions must be used to verify data integrity.

The essential mathematical operation in the calculation of a CRC is binary division, and the remainder from the division determines the CRC. The main portion of the algorithm in pseudocode is as follows:

shiftregister = initial value (commonly 0x0000... or 0xFFFF...) while bits remain in string: if MSB of shiftregister is set: shiftregister = (shiftregister leftshift 1) xor polynomial ("leftshift" assumes big-endian architecture) else: shiftregister = shiftregister leftshift 1 xor next bit from the string into LSB of shiftregister output shiftregister

Note: Use of a lookup table containing the CRC's of all 256 possible bytes allows for an eight-fold increase in the speed of the algorithm.

CRC types are often identified by "polynomial," which is the number used as the divisor (given in hexadecimal format). One of the most commonly encountered of the CRC types is that used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. It uses the polynomial 0x04C11DB7, and is known as "CRC-32."

CRC's are often referred to as "checksums," but such designations are not accurate since, technically, a checksum is calculated through addition, not division.

External Links and Resources

A Painless Guide to CRC Error Detection Algorithms
Understanding Cyclic Redundancy Check
Jacksum (a program with various message verification functions)

Frequency of Internet Keywords: Cyclic Redundancy Check

Modern Translation: Cyclic Redundancy Check

Language		Translations for "cyclic redundancy check"; alternative meanings/domain in parentheses.
Danish		cycklisk redundanscheck. (various references)

Dutch		cyclische-redundantiecontrole. (various references)

French		CRC, contrôle par redondance cyclique, contrôle de redondance cyclique, contrôle cyclique par redondance. (various references)

German		CRC-Prüfung (crc check), zyklischer Redundanztest, zyklischer Überflüssigkeitstest, zyklische Redundanzprüfung. (various references)

Greek		κυκλικός έλεγχος πλεονασμού. (various references)

Italian		controllo di ridondanza ciclica, controllo della ridondanza ciclica. (various references)

Pig Latin		ycliccay edundancyray eckchay

Portuguese		controlo por redundância cíclica, teste de redundância cíclico. (various references)

Spanish		VRC, verificación por redundancia cíclica. (various references)
Source: compiled by the editor from various translation references.

Expression	Frequency per Day
cyclic redundancy check	85
Source: compiled by the editor from various references; see credits.

Cyclic Redundancy Check

Definition: Cyclic Redundancy Check