Cyclical redundancy check

from Wikipedia, the free encyclopedia

The cyclic redundancy check (English cyclic redundancy check , therefore usually CRC ) is a method for determining a check value for data to be able to detect errors in transmission or storage. In the ideal case, the process can even correct the received data independently in order to avoid a new transmission.

It was developed in 1961 by W. Wesley Peterson .

General

Before data storage or transmission , additional redundancy in the form of a so-called CRC value is added for each data block of the user data . This is a test value calculated according to a certain procedure, with the help of which one can identify any errors that may have occurred during storage or transmission. To check the data, the same calculation method is used on the data block including the added CRC value. If the result is then zero, it can be assumed that the data block is unadulterated. However, various technical applications deviate from this scheme, for example by initializing the calculation with a specific value or by inverting the CRC value before transmission.

CRC is designed in such a way that errors in the transmission of the data, such as those caused by noise on the line, are detected with a high degree of probability. CRCs of serial data transmissions can be implemented very easily in hardware. For example, data transmissions via Ethernet, as well as most hard disk transmissions, are checked with the CRC method.

The CRC procedure is only designed for the detection of random errors. It is not suitable for confirming the integrity of the data. That is, it is relatively easy to create, by intentional modification, a data stream that has the same CRC value as a given message. If such security is required, cryptographic hash functions such as SHA must be used.

The name of the method is based on the fact that the added value has no information content that is not already contained in the underlying data block. It is therefore redundant. CRCs are based on cyclic codes . These are block codes that have the property that every cyclic shift of the bits of a valid code word is also a valid code word.

Procedure

The calculation of the CRC value is based on polynomial division : the sequence of bits to be transmitted is regarded as a binary polynomial . Example: The bit sequence 1,0,0,1,1,1,0,1 corresponds to the polynomial

The bit sequence of the code representation of the data is divided modulo mod (2) by a generator polynomial (the CRC polynomial) to be defined beforehand , leaving a remainder. This remainder is the CRC value. When the data block is transmitted, the CRC value is appended to the original data block and transmitted along with it.

In order to verify that the data does not contain an error, the received data block with the attached CRC value is interpreted as a binary sequence, divided again by the CRC polynomial modulo and the rest is determined. If there is no remainder, either no error has occurred or a (very unlikely) error has occurred which has the CRC polynomial as a factor in the polynomial representation.

Make sure that the ones and zeros in communication with CRC are not a representation of a number, but a polynomial. This means that modulo division with binary numbers (or numbers in general), for example with a calculator, does not lead to the correct result.

The transfer of data requires certain indispensable agreements. On the one hand, the recipient must be aware that a secure transmission of the original data should take place at all. This cannot be recognized from the type of incoming data stream alone. On the other hand, the receiver must use the same CRC polynomial and calculation method as the sender. And finally, the recipient must have the information about where in the data stream the checksum that is transmitted in addition to the data is located.

example

The following is an example in which the CRC is to be calculated and checked for a binary code of 5 bits. The generator polynomial (CRC polynomial) is 110101( ) and is therefore 5th  degree . Of the transmitted bit sequence, which as a frame (engl. Frame hereinafter) are zeros appended (Appendix frame), where the degree of the generator polynomial corresponds to (or the number of bits of the generator polynomial minus one).

Generator polynomial: 110101   (previously determined)
Frame: 11011   (User data)
Frame with attachment: 1101100000   (the generator polynomial has places, so zeros are added; here is )

Now the frame with appendix is ​​divided from the left by the generator polynomial. Only the exclusive OR ( XOR ) is used here. If you apply this in the first step, the 110110 XOR  becomes 110101the number 000011(where: 1 XOR 1 = 0; 1 XOR 0 = 1; 0 XOR 1 = 1; 0 XOR 0 = 0). The full example follows:

↓ always start with the first common 1

1101100000
110101
------
0000110000
    110101
    ------
     00101 (Rest)

The rest is now attached to the frame without an attachment. This must also consist of bits. We are now attached to the frame. 00101

Transmitted frame: 1101100101

This message can now be transmitted over a network, for example. When the recipient receives the message, he or she can check whether it has arrived correctly.

