View source for Computation of cyclic redundancy checks

{{short description|Overview of the computation of cyclic redundancy checks}}

Computation of a [[Cyclic redundancy check|cyclic redundancy check]] is derived from the mathematics of [[Mathematics of cyclic redundancy checks|polynomial division, modulo two]]. In practice, it resembles [[Long division|long division]] of the [[Binary code|binary]] message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that [[Exclusive or|exclusive or]] operations replace subtractions.  Division of this type is efficiently realised in hardware by a modified [[Shift register|shift register]],<ref>{{cite book 
| first1=Elena 
| last1=Dubrova
| first2=Shohreh Sharif
| last2=Mansouri
| title=2012 IEEE 42nd International Symposium on Multiple-Valued Logic
| chapter=A BDD-Based Approach to Constructing LFSRS for Parallel CRC Encoding
| chapter-url=http://doi.ieeecomputersociety.org/10.1109/ISMVL.2012.20
| pages=128–133  
| date=May 2012
| doi=10.1109/ISMVL.2012.20 
| isbn=978-0-7695-4673-5| s2cid=27306826 
}}</ref> and in software by a series of equivalent [[Algorithm|algorithm]]s, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated<ref name="williams96">{{cite web
| url=http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
| title=A Painless Guide to CRC Error Detection Algorithms V3.00
| last=Williams
| first=Ross N.
| date=1996-09-24
| access-date=2016-02-16
| archive-url=https://web.archive.org/web/20060927004051/http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
| archive-date=2006-09-27
| url-status=dead
}}</ref>) through [[Byte|byte]]-wise parallelism and [[Space–time tradeoff|space–time tradeoff]]s.

[[Image:CRC8-gen.gif|thumb|right|380 px|Example of generating an 8-bit [[Cyclic redundancy check|CRC]]. The generator is a Galois-type [[Linear-feedback shift register|shift register]] with XOR gates placed according to powers (white numbers) of ''x'' in the generator polynomial. The message stream may be any length. After it has been shifted through the register, followed by 8 zeroes, the result in the register is the checksum.]]
[[Image:CRC8-rx.gif|thumb|380 px|Checking received data with checksum. The received message is shifted through the same register as used in the generator, but the received checksum is attached to it instead of zeroes. Correct data yields the all-zeroes result; a corrupted bit in either the message or checksum would give a different result, warning that an error has occurred.]]

Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final Exclusive-Or step and, most critically, a bit ordering ([[Endianness|endianness]]).  As a result, the code seen in practice deviates confusingly from "pure" division,<ref name="williams96"/> and the register may shift left or right.

== Example ==
As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the [[ASCII]] character "W", which is binary 01010111<sub>2</sub>, decimal 87<sub>10</sub>, or [[Hexadecimal|hexadecimal]] 57<sub>16</sub>.  For illustration, we will use the CRC-8-ATM ([[CRC-based framing|HEC]]) polynomial <math>x^8+x^2+x+1</math>.  Writing the first bit transmitted (the coefficient of the highest power of <math>x</math>) on the left, this corresponds to the 9-bit string "100000111".

The byte value 57<sub>16</sub> can be transmitted in two different orders, depending on the bit ordering convention used.  Each one generates a different message polynomial <math>M(x)</math>.  Msbit-first, this is <math>x^6+x^4+x^2+x+1</math> = 01010111, while lsbit-first, it is <math>x^7+x^6+x^5+x^3+x</math> = 11101010.  These can then be multiplied by <math>x^8</math> to produce two 16-bit message polynomials <math>x^8 M(x)</math>.

Computing the remainder then consists of subtracting multiples of the generator polynomial <math>G(x)</math>.  This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions [[Carry (arithmetic)|borrow]] "from infinity" instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.

{| border="1" style="margin:auto;"
! Most-significant bit first !! Least-significant bit first
|-
|
{|
|-
| || style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0||0||0||0||0||0||0
|-
|−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0||0||0||0||0||0
|-
| ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0||0||0||0||0
|-
| || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0||0||0||0
|-
| || || ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0||0||0
|-
| || || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0||0
|-
| || || || || ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0||0||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0
|-
| || || || || || ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0||0||0||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1||0
|-
| || || || || || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0||0||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0
|}
||
{| border="0"
|-
| || style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0||0||0||0||0||0||0
|-
|−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0||0||0||0||0||0
|-
| ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1||0||0||0||0||0||0
|-
| || ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1||0||0||0||0||0
|-
| || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0||0||0
|-
| || || || ||−|| style="background:#cfc;"|1|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|0|| style="background:#cfc;"|1|| style="background:#cfc;"|1|| style="background:#cfc;"|1
|-
|=||0||0||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1||0||0||0
|-
| || || || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0||0||0
|-
| || || || || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0||0||0||0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0||0
|-
| || || || || || || ||−|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0|| style="background:#fcf;"|0
|-
|=||0||0||0||0||0||0||0||0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|1|| style="background:LightBlue;"|1|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0|| style="background:LightBlue;"|0
|}
|}
Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero; at the end, a group which is unchanged from the original; and a blue shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left.

In the msbit-first example, the remainder polynomial is <math>x^7+x^5+x</math>.  Converting to a hexadecimal number using the convention that the highest power of ''x'' is the msbit; this is A2<sub>16</sub>.  In the lsbit-first, the remainder is <math>x^7+x^4+x^3</math>.  Converting to hexadecimal using the convention that the highest power of ''x'' is the lsbit, this is 19<sub>16</sub>.

== Implementation ==
Writing out the full message at each step, as done in the example above, is very tedious.  Efficient implementations
use an <math>n</math>-bit [[Shift register|shift register]] to hold only the interesting bits.  Multiplying the polynomial by <math>x</math> is equivalent to shifting the register by one place, as the coefficients do not change in value but only move up to the next term of the polynomial.

