Editing Cyclic redundancy check (section)

== Introduction ==
CRCs are based on the theory of [[cyclic code|cyclic]] [[error-correcting code]]s. The use of [[systematic code|systematic]] cyclic codes, which encode messages by adding a fixed-length check value, for the purpose of error detection in communication networks, was first proposed by [[W. Wesley Peterson]] in 1961.<ref name="PetersonBrown1961">{{Cite journal
|last1 = Peterson |first1=W. W. |last2 =Brown |first2=D. T.
|date=January 1961
| title = Cyclic Codes for Error Detection
| journal = Proceedings of the IRE
| doi = 10.1109/JRPROC.1961.287814
| volume = 49
| issue = 1
| pages = 228–235
|s2cid=51666741 }}</ref>
Cyclic codes are not only simple to implement but have the benefit of being particularly well suited for the detection of [[burst error]]s: contiguous sequences of erroneous data symbols in messages. This is important because burst errors are common transmission errors in many [[communication channel]]s, including magnetic and optical storage devices. Typically an ''n''-bit CRC applied to a data block of arbitrary length will detect any single error burst not longer than ''n'' bits, and the fraction of all longer error bursts that it will detect is approximately {{nowrap|(1 − 2<sup>−''n''</sup>)}}.

Specification of a CRC code requires definition of a so-called [[generator polynomial]]. This polynomial becomes the [[divisor]] in a [[polynomial long division]], which takes the message as the [[division (mathematics)|dividend]] and in which the [[quotient]] is discarded and the [[remainder]] becomes the result.  The important caveat is that the polynomial [[coefficient]]s are calculated according to the arithmetic of a [[finite field]], so the addition operation can always be performed bitwise-parallel (there is no carry between digits).

In practice, all commonly used CRCs employ the finite field of two elements, [[GF(2)]]. The two elements are usually called 0 and 1, comfortably matching computer architecture.

A CRC is called an ''n''-bit CRC when its check value is ''n'' bits long. For a given ''n'', multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree ''n'', which means it has {{nowrap|''n'' + 1}} terms. In other words, the polynomial has a length of {{nowrap|''n'' + 1}}; its encoding requires {{nowrap|''n'' + 1}} bits. Note that most polynomial specifications either drop the [[Most significant bit|MSb]] or [[Least significant bit|LSb]], since they are always 1. The CRC and associated polynomial typically have a name of the form CRC-''n''-XXX as in the [[#table|table]] below.

The simplest error-detection system, the [[parity bit]], is in fact a 1-bit CRC: it uses the generator polynomial&nbsp;{{nowrap|''x'' + 1}} (two terms),<ref name=Ergen-2008>{{cite book|chapter=2.3.3 Error Detection Coding|title=Mobile Broadband|last=Ergen|first=Mustafa|publisher=[[Springer Nature|Springer]]|date=21 January 2008|pages=29–30|doi=10.1007/978-0-387-68192-4_2|isbn=978-0-387-68192-4}}</ref> and has the name CRC-1.