The faulty transmission can now be recognized by dividing by the generator polynomial:

Correct transmission of the message: 1101100101
The generator polynomial (as above): 110101
 1101100101
 110101
 ------
     110101
     110101
     ------
      00000
The remainder of the division is zero. So there was probably no error.
Incorrectly transmitted message (example): 1001100101
The generator polynomial (as above): 110101
 1001100101
 110101
 ------
  100110
  110101
  ------
   100111
   110101
   ------
    100100
    110101
    ------
     100011
     110101
     ------
      10110

The remainder of the division ( 10110) is non-zero. So an error occurred. The following four cases can arise when checking for correctness:

  1. The remainder of the division is zero and the message is correct
  2. The remainder of the division is zero and the message is incorrect (this case is unlikely, but it can happen if the error polynomial is a multiple of the generator polynomial or if the error is in the data part and in the CRC value)
  3. The remainder of the division is non-zero and the message is in error
  4. The remainder of the division is non-zero and the message is correct (this case occurs if only the appended remainder is transmitted incorrectly; however, this is also unlikely since the transmitted remainder is short compared to the total length of the packet)

implementation

The CRC process can be implemented both in simple hardware modules and in software . A is used

  • Shift register with n bits, where n is the degree of the generator polynomial (about a 32-bit shift register with CRC-32) and a
  • Bit data stream of any length followed by n zero bits.

Pseudocode of the algorithm , most significant bit on the far left, multiplication by 2 means shifting one place to the left:

crc  : = 0000… (start value)
for all bits b in the data stream :
  if  the leftmost bit of crc is 1 : crc  : = ( crc * 2 + b ) xor CRC polynomial   otherwise: crc  : = crc * 2 + b crc contains the result.
    

    

Using a table that contains the associated CRC value for each of the 256 possible bytes for a CRC-8, for example, the above algorithm can be accelerated by a factor of 8. This results from the fact that a table entry contains 8 bits = 1 byte and different table entries exist. The increase in speed is achieved through direct access to the table with the help of the bit sequence to be calculated, in that the CRC-8 calculation you are looking for is at the point in the table that has the binary value of the bit sequence to be calculated as an index.

The shift left and exclusive-or operations make the CRC ideal for use in logic circuits . The CRC of a data stream can be calculated bit by bit (or byte by byte, etc.) and attached to the data by the sender. The receiver of the data stream can calculate the CRC in the same way as the sender, but with the inclusion of the CRC. The result including the CRC must then be equal to zero, otherwise the stream contains bit errors .

CRC types are often differentiated based on the polynomial used as a divisor (in hexadecimal format). One of the most widely used CRCs (used by Ethernet , FDDI , ZIP and PNG , among others ) is the polynomial 0x04C11DB7, known as CRC-32. It turned out that some polynomials “protect” better than others. Polynomials commonly used for CRC are the result of extensive mathematical and empirical analysis and are not random numbers, even if they look like that.

Other starting values

The implementation carries out a polynomial division if 0000… is used as the start value . Often you can find other starting values, such as 1111… . This corresponds to a polynomial division if the first n bits of the data stream are inverted.

A start value unequal to 0000 ... is preferable, since missing bits within leading zeros in the data stream will otherwise not be recognized (just as with a normal division, leading zeros do not count in a polynomial division).

Zero problem and post processing

Another problem is the zero problem, which occurs in two forms:

  1. If a data stream happens to produce a CRC equal to zero, the CRC is also zero if additional zeros are appended to the data stream or - if the data stream ends with one or more zeros - some of these last zeros are removed.
  2. If the CRC is appended to the end of the data stream (as it is being sent by a sender) and additional zeros are added during transmission (after the CRC sent), these additional zeros cannot be recognized at the end.

The zero problem in both versions is independent of whether starting values ​​equal to zero or not equal to zero are used.

The zero problem in both versions is avoided by inverting the bits of the CRC result. If the CRC check is carried out in the receiver in such a way that the receiver calculates a CRC from the received data packet, the data packet consisting of a data stream and an appended CRC, then in the case of an unchanged (non-inverted) CRC of the sender, the calculated CRC in the receiver is always zero. In the case of an inverted CRC of the sender, the calculated CRC in the receiver is always the same value; this is also known as the Magic Number.