Here is a first draft of some [[Pseudocode|pseudocode]] for computing an ''n''-bit CRC.  It uses a contrived [[Object composition|composite data type]] for polynomials, where <code>''x''</code> is not an integer variable, but a constructor generating a ''Polynomial'' [[Object (computer science)|object]] that can be added, multiplied and exponentiated.  To <code>'''xor'''</code> two polynomials is to add them, modulo two; that is, to exclusive OR the coefficients of each matching term from both polynomials.

 '''function''' crc(''bit array'' bitString[1..len], ''int'' len) {
     remainderPolynomial := '''polynomialForm'''(bitString[1..n])   ''// First n bits of the message''
     ''// A popular variant complements remainderPolynomial here; see {{slink||Preset to −1}} below''
     '''for''' i '''from''' 1 '''to''' len {
         remainderPolynomial := remainderPolynomial * ''x'' + bitString[i+n] * ''x''<sup>0</sup>   ''// Define bitString[k]=0 for k>len''
         '''if''' coefficient of ''x''<sup>n</sup> of remainderPolynomial = 1 {
             remainderPolynomial := remainderPolynomial '''xor''' generatorPolynomial
         }
     }
     ''// A popular variant complements remainderPolynomial here; see {{slink||Post-invert}} below''
     '''return''' remainderPolynomial
 }
:'''Code fragment 1: Simple polynomial division'''

Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; the input <code>bitString</code> is already in the form of a bit array, and the <code>remainderPolynomial</code> is manipulated in terms of polynomial operations; the multiplication by <math>x</math> could be a left or right shift, and the addition of <code>bitString[i+n]</code> is done to the <math>x^0</math> coefficient, which could be the right or left end of the register.

This code has two disadvantages.  First, it actually requires an ''n''+1-bit register to hold the <code>remainderPolynomial</code> so that the <math>x^n</math> coefficient can be tested. More significantly, it requires the <code>bitString</code> to be padded with ''n'' zero bits.

The first problem can be solved by testing the <math>x^{n-1}</math> coefficient of the <code>remainderPolynomial</code> before it is multiplied by <math>x</math>.

The second problem could be solved by doing the last ''n'' iterations differently, but there is a more subtle optimization which is used universally, in both hardware and software implementations.

Because the XOR operation used to subtract the generator polynomial from the message is commutative and associative, it does not matter in what order the various inputs are combined into the <code>remainderPolynomial</code>.  And specifically, a given bit of the <code>bitString</code> does not need to be added to the <code>remainderPolynomial</code> until the very last instant when it is tested to determine whether to <code>xor</code> with the <code>generatorPolynomial</code>.

This eliminates the need to preload the <code>remainderPolynomial</code> with the first ''n'' bits of the message, as well:

 '''function''' crc(''bit array'' bitString[1..len], ''int'' len) {
     remainderPolynomial := 0
     ''// A popular variant complements remainderPolynomial here; see {{slink||Preset to −1}} below''
     '''for''' i '''from''' 1 '''to''' len {
         remainderPolynomial := remainderPolynomial '''xor''' (bitstring[i] * ''x''<sup>n−1</sup>)
         '''if''' (coefficient of ''x''<sup>n−1</sup> of remainderPolynomial) = 1 {
             remainderPolynomial := (remainderPolynomial * ''x'') '''xor''' generatorPolynomial
         } '''else''' {
             remainderPolynomial := (remainderPolynomial * ''x'')
         }
     }
     ''// A popular variant complements remainderPolynomial here; see {{slink||Post-invert}} below''
     '''return''' remainderPolynomial
 }
:'''Code fragment 2: Polynomial division with deferred message XORing'''

This is the standard bit-at-a-time hardware CRC implementation, and is well worthy of study; once you understand why this computes exactly the same result as the first version, the remaining optimizations are quite straightforward.  If <code>remainderPolynomial</code> is only ''n'' bits long, then the <math>x^n</math> coefficients of it and of <code>generatorPolynomial</code> are simply discarded.  This is the reason that you will usually see CRC polynomials written in binary with the leading coefficient omitted.

In software, it is convenient to note that while one may delay the <code>xor</code> of each bit until the very last moment, it is also possible to do it earlier.  It is usually convenient to perform the <code>xor</code> a [[Byte|byte]] at a time, even in a bit-at-a-time implementation like this:

 '''function''' crc(''byte array'' string[1..len], ''int'' len) {
     remainderPolynomial := 0
     ''// A popular variant complements remainderPolynomial here; see {{slink||Preset to −1}} below''
     '''for''' i '''from''' 1 '''to''' len {
         remainderPolynomial := remainderPolynomial '''xor''' '''polynomialForm'''(string[i]) * x<sup>n−8</sup>
         '''for''' j '''from''' 1 '''to''' 8 {    ''// Assuming 8 bits per byte''
             '''if''' coefficient of ''x''<sup>n−1</sup> of remainderPolynomial = 1 {
                 remainderPolynomial := (remainderPolynomial * ''x'') '''xor''' generatorPolynomial
             } '''else''' {
                 remainderPolynomial := (remainderPolynomial * ''x'')
             }
         }
     }
     ''// A popular variant complements remainderPolynomial here; see {{slink||Post-invert}} below''
     '''return''' remainderPolynomial
 }
:'''Code fragment 3: Polynomial division with bytewise message XORing'''

This is usually the most compact software implementation, used in microcontrollers when space is at a premium over speed.

