Cyclic redundancy check

related topics
{math, number, function}
{system, computer, user}

A cyclic redundancy check (CRC) or polynomial code checksum is a hash function designed to detect accidental changes to raw computer data, and is commonly used in digital networks and storage devices such as hard disk drives. A CRC-enabled device calculates a short, fixed-length binary sequence, known as the CRC code or just CRC, for each block of data and sends or stores them both together. When a block is read or received the device repeats the calculation; if the new CRC does not match the one calculated earlier, then the block contains a data error and the device may take corrective action such as rereading or requesting the block be sent again, otherwise the data is assumed to be error free (though, with some small probability, it may contain undetected errors; this is the fundamental nature of error-checking)[1].

CRCs are so called because the check (data verification) code is a redundancy (it adds zero information to the message) and the algorithm is based on cyclic codes. The term CRC may refer to the check code or to the function that calculates it, which accepts data streams of any length as input but always outputs a fixed-length code. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels. The CRC was invented by W. Wesley Peterson in 1961; the 32-bit polynomial used in the CRC function of Ethernet and many other standards is the work of several researchers and was published in 1975.

Contents

Introduction

A CRC is an error-detecting code. Its computation resembles a polynomial long division operation in which the quotient is discarded and the remainder becomes the result, with the important distinction that the polynomial coefficients are calculated according to the carry-less arithmetic of a finite field. The length of the remainder is always less than the length of the divisor (called the generator polynomial), which therefore determines how long the result can be. The definition of a particular CRC specifies the divisor to be used, among other things.

Full article ▸

related documents
Database normalization
IEEE 754-1985
Uniform Resource Identifier
SHA hash functions
Linear combination
Algebraic structure
E (mathematical constant)
Ideal class group
Sequence
Elliptic curve
Abstract interpretation
Arithmetic coding
Gaussian quadrature
Random variable
Natural transformation
Exclusive or
Binary relation
Pushdown automaton
Absolute convergence
Partition (number theory)
Galois theory
Ultrafilter
Axiom schema of replacement
Heine–Borel theorem
Presentation of a group
Complex analysis
Euclidean algorithm
Glossary of topology
Fuzzy logic
Countable set