The zero problem of the second embodiment can also be avoided by reversing the order of the CRC bits. However, the case where the CRC is equal to zero remains undetected, which represents the zero problem of the first type.

The zero problem described so far thus relates to the problem of recognizing additional zeros that have been added or lost at the end of the data stream. However, this is only necessary if, due to the prevailing boundary conditions, it cannot be guaranteed that the size of the data will remain unchanged.

However, one sometimes speaks of a zero problem when it is problematic if a data stream made up of all zeros also generates a CRC equal to zero. A CRC equal to zero from zero data always arises regardless of the generator polynomial if the CRC start value is equal to zero and the bits of the resulting CRC are not inverted. This problem can thus be avoided by specifying a start value that is not equal to zero or by inverting the resulting CRC bits.

The well-known CRC-32 uses both 1111 ... as a start value and an inverse result. With CRC-16, 1111 .. is also mostly used, but the result is not inverted. In both cases, the order of the CRC bits remains unchanged.

Detected errors

If the CRC polynomial is well chosen, all single-bit errors, every odd number of corrupted bits and all bundle errors of the length can be detected with the method described above , where the degree of the CRC polynomial is. In addition, all errors (including independent four-bit, six-bit, eight-bit errors, etc.) whose polynomial representation has a lower degree than the CRC polynomial are recognized. Contrary to popular belief, two-bit errors are not generally recognized. Why this is the case and how the CRC polynomial is to be selected will follow from the following considerations.

Let the CRC polynomial (generator polynomial) and the polynomial representation of the bit sequence to be transmitted expanded by the CRC value. If an error occurs during transmission, it does not arrive (in polynomial representation) at the recipient , but arrives . The bit sequence to which it belongs has a 1 at each bit position that was inverted or corrupted in the bit sequence to be transmitted. When the receiver receives the bit sequence expanded by the CRC value, it calculates . There (by definition of ) is the result .

One-bit error

If a one-bit error has occurred , where determines which bit is inverted. If now contains two or more terms, we will never divide.

Two isolated one-bit errors

If two isolated one-bit errors have occurred , where . If you exclude , this can also be written as. Since it cannot be divisible by , it is sufficient to require that it does not divide (for all up to the maximum value of , i.e. the maximum frame length). Simple polynomials of low degree which allow reliable transmission for long frames are known. For example, the term does not divide for anything less than 32767.

Odd number of errors

If an odd number of bits is corrupted, contains an odd number of terms (e.g. , but not e.g. ). If you choose the CRC polynomial in such a way that it has as a factor, all errors with an odd number of corrupted bits are recognized.

Proof: When dividing by a polynomial with even parity (= number of terms in the polynomial, i.e. number of ones in the bit sequence) the evenness or oddness of the parity in the division remainder is equal to that of the dividend, because 00 becomes 11 ( and vice versa) and 01 becomes 10 (and vice versa).

is the smallest polynomial with even parity. In is therefore always or remain as a residual, if odd parity has. This is not divisible by.

Bundle error

All burst errors of the length , where the degree of the CRC polynomial is, are recognized. A bundle error of length can be written as , whereby it determines how many bit positions from the right side of the received bit sequence (or of the received frame) the bundle error is removed. If the error is to be recognized, the division of by a remainder must result.

As always the term contains are and prime. That means, if , then must . However, this is not possible because, by assumption, the degree of is smaller ( ) than the degree of . The rest can never be 0 and the bundle error is recognized.

example

The generator polynomial (IBM-CRC-16) can be factored as. Because of the factor , this CRC is able to recognize all errors with an uneven number. Furthermore, the smallest positive integer k for which the generator polynomial divides the polynomial is k = 32767. This means that all randomly arranged, double bit errors are reliably detected if the block length is less than 32768. All bundle errors of length 16 or less are also reliably detected. Bundle errors with a length of 17 can be detected with a probability of 0.99997. All bundle errors with a length of 18 and more can be identified with a probability of 0.99998.