== Bit ordering (endianness) ==
When implemented in [[Bit-serial architecture|bit serial]] hardware, the generator polynomial uniquely describes the bit assignment; the first bit transmitted is always the coefficient of the highest power of <math>x</math>, and the last <math>n</math> bits transmitted are the CRC remainder <math>R(x)</math>, starting with the coefficient of <math>x^{n-1}</math> and ending with the coefficient of <math>x^0</math>, a.k.a. the coefficient of 1.

However, when bits are processed a [[Byte|byte]] at a time, such as when using parallel transmission, byte framing as in 8B/10B encoding or [[RS-232]]-style [[Asynchronous serial communication|asynchronous serial communication]], or when implementing a CRC in [[Software|software]], it is necessary to specify the bit ordering (endianness) of the data; which bit in each byte is considered "first" and will be the coefficient of the higher power of <math>x</math>.

If the data is destined for [[Serial communication|serial communication]], it is best to use the bit ordering the data will ultimately be sent in.  This is because a CRC's ability to detect [[Burst error|burst error]]s is based on proximity in the message polynomial <math>M(x)</math>; if adjacent polynomial terms are not transmitted sequentially, a physical error burst of one length may be seen as a longer burst due to the rearrangement of bits.

For example, both [[IEEE 802]] ([[Ethernet|ethernet]]) and [[RS-232]] ([[Serial port|serial port]]) standards specify least-significant bit first (little-endian) transmission, so a software CRC implementation to protect data sent across such a link should map the least significant bits in each byte to coefficients of the highest powers of <math>x</math>.  On the other hand, [[Floppy disk|floppy disk]]s and most hard drives write the most significant bit of each byte first.

The lsbit-first CRC is slightly simpler to implement in software, so is somewhat more commonly seen, but many programmers find the msbit-first bit ordering easier to follow.  Thus, for example, the XMODEM-CRC extension, an early use of CRCs in software, uses an msbit-first CRC.

So far, the pseudocode has avoided specifying the ordering of bits within bytes by describing shifts in the pseudocode as multiplications by <math>x</math> and writing explicit conversions from binary to polynomial form.  In practice, the CRC is held in a standard binary register using a particular bit-ordering convention.  In msbit-first form, the most significant binary bits will be sent first and so contain the higher-order polynomial coefficients, while in lsbit-first form, the least-significant binary bits contain the higher-order coefficients.  The above pseudocode can be written in both forms.  For concreteness, this uses the 16-bit  CRC-16-CCITT polynomial <math>x^{16} + x^{12} + x^5 + 1</math>:

 ''// Most significant bit first (big-endian)''
 ''// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021''
 '''function''' crc(''byte array'' string[1..len], ''int'' len) {
     rem := 0
     ''// A popular variant complements rem here''
     '''for''' i '''from''' 1 '''to''' len {
         rem  := rem '''xor''' (string[i] '''leftShift''' (n-8))   ''// n = 16 in this example''
         '''for''' j '''from''' 1 '''to''' 8 {   ''// Assuming 8 bits per byte''
             '''if''' rem '''and''' 0x8000 {   ''// if leftmost (most significant) bit is set''
                 rem  := (rem '''leftShift''' 1) '''xor''' 0x1021
             } '''else''' {
                 rem  := rem '''leftShift''' 1
             }
             rem  := rem '''and''' 0xffff      // Trim remainder to 16 bits
         }
     }
     ''// A popular variant complements rem here''
     '''return''' rem
 }
:'''Code fragment 4: Shift register based division, MSB first'''

 ''// Least significant bit first (little-endian)''
 ''// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408''
 '''function''' crc(''byte array'' string[1..len], ''int'' len) {
     rem  := 0
     ''// A popular variant complements rem here''
     '''for''' i '''from''' 1 '''to''' len {
         rem  := rem '''xor''' string[i]
         '''for''' j '''from''' 1 '''to''' 8 {   ''// Assuming 8 bits per byte''
             '''if''' rem '''and''' 0x0001 {   ''// if rightmost (most significant) bit is set''
                 rem  := (rem '''rightShift''' 1) '''xor''' 0x8408
             } '''else''' {
                 rem  := rem '''rightShift''' 1
             }
         }
     }
     ''// A popular variant complements rem here''
     '''return''' rem
 }
:'''Code fragment 5: Shift register based division, LSB first'''

Note that the lsbit-first form avoids the need to shift <code>string[i]</code> before the <code>xor</code>.  In either case, be sure to transmit the bytes of the CRC in the order that matches your chosen bit-ordering convention.

== Multi-bit computation ==

=== Sarwate algorithm (single lookup table) ===
Another common optimization uses a [[Lookup table|lookup table]] indexed by highest order coefficients of <code>rem</code> to process more than one bit of dividend per iteration.<ref>{{cite journal |first=Dilip V. |last=Sarwate |title=Computation of Cyclic Redundancy Checks via Table Look-Up |journal=[[Communications of the ACM]] |volume=31 |issue=8 |date=August 1998 |pages=1008–1013 |doi=10.1145/63030.63037|s2cid=5363350 |doi-access=free }}</ref>  Most commonly, a 256-entry lookup table is used, replacing the body of the outer loop (over <code>i</code>) with:

 // Msbit-first
 rem = (rem '''leftShift''' 8) '''xor''' big_endian_table[string[i] '''xor''' ((leftmost 8 bits of rem) '''rightShift''' (n-8))]
 // Lsbit-first
 rem = (rem '''rightShift''' 8) '''xor''' little_endian_table[string[i] '''xor''' (rightmost 8 bits of rem)]
:'''Code fragment 6: Cores of table based division'''

