Admin: Created page with "Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it re..."

2019-05-04T02:37:42Z

Created page with "Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it re..."

New page

Computation of a [[cyclic redundancy check]] is derived from the mathematics of [[Mathematics of cyclic redundancy checks|polynomial division, modulo two]]. In practice, it resembles [[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]] operations replace subtractions. Division of this type is efficiently realised in hardware by a modified [[shift register]], and in software by a series of equivalent [[algorithm]]s, starting with simple code close to the mathematics and becoming faster (and arguably more [[obfuscated code|obfuscated]]) through [[byte]]-wise [[Parallelism (computing)|parallelism]] and [[space–time tradeoff]]s.

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]]). As a result, the code seen in practice deviates confusingly from "pure" division, Most commonly, a 256-entry lookup table is used, replacing the inner loop over <code>j</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. 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 -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 × 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.

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

=== Parallel computation without table ===

Parallel update for a byte or a word at a time can also be done explicitly, without a table. 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"
|-
| ci || CRC bit 7…0 (or 15…0) before update
|-
| ri || CRC bit 7…0 (or 15…0) after update
|-
| di || input data bit 7…0
|-
| ei = di + ci
| ep = e7 + e6 + … + e1 + e0 ''(parity bit)''
|-
| si = di + ci+8
| sp = s7 + s6 + … + s1 + s0 ''(parity bit)''
|}

{| class="wikitable"
|+ Bit-wise update equations for some CRC-8 polynomials after 8 bits have been shifted in
! Polynomial:
| (''x''7 + ''x''3 + 1) × ''x'' ''(left-shifted CRC-7-CCITT)''
| ''x''8 + ''x''5 + ''x''4 + 1 ''(CRC-8-Dallas/Maxim)''
|-
! Coefficients:
| 0x12 = (0x09 << 1) ''([[Most significant bit|MSBF]]/normal)''
| 0x8c ''([[Least significant bit|LSBF]]/reverse)''
|-
|
r0 ←
r1 ←
r2 ←
r3 ←
r4 ←
r5 ←
r6 ←
r7 ←
|
0
e0 + e4 + e7
e1 + e5
e2 + e6
e3 + e7 + e0 + e4 + e7
e4 + e1 + e5
e5 + e2 + e6
e6 + e3 + e7
|
e0 + e4 + e1 + e0 + e5 + e2 + e1
e1 + e5 + e2 + e1 + e6 + e3 + e2 + e0
e2 + e6 + e3 + e2 + e0 + e7 + e4 + e3 + e1
e3 + e0 + e7 + e4 + e3 + e1
e4 + e1 + e0
e5 + e2 + e1
e6 + e3 + e2 + e0
e7 + e4 + e3 + e1
|-valign="top"
! C code 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''16 + ''x''12 + ''x''5 + 1 ''(CRC-16-CCITT)''
| colspan="2" | ''x''16 + ''x''15 + ''x''2 + 1 ''(CRC-16-ANSI)''
|-
! Coefficients:
| 0x1021 ''(MSBF/normal)''
| 0x8408 ''(LSBF/reverse)''
| 0x8005 ''(MSBF/normal)''
| 0xa001 ''(LSBF/reverse)''
|-
|
r0 ←
r1 ←
r2 ←
r3 ←
r4 ←
r5 ←
r6 ←
r7 ←
r8 ←
r9 ←
r10 ←
r11 ←
r12 ←
r13 ←
r14 ←
r15 ←
|
s4 + s0
s5 + s1
s6 + s2
s7 + s3
 s4
 s5 + s4 + s0
 s6 + s5 + s1
 s7 + s6 + s2
c0 + s7 + s3
c1 + s4
c2 + s5
c3 + s6
c4 + s7 + s4 + s0
c5 + s5 + s1
c6 + s6 + s2
c7 + s7 + s3
|
c8 + e4 + e0
c9 + e5 + e1
c10 + e6 + e2
c11 + e0 + e7 + e3
c12 + e1
c13 + e2
c14 + e3
c15 + e4 + e0
 e0 + e5 + e1
 e1 + e6 + e2
 e2 + e7 + e3
 e3
 e4 + e0
 e5 + e1
 e6 + e2
 e7 + e3
|
 sp
 s0 + sp
 s1 + s0
 s2 + s1
 s3 + s2
 s4 + s3
 s5 + s4
 s6 + s5
c0 + s7 + s6
c1 + s7
c2
c3
c4
c5
c6
c7 + sp
|
c8 + ep
c9 
c10
c11
c12
c13
c14 + e0
c15 + e1 + e0
 e2 + e1
 e3 + e2
 e4 + e3
 e5 + e4
 e6 + e5
 e7 + e6
 ep + e7
 ep
|-valign="top"
! C code 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 [[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.

== 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. This possibility is the reason that most network protocols that 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.

== 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, 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. 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 constant non-zero result. (To be precise, the result is the CRC (without non-zero preset, but with post-invert) of the inversion pattern.) Once this constant has been obtained (most easily 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 ==
* [[List of hash functions]]
* [[Fletcher's checksum]]

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

Computation of cyclic redundancy checks - Revision history

Admin: Created page with "Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it re..."