Detected errors (according to the bit filter theory)

For the sake of completeness, the following should be added:

  1. Any generator polynomial recognizes all bundle errors that are no longer than the generator polynomial - except for one, namely that which has the same bit pattern as the generator polynomial. Of course, this also includes one-bit errors as bundle errors of length 1.
  2. A generator polynomial with an even number of terms detects any odd number of bit errors.
  3. With the bit filter theory it can be shown that only those two-bit errors are not recognized, the distance between which is a multiple of the cycle of the period of the longest bit filter. In the case of optimally selected generator polynomials of degree with an even number of terms, this distance is , for example , this period is 32767, i.e. more than 4000 bytes!
  4. It can similarly be shown that all one-bit errors can be corrected if the data block is no longer than the period just mentioned. This follows from the fact that the residues after division by the generator polynomial are all different - as far as one can have different residues, of which there are at most . However, under certain circumstances three-bit errors leave the same residue, so that in this case a correction can falsify the result even more. However, one and two-bit errors must always be differentiated with certainty.

More details can be found in the reference analysis of the CRC method with bit filters . There is also a list of optimal generator polynomials of various degrees.

Calculation of a CRC checksum in C and Pascal or Delphi

CRC-32 implementation in the C programming language

The following C program calculates the CRC-32 of the 8-bit long data stream 10001100 :

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
/* typedef unsigned __int32 uint32_t; /* => für MS-VS */

#define CRC32MASK   0x04C11DB7        /* CRC-32 Bitmaske */

int      bitstream[] = { 1,0,0,0,1,1,0,0 };
int      bitcount    = 8;
uint32_t crc32       = 0;             /* Schieberegister */

int main ()
{
    int i;
    for (i = 0; i < bitcount; i++)
    {
        if ( ((crc32 >> 31) & 1) != bitstream[i])
            crc32 = (crc32 << 1) ^ CRC32MASK;
        else
            crc32 = (crc32 << 1);
    }
    printf ("0x%08X\n", crc32);
    return EXIT_SUCCESS;
}

Modified CRC32: start value 111 ..., inverted result with reversed bit sequence

Standards like Ethernet modify the algorithm:

  • 111 .... 111 is used as the start value (this corresponds to an inversion of the first 32 bits in the data stream).
  • If the data stream consists of bytes, the least significant bit is used first.
  • All bits in the result are inverted and the bit order is rotated, that is, the most significant bit appears first.

The following program calculates such a modified CRC value:

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define CRC32MASKREV   0xEDB88320            /* CRC-32 Bitmaske, umgekehrte Bitfolge */

int      bitstream[] = { 1,0,0,0,1,1,0,0 };  /* ASCII-"1", LSB zuerst */
int      bitcount    = 8;
uint32_t crc32_rev   = ~0;                   /* Schieberegister, Startwert (111...) */

int main(void)
{
    int i;
    for (i = 0; i < bitcount; i++)
    {
        if ((crc32_rev & 1) != bitstream[i])
            crc32_rev = (crc32_rev >> 1) ^ CRC32MASKREV;
        else
            crc32_rev = (crc32_rev >> 1);
    }
    printf("0x%08X\n", ~crc32_rev);          /* inverses Ergebnis, MSB zuerst */
    return EXIT_SUCCESS;
}

IBM-CRC-16 implementation in the programming language Pascal / Delphi

The following Pascal program calculates an IBM-CRC-16 value with start value 111 ... and reversed bit sequence via an array of bytes and outputs it:

const
  Polynom: Word = $A001;
  Initial: Word = $FFFF;
var
  CRC: Word;
  N, I: Integer;
  B: Byte;

begin
  CRC := Initial;
  for I := Low(Buffer) to High(Buffer) do
  begin
    B := Buffer[I];
    CRC := CRC xor B;
    for N := 1 to 8 do
      if (CRC and 1) > 0 then
        CRC := (CRC shr 1) xor Polynom
      else
        CRC := (CRC shr 1);
  end;
  Showmessage(IntToHex(CRC, 4)); (* Ausgabe *)
end;