One of the most commonly encountered CRC algorithms is known as '''CRC-32''', used by (among others) [[Ethernet]], FDDI, [[ZIP (file format)|ZIP]] and other archive formats, and [[Portable Network Graphics|PNG]] image format.  Its polynomial can be written msbit-first as 0x04C11DB7, or lsbit-first as 0xEDB88320. The W3C webpage on [[Portable Network Graphics|PNG]] includes an appendix with a short and simple table-driven implementation in C of CRC-32.<ref>{{cite web
| url=https://www.w3.org/TR/PNG/#D-CRCAppendix 
| title=Portable Network Graphics (PNG) Specification (Second Edition): Annex D, Sample Cyclic Redundancy Code implementation
| date=2003-11-10
| publisher=W3C
| access-date = 2016-02-16}}</ref> You will note that the code corresponds to the lsbit-first byte-at-a-time pseudocode presented here, and the table is generated using the bit-at-a-time code.

Using a 256-entry table is usually most convenient, but other sizes can be used.  In small microcontrollers, using a 16-entry table to process four bits at a time gives a useful speed improvement while keeping the table small.  On computers with ample storage, a {{val|65536}}-entry table can be used to process 16 bits at a time.

==== Generating the tables ====

The software to generate the tables is so small and fast that it is usually faster to compute them on program startup than to load precomputed tables from storage.  One popular technique is to use the bit-at-a-time code 256 times to generate the CRCs of the 256 possible 8-bit bytes.  However, this can be optimized significantly by taking advantage of the property that <code>table[i '''xor''' j] == table[i] '''xor''' table[j]</code>.  Only the table entries corresponding to powers of two need to be computed directly.

In the following example code, <code>crc</code> holds the value of <code>table[i]</code>:

 big_endian_table[0] := 0
 crc := 0x8000 // ''Assuming a 16-bit polynomial''
 i := 1
 '''do''' {
     '''if''' crc '''and''' 0x8000 {
         crc := (crc '''leftShift''' 1) '''xor''' 0x1021 // ''The CRC polynomial''
     } '''else''' {
         crc := crc '''leftShift''' 1
     }
     // crc ''is the value of'' big_endian_table[i]''; let'' j ''iterate over the already-initialized entries''
     '''for''' j '''from''' 0 '''to''' i−1 {
         big_endian_table[i + j] := crc '''xor''' big_endian_table[j];
     }
     i := i '''leftshift''' 1
 } '''while''' i < 256
:'''Code fragment 7: Byte-at-a-time CRC table generation, MSB first'''

 little_endian_table[0] := 0
 crc := 1;
 i := 128
 '''do''' {
     '''if''' crc '''and''' 1 {
         crc := (crc '''rightShift''' 1) '''xor''' 0x8408 // ''The CRC polynomial''
     } '''else''' {
         crc := crc '''rightShift''' 1
     }
     // crc ''is the value of'' little_endian_table[i]''; let'' j ''iterate over the already-initialized entries''
     '''for''' j '''from''' 0 '''to''' 255 '''by''' 2 &times; i {
         little_endian_table[i + j] := crc '''xor''' little_endian_table[j];
     }
     i := i '''rightshift''' 1
 } '''while''' i > 0
:'''Code fragment 8: Byte-at-a-time CRC table generation, LSB first'''

In these code samples, the table index <code>i + j</code> is equivalent to <code>i '''xor''' j</code>; you may use whichever form is more convenient.

