# Cyclic Redundancy Check (CRC) ## What is CRC Cyclic Redundancy Check, commonly abbreviated as CRC, is a powerful error detection algorithm used extensively in digital networks and storage devices. It treats the data to be checked as a large binary polynomial and divides it by a predetermined generator polynomial. The remainder of this polynomial division, called the CRC value or frame check sequence, is appended to the data before transmission. The receiver performs the same division and checks whether the remainder is zero. A non-zero remainder indicates that the data was corrupted during transmission. ## Mathematical Basis CRC is based on polynomial arithmetic in modulo 2, which means that addition and subtraction are both equivalent to XOR and there are no carries. In this arithmetic, 1 plus 1 equals 0, not 2. The data to be transmitted is treated as a polynomial where each bit is a coefficient. A generator polynomial is chosen that has special mathematical properties ensuring good error detection capability. The CRC value is the remainder when the data polynomial, shifted left by the degree of the generator polynomial, is divided by the generator polynomial using modulo 2 division. ## CRC Calculation Process Suppose the data to be transmitted is 1101011011 and the generator polynomial is 10011. The degree of the generator polynomial is 4, so 4 zeros are appended to the data, giving 11010110110000. This augmented data is divided by the generator using modulo 2 division, which is essentially XOR applied repeatedly. The remainder after division is the CRC value, which is appended to the original data in place of the zeros. The receiver divides the received data, including the CRC, by the same generator polynomial. If the remainder is zero, the data was received without error. ## CRC Variants Different applications use CRC generators of different lengths. CRC-8 produces an 8-bit CRC and is used in some embedded systems. CRC-16 produces a 16-bit CRC and is used in storage devices and some communication protocols. CRC-32 produces a 32-bit CRC and is used in Ethernet and other networking protocols. CRC-32C is a variant used in iSCSI and SCTP. The longer the CRC, the stronger the error detection capability. ## Error Detection Capability CRC can detect all single-bit errors, all double-bit errors for any length message, all odd numbers of bit errors if the generator polynomial includes the factor x plus 1, all burst errors with a length equal to or less than the degree of the generator polynomial, and most burst errors longer than the generator polynomial with a very high probability of detection.