CRC-CCITT implementation in the programming language Pascal / Delphi

The following Pascal program calculates a CRC-CITT value with starting value 0 via an array of bytes and outputs it:

const
  Polynom: Word = $1021;
  Initial: Word = 0;
var
  CRC: Word;
  N, I: Integer;
  B: Byte;

begin
  CRC := Initial;
  for I := Low(Buffer) to High(Buffer) do
  begin
    B := Buffer[I];
    CRC := CRC xor (B shl 8);
    for N := 1 to 8 do
      if (CRC and $8000) <> 0 then
        CRC := (CRC shl 1) xor Polynom
      else
        CRC := CRC shl 1;
  end;
  CRC := CRC and $FFFF;
  Showmessage(IntToHex(CRC, 4)); (* Ausgabe *)
end;

Polynomials and types

Surname polynomial length Best before Remarks
CRC-CCITT (CRC-4) 15th 3 Identical to the (15,11) hammering code
USB (CRC-5) 31 3 Identical to the (31,26) hammering code
Bluetooth 15th Abbreviated (15,10) Hamming Code.
SD / MMC card (CRC-7) 127 3 Identical to the (127,120) hammering code
CRC-8 (Dallas / Maxim 1-Wire Bus) 127 4th Described by Dallas / Maxim
CRC-8 (ITU-T) 127 4th ISDN Header Error Control (Section 7.3.2.2)
CRC-8 (SAE-J1850) 255 3 Used by AES / EBU
CRC-12
CAN CRC 127 6th
CRC-CCITT (CRC-16) 32767 4th Used with XMODEM  CRC, HDLC , X.25 (Section 2.2.7.4, Appendix I)
IBM-CRC-16 32767 4th
CRC-DNP (CRC-16)
CRC-16 VÖV 04.05.1
CRC-24 (IETF RFC2440)
CRC-24 (Mode-S) For frame lengths up to 112 bits, error-correcting up to 5 bits
CRC-32 ( IEEE 802.3 ) 3 Used with Ethernet
CRC-64 (ISO 3309)
CRC-64 ( ECMA-182 ) Used by XZ Utils

The MHD column indicates the minimum Hamming distance that distinguishes two bit sequences with a valid CRC value. A CRC algorithm can therefore recognize every error that affects less than MHD bit positions within the specified maximum length . If the maximum length is exceeded, there are two-bit errors in every CRC algorithm that are not recognized (e.g. two errors that are exactly length positions apart).

CRC values ​​are often referred to as checksums , although the control bits are not only calculated by (ordinary) addition. The term “checksum” was first used in connection with parity bits , which can be calculated as a real sum . The term has become so common that it was adopted as a name for the calculation of general control bits.

The test polynomials were selected from a large number of possible polynomials in such a way that “favorable” properties result for the code generated with them. Example: If a polynomial has an even number of terms in x (CRC16-CCITT: 4 and CRC16-IBM: 4, but not CRC-4: 3), the binomial (x + 1) is included as a factor. This binomial causes a "parity check", whereby all errors with an uneven number of error locations can be recognized in the resulting code in any case.

See also

Web links

Individual evidence

  1. ^ WW Peterson: Cyclic Codes for Error Detection . In: Proceedings of the IRE , Vol. 49, No. 1, 1961, pp. 228-235
  2. ^ Todd K. Moon: Error Correction Coding . John Wiley & Sons, 2005, ISBN 0-471-64800-0 , pp. 149 .
  3. Dallas / Maxim DS18S20, p. 6 ( Memento of the original from April 1, 2010 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 250 kB) on datasheets.maxim-ic.com @1@ 2Template: Webachiv / IABot / datasheets.maxim-ic.com
  4. ITU-T Recommendation I432.1 . International Telecommunication Union. Pp. 5-6. February 1999. Retrieved March 9, 2011.
  5. ITU-T Recommendation X.25 . International Telecommunication Union. 9, October 145, 1996. Retrieved March 9, 2011.
  6. IEEE Std 802.3-2015 Section 1 . IEEE Computer Society. P. 112. September 9, 2015. Accessed May 4, 2018.
  7. ECMA-182