==== CRC-32 algorithm ====
This is a practical algorithm for the CRC-32 variant of CRC.<ref>{{cite web|url=https://msdn.microsoft.com/en-us/library/dd905031.aspx|title=[MS-ABS]: 32-Bit CRC Algorithm|website=msdn.microsoft.com|access-date=4 November 2017|archive-date=7 November 2017|archive-url=https://web.archive.org/web/20171107004846/https://msdn.microsoft.com/en-us/library/dd905031.aspx|url-status=live}}</ref> The CRCTable is a [[Memoization|memoization]] of a calculation that would have to be repeated for each byte of the message ({{section link|Computation of cyclic redundancy checks|Multi-bit computation}}).

 <span style="color:green;">'''Function'''</span> CRC32
    <span style="color:blue;">'''Input:'''</span>
       data:  Bytes     <span style="color:green;">'''// Array of bytes'''</span>
    <span style="color:blue;">'''Output:'''</span>
       crc32: UInt32    <span style="color:green;">'''// 32-bit unsigned CRC-32 value'''</span><br>
 <span style="color:green;">'''// Initialize CRC-32 to starting value'''</span>
 crc32 &larr; 0xFFFFFFFF<br>
 <span style="color:blue;">'''for each'''</span> byte <span style="color:blue;">'''in'''</span> data <span style="color:blue;">'''do'''</span>
    nLookupIndex &larr; (crc32 xor byte) and 0xFF
    crc32 &larr; (crc32 shr 8) xor CRCTable[nLookupIndex]  <span style="color:green;">'''// CRCTable is an array of 256 32-bit constants'''</span><br>
 <span style="color:green;">'''// Finalize the CRC-32 value by inverting all the bits'''</span>
 crc32 &larr; crc32 xor 0xFFFFFFFF
 <span style="color:blue;">'''return'''</span> crc32


In C, the algorithm looks as such:
<source lang="c">
#include <inttypes.h> // uint32_t, uint8_t

uint32_t CRC32(const uint8_t data[], size_t data_length) {
	uint32_t crc32 = 0xFFFFFFFFu;
	
	for (size_t i = 0; i < data_length; i++) {
		const uint32_t lookupIndex = (crc32 ^ data[i]) & 0xff;
		crc32 = (crc32 >> 8) ^ CRCTable[lookupIndex];  // CRCTable is an array of 256 32-bit constants
	}
	
	// Finalize the CRC-32 value by inverting all the bits
	crc32 ^= 0xFFFFFFFFu;
	return crc32;
}
</source>

=== Byte-Slicing using multiple tables ===

There exists a slice-by-N (typically slice-by-8 for CRC32; N ≤ 64) algorithm that usually doubles or triples the performance compared to the Sarwate algorithm. Instead of reading 8 bits at a time, the algorithm reads 8N bits at a time. Doing so maximizes performance on superscalar processors.<ref>{{cite book |doi=10.1109/ISCC.2005.18 |url=https://static.aminer.org/pdf/PDF/000/432/446/a_systematic_approach_to_building_high_performance_software_based_crc.pdf |chapter=A Systematic Approach to Building High Performance Software-Based CRC Generators |title=10th IEEE Symposium on Computers and Communications (ISCC'05) |year=2005 |last1=Kounavis |first1=M.E. |last2=Berry |first2=F.L. |pages=855–862 |isbn=0-7695-2373-0 |s2cid=10308354 }}</ref><ref>{{cite journal |title=Novel Table Lookup-Based Algorithms for High-Performance CRC Generation |journal=IEEE Transactions on Computers |date=November 2008 |volume=57 |issue=11 |pages=1550–1560 |doi=10.1109/TC.2008.85 |first1=Frank L. |last1=Berry |first2=Michael E. |last2=Kounavis|s2cid=206624854 }}</ref><ref>{{cite tech report |title=High Octane CRC Generation with the Intel Slicing-by-8 Algorithm |publisher=[[Company:Intel|Intel]] |url=http://download.intel.com:80/technology/comms/perfnet/download/slicing-by-8.pdf |archive-url=https://web.archive.org/web/20120722193753/http://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf |archive-date=2012-07-22 |url-status=dead }}</ref><ref>{{Cite web|url=https://www.kernel.org/doc/Documentation/crc32.txt|title=Brief tutorial on CRC computation|work=The Linux Kernel Archives}}</ref>

It is unclear who actually invented the algorithm.<ref>{{cite web |title=Who invented the slicing-by-N CRC32 algorithm? |first=Abhijit |last=Menon-Sen |date=2017-01-20 |url=http://toroid.org/crc32-slicing-by-N-paper}}</ref>

=== Parallel computation without table ===

Parallel update for a byte or a word at a time can also be done explicitly, without a table.<ref>{{cite newsgroup
  | title = Re: 8051 and CRC-CCITT
  | author = Jon Buller
  | date = 1996-03-15
  | newsgroup = comp.arch.embedded
  | message-id= 31498ED0.7C0A@nortel.com
  | url = https://groups.google.com/d/msg/comp.arch.embedded/fvQ7yM5F6ys/3xcgqF3Kqc4J
  | access-date = 2016-02-16
}}</ref> This is normally used in high-speed hardware implementations.  For each bit an equation is solved after 8 bits have been shifted in. The following tables list the equations for some commonly used polynomials, using following symbols:

{| class="wikitable"
|-
| c<sub>i</sub> || CRC bit 7…0 (or 15…0) before update
|-
| r<sub>i</sub> || CRC bit 7…0 (or 15…0) after update
|-
| d<sub>i</sub> || input data bit 7…0
|-
| e<sub>i</sub> = d<sub>i</sub> + c<sub>i</sub>
| e<sub>p</sub> = e<sub>7</sub> + e<sub>6</sub> + … + e<sub>1</sub> + e<sub>0</sub> ''(parity bit)''
|-
| s<sub>i</sub> = d<sub>i</sub> + c<sub>i+8</sub>
| s<sub>p</sub> = s<sub>7</sub> + s<sub>6</sub> + … + s<sub>1</sub> + s<sub>0</sub> ''(parity bit)''
|}

{| class="wikitable"
|+ Bit-wise update equations for some CRC-8 polynomials after 8 bits have been shifted in
! Polynomial:
| (''x''<sup>7</sup> + ''x''<sup>3</sup> + 1) &times; ''x'' ''(left-shifted CRC-7-CCITT)''
| ''x''<sup>8</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + 1 ''(CRC-8-Dallas/Maxim)''
|-
! Coefficients:
| 0x12 = (0x09 << 1) ''([[Most significant bit|MSBF]]/normal)''
| 0x8c ''([[Least significant bit|LSBF]]/reverse)''
|-
|
 r<sub>0 </sub> &larr;
 r<sub>1 </sub> &larr;
 r<sub>2 </sub> &larr;
 r<sub>3 </sub> &larr;
 r<sub>4 </sub> &larr;
 r<sub>5 </sub> &larr;
 r<sub>6 </sub> &larr;
 r<sub>7 </sub> &larr;
|
 0
 e<sub>0</sub> + e<sub>4</sub> + e<sub>7</sub>
 e<sub>1</sub> + e<sub>5</sub>
 e<sub>2</sub> + e<sub>6</sub>
 e<sub>3</sub> + e<sub>7</sub>    <sub> </sub> + e<sub>0</sub> + e<sub>4</sub> + e<sub>7</sub>
 e<sub>4</sub>    <sub> </sub>    <sub> </sub> + e<sub>1</sub> + e<sub>5</sub>
 e<sub>5</sub>    <sub> </sub>    <sub> </sub> + e<sub>2</sub> + e<sub>6</sub>
 e<sub>6</sub>    <sub> </sub>    <sub> </sub> + e<sub>3</sub> + e<sub>7</sub>
|
 e<sub>0</sub>    <sub> </sub>    <sub> </sub> + e<sub>4</sub> + e<sub>1</sub> + e<sub>0</sub>    <sub> </sub>   + e<sub>5</sub> + e<sub>2</sub> + e<sub>1</sub>
 e<sub>1</sub>    <sub> </sub>    <sub> </sub> + e<sub>5</sub> + e<sub>2</sub> + e<sub>1</sub>    <sub> </sub>   + e<sub>6</sub> + e<sub>3</sub> + e<sub>2</sub> + e<sub>0</sub>
 e<sub>2</sub>    <sub> </sub>    <sub> </sub> + e<sub>6</sub> + e<sub>3</sub> + e<sub>2</sub> + e<sub>0</sub>   + e<sub>7</sub> + e<sub>4</sub> + e<sub>3</sub> + e<sub>1</sub>
 e<sub>3</sub> + e<sub>0</sub>    <sub> </sub> + e<sub>7</sub> + e<sub>4</sub> + e<sub>3</sub> + e<sub>1</sub>
 e<sub>4</sub> + e<sub>1</sub> + e<sub>0</sub>
 e<sub>5</sub> + e<sub>2</sub> + e<sub>1</sub>
 e<sub>6</sub> + e<sub>3</sub> + e<sub>2</sub> + e<sub>0</sub>
 e<sub>7</sub> + e<sub>4</sub> + e<sub>3</sub> + e<sub>1</sub>
|-valign="top"
! C code<br />fragments:
|<source lang="c">
 uint8_t c, d, e, f, r;
 …
 e = c ^ d;
 f = e ^ (e >> 4) ^ (e >> 7);
 r =     (f << 1) ^ (f << 4);</source>
|<source lang="c">
 uint8_t c, d, e, f, r;
 …
 e = c ^ d;
 f = e ^ (e << 3) ^ (e << 4) ^ (e << 6);
 r = f ^ (f >> 4) ^ (f >> 5);</source>
|}

{| class="wikitable"
|+ Bit-wise update equations for some CRC-16 polynomials after 8 bits have been shifted in
! Polynomial:
| colspan="2" | ''x''<sup>16</sup> + ''x''<sup>12</sup> + ''x''<sup>5</sup> + 1 ''(CRC-16-CCITT)''
| colspan="2" | ''x''<sup>16</sup> + ''x''<sup>15</sup> + ''x''<sup>2</sup> + 1 ''(CRC-16-ANSI)''
|-
! Coefficients:
| 0x1021 ''(MSBF/normal)''
| 0x8408 ''(LSBF/reverse)''
| 0x8005 ''(MSBF/normal)''
| 0xa001 ''(LSBF/reverse)''
|-
|
 r<sub>0 </sub> &larr;
 r<sub>1 </sub> &larr;
 r<sub>2 </sub> &larr;
 r<sub>3 </sub> &larr;
 r<sub>4 </sub> &larr;
 r<sub>5 </sub> &larr;
 r<sub>6 </sub> &larr;
 r<sub>7 </sub> &larr;
 r<sub>8 </sub> &larr;
 r<sub>9 </sub> &larr;
 r<sub>10</sub> &larr;
 r<sub>11</sub> &larr;
 r<sub>12</sub> &larr;
 r<sub>13</sub> &larr;
 r<sub>14</sub> &larr;
 r<sub>15</sub> &larr;
|
 s<sub>4</sub> + s<sub>0</sub>
 s<sub>5</sub> + s<sub>1</sub>
 s<sub>6</sub> + s<sub>2</sub>
 s<sub>7</sub> + s<sub>3</sub>
  <sub> </sub>   s<sub>4</sub>
  <sub> </sub>   s<sub>5</sub>  + s<sub>4</sub> + s<sub>0</sub>
  <sub> </sub>   s<sub>6</sub>  + s<sub>5</sub> + s<sub>1</sub>
  <sub> </sub>   s<sub>7</sub>  + s<sub>6</sub> + s<sub>2</sub>
 c<sub>0</sub>    <sub> </sub>  + s<sub>7</sub> + s<sub>3</sub>
 c<sub>1</sub>    <sub> </sub>     <sub> </sub> + s<sub>4</sub>
 c<sub>2</sub>    <sub> </sub>     <sub> </sub> + s<sub>5</sub>
 c<sub>3</sub>    <sub> </sub>     <sub> </sub> + s<sub>6</sub>
 c<sub>4</sub>    <sub> </sub>     <sub> </sub> + s<sub>7</sub>  + s<sub>4</sub> + s<sub>0</sub>
 c<sub>5</sub>    <sub> </sub>     <sub> </sub>    <sub> </sub>  + s<sub>5</sub> + s<sub>1</sub>
 c<sub>6</sub>    <sub> </sub>     <sub> </sub>    <sub> </sub>  + s<sub>6</sub> + s<sub>2</sub>
 c<sub>7</sub>    <sub> </sub>     <sub> </sub>    <sub> </sub>  + s<sub>7</sub> + s<sub>3</sub>
|
 c<sub>8 </sub>   <sub> </sub>     <sub> </sub>  + e<sub>4</sub> + e<sub>0</sub>
 c<sub>9 </sub>   <sub> </sub>     <sub> </sub>  + e<sub>5</sub> + e<sub>1</sub>
 c<sub>10</sub>   <sub> </sub>     <sub> </sub>  + e<sub>6</sub> + e<sub>2</sub>
 c<sub>11</sub>   <sub> </sub>  + e<sub>0</sub>  + e<sub>7</sub> + e<sub>3</sub>
 c<sub>12</sub>   <sub> </sub>  + e<sub>1</sub>
 c<sub>13</sub>   <sub> </sub>  + e<sub>2</sub>
 c<sub>14</sub>   <sub> </sub>  + e<sub>3</sub>
 c<sub>15</sub>   <sub> </sub>  + e<sub>4</sub> + e<sub>0</sub>
  <sub>  </sub>  e<sub>0</sub>  + e<sub>5</sub> + e<sub>1</sub>
  <sub>  </sub>  e<sub>1</sub>  + e<sub>6</sub> + e<sub>2</sub>
  <sub>  </sub>  e<sub>2</sub>  + e<sub>7</sub> + e<sub>3</sub>
  <sub>  </sub>  e<sub>3</sub>
  <sub>  </sub>  e<sub>4</sub> + e<sub>0</sub>
  <sub>  </sub>  e<sub>5</sub> + e<sub>1</sub>
  <sub>  </sub>  e<sub>6</sub> + e<sub>2</sub>
  <sub>  </sub>  e<sub>7</sub> + e<sub>3</sub>
|
  <sub> </sub>    <sub> </sub>   s<sub>p</sub>
  <sub> </sub>    <sub> </sub>   s<sub>0</sub> + s<sub>p</sub>
  <sub> </sub>    <sub> </sub>   s<sub>1</sub> + s<sub>0</sub>
  <sub> </sub>    <sub> </sub>   s<sub>2</sub> + s<sub>1</sub>
  <sub> </sub>    <sub> </sub>   s<sub>3</sub> + s<sub>2</sub>
  <sub> </sub>    <sub> </sub>   s<sub>4</sub> + s<sub>3</sub>
  <sub> </sub>    <sub> </sub>   s<sub>5</sub> + s<sub>4</sub>
  <sub> </sub>    <sub> </sub>   s<sub>6</sub> + s<sub>5</sub>
 c<sub>0</sub>    <sub> </sub> + s<sub>7</sub> + s<sub>6</sub>
 c<sub>1</sub>    <sub> </sub>    <sub> </sub> + s<sub>7</sub>
 c<sub>2</sub>
 c<sub>3</sub>
 c<sub>4</sub>
 c<sub>5</sub>
 c<sub>6</sub>
 c<sub>7</sub> + s<sub>p</sub>
|
 c<sub>8 </sub>    <sub> </sub>    <sub> </sub> + e<sub>p</sub>
 c<sub>9 </sub>
 c<sub>10</sub>
 c<sub>11</sub>
 c<sub>12</sub>
 c<sub>13</sub>
 c<sub>14</sub> + e<sub>0</sub>
 c<sub>15</sub> + e<sub>1</sub> + e<sub>0</sub>
  <sub>  </sub>   e<sub>2</sub> + e<sub>1</sub>
  <sub>  </sub>   e<sub>3</sub> + e<sub>2</sub>
  <sub>  </sub>   e<sub>4</sub> + e<sub>3</sub>
  <sub>  </sub>   e<sub>5</sub> + e<sub>4</sub>
  <sub>  </sub>   e<sub>6</sub> + e<sub>5</sub>
  <sub>  </sub>   e<sub>7</sub> + e<sub>6</sub>
  <sub>  </sub>   e<sub>p</sub> + e<sub>7</sub>
  <sub>  </sub>    <sub> </sub>   e<sub>p</sub>
|-valign="top"
! C code<br />fragments:
|<source lang="c">
 uint8_t  d, s, t;
 uint16_t c, r;
 …
 s = d ^ (c >> 8);
 t = s ^ (s >> 4);
 r = (c << 8) ^
      t       ^
     (t << 5) ^
     (t << 12);</source>
|<source lang="c">
 uint8_t  d, e, f;
 uint16_t c, r;
 …
 e = c ^ d;
 f = e ^ (e << 4);
 r = (c >> 8) ^
     (f << 8) ^
     (f << 3) ^
     (f >> 4);</source>
|<source lang="c">
 uint8_t  d, s, p;
 uint16_t c, r, t;
 …
 s = d ^ (c >> 8);
 p = s ^ (s >> 4);
 p = p ^ (p >> 2);
 p = p ^ (p >> 1);
 p = p & 1;
 t = p | (s << 1);
 r = (c << 8)  ^
     (t << 15) ^
      t        ^
     (t << 1);</source>
|<source lang="c">
 uint8_t  d, e, p;
 uint16_t c, r, f;
 …
 e = c ^ d;
 p = e ^ (e >> 4);
 p = p ^ (p >> 2);
 p = p ^ (p >> 1);
 p = p & 1;
 f = e | (p << 8);
 r = (c >> 8) ^
     (f << 6) ^
     (f << 7) ^
     (f >> 8);</source>
|}

=== Two-step computation ===
As the CRC-32 polynomial has a large number of terms, when computing the remainder a byte at a time each bit depends on several bits of the previous iteration.  In byte-parallel hardware implementations this calls for either multiple-input or cascaded XOR gates which increases [[Engineering:Propagation delay|propagation delay]].

To maximise computation speed, an ''intermediate remainder'' can be calculated by passing the message through a 123-bit shift register.  The polynomial is a carefully selected multiple of the standard polynomial such that the terms (feedback taps) are widely spaced, and no bit of the remainder is XORed more than once per byte iteration.  Thus only two-input XOR gates, the fastest possible, are needed.  Finally the intermediate remainder is divided by the standard polynomial in a second shift register to yield the CRC-32 remainder.<ref name="glaise">{{cite journal
| last=Glaise
| first=René J.
| date=1997-01-20
| title=A two-step computation of cyclic redundancy code CRC-32 for ATM networks
| journal=IBM Journal of Research and Development
| volume=41
| issue=6
| publisher=[[Company:IBM|IBM]]
| location=Armonk, NY
| doi=10.1147/rd.416.0705
| url=http://www.research.ibm.com/journal/rd/416/glaise.html
| archive-url=https://web.archive.org/web/20090130044254/http://www.research.ibm.com/journal/rd/416/glaise.html
| archive-date=2009-01-30
| page=705
| access-date=2016-02-16}}</ref>

=== Block-wise computation ===
Block-wise computation of the remainder can be performed in hardware for any CRC polynomial by factorizing the State Space transformation matrix needed to compute the remainder into two simpler Toeplitz matrices.<ref>{{Cite journal |last=Das |first=Arindam |date=2022 |title=Block-wise computation of Cyclic Redundancy Code using factored Toeplitz matrices in lieu of Look-Up Table |url=https://ieeexplore.ieee.org/document/9826414 |journal=IEEE Transactions on Computers |volume=72 |issue=4 |pages=1110–1121 |doi=10.1109/TC.2022.3189574 |s2cid=250472783 |issn=0018-9340}}</ref> 

== One-pass checking ==
When appending a CRC to a message, it is possible to detach the transmitted CRC, recompute it, and verify the recomputed value against the transmitted one.  However, a simpler technique is commonly
used in hardware.

When the CRC is transmitted with the correct byte order (matching the chosen bit-ordering convention), a receiver can compute an overall CRC, over the message ''and'' the CRC, and if they are correct, the result will be zero.<ref>{{cite web 
 |first1=Andrew |last1=Kadatch |first2=Bob |last2=Jenkins
 |url=https://github.com/rurban/crcutil/raw/master/doc/crc.pdf#page=4
 |title=Everything we know about CRC but afraid to forget
 |year=3 September 2010
 |page=4
 |quote=The fact that the CRC of a message followed by its CRC is a constant value which does not depend on the message... is well known and has been widely used in the telecommunication industry for long time.
}}</ref>
This possibility is the reason that most network protocols which include a CRC do so ''before'' the ending delimiter; it is not necessary to know whether the end of the packet is imminent to check the CRC.

In fact, a few protocols use the CRC ''as'' the message delimiter, a technique called [[CRC-based framing]].  (This requires multiple frames to detect acquisition or loss of framing, so is limited to applications where the frames are a known length, and the frame contents are sufficiently random that valid CRCs in misaligned data are rare.)

== CRC variants ==
In practice, most standards specify presetting the register to all-ones and inverting the CRC before transmission.  This has no effect on the ability of a CRC to detect changed bits, but gives it the ability to notice bits that are added to the message.

=== Preset to −1 ===
The basic mathematics of a CRC accepts (considers as correctly transmitted) messages which, when interpreted as a polynomial, are a multiple of the CRC polynomial.  If some leading 0 bits are prepended to such a message, they will not change its interpretation as a polynomial.  This is equivalent to the fact that 0001 and 1 are the same number.

But if the message being transmitted does care about leading 0 bits, the inability of the basic CRC algorithm to detect such a change is undesirable.  If it is possible that a transmission error could add such bits, a simple solution is to start with the <code>rem</code> shift register set to some non-zero value; for convenience, the all-ones value is typically used.  This is mathematically equivalent to complementing (binary NOT) the first ''n'' bits of the message, where ''n'' is the number of bits in the CRC register.

This does not affect CRC generation and checking in any way, as long as both generator and checker use the same initial value.  Any non-zero initial value will do, and a few standards specify unusual values,<ref>E.g. low-frequency RFID {{Citation
| url=http://www.ti.com/lit/ds/symlink/tms37157.pdf
| title=TMS37157 data sheet - Passive Low Frequency Interface Device With EEPROM and 134.2 kHz Transponder Interface
| publisher=[[Company:Texas Instruments|Texas Instruments]]
| date=November 2009
| page=39
| quote=The CRC Generator is initialized with the value 0x3791 as shown in Figure 50.
| access-date=2016-02-16}}</ref> but the all-ones value (−1 in twos complement binary) is by far the most common.  Note that a one-pass CRC generate/check will still produce a result of zero when the message is correct, regardless of the preset value.

=== Post-invert ===
The same sort of error can occur at the end of a message, albeit with a more limited set of messages.  Appending 0 bits to a message is equivalent to multiplying its polynomial by ''x'', and if it was previously a multiple of the CRC polynomial, the result of that multiplication will be, as well.  This is equivalent to the fact that, since 726 is a multiple of 11, so is 7260.

A similar solution can be applied at the end of the message, inverting the CRC register before it is appended to the message.  Again, any non-zero change will do; inverting all the bits (XORing with an all-ones pattern) is simply the most common.

This has an effect on one-pass CRC checking: instead of producing a result of zero when the message is correct, it produces a fixed non-zero result.  (To be precise, the result is the CRC, with zero preset but with post-invert, of the inversion pattern.)  Once this constant has been obtained (e.g. by performing a one-pass CRC generate/check on an arbitrary message), it can be used directly to verify the correctness of any other message checked using the same CRC algorithm.

== See also ==
General category
* Error correcting code
* [[List of hash functions]]
* Parity is equivalent to a 1-bit CRC with polynomial {{math|''x''+1}}.

Non-CRC checksums
* [[Adler-32]]
* [[Fletcher's checksum]]

== References ==
<references/>

== External links ==
* {{cite web
| url=http://pages.pathcom.com/~vadco/crc.html
| title=64 Bit Cyclic Redundant Code – XOR Long Division To Bytewise Table Lookup
| author=JohnPaul Adamovsky}}

* {{cite web
| url=https://github.com/lizardfs/lizardfs/tree/master/external/crcutil-1.0
| title=Efficient (~1 CPU cycle per byte) CRC implementation
| author=Andrew Kadarch, Bob Jenkins| website=[[GitHub]]
}}

[[Category:Cyclic redundancy checks]]
[[Category:Finite fields]]

{{Sourceattribution|Computation of cyclic redundancy checks}}