Cyclic redundancy check
The cyclic redundancy check ( cyclic redundancy check English, therefore usually CRC ) is a method for determining a test value for data in order to detect errors in transmission or storage can.
It was developed in 1961 by W. Wesley Peterson.
- 3.1 one-bit errors
- 3.2 Two isolated single-bit error
- 3.3 Odd number of errors
- 3.4 bundle error
- 3.5 Example
- 3.6 Detected faults (after Bitfiltertheorie )
General
Prior to the data storage or transmission of additional redundancy is added in the form of a so-called CRC value for each data block of user data. This is a test value calculated according to a certain method, by which you can identify any that occurred during storage or transmission errors. To verify the data the same calculation method is applied to the data block including the attached CRC value. If the result is then zero, it can be assumed that the data block is unadulterated. Various technical applications but soft on this scheme by initializing example, the calculation of a certain value or invert the CRC before transmitting.
CRC is designed such that errors in the transmission of data, as may be caused for example by noise on the line may be detected with high probability. CRCs of serial data transmissions can be easily implemented in hardware. For example, data transfers over Ethernet, as well as most hard drives transmissions are checked with CRC method.
The CRC method is designed for the detection of random errors. It is not suitable to confirm the integrity of the data. That is, it is relatively easy to produce by intentional modification of 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 based on the fact that the attached value has no information content, which is not included in the underlying data block. It is therefore redundant. CRCs are based on cyclic codes. These are block codes that have the property that any cyclic shift of the bits of a valid code word is another valid code word.
Method
The calculation of the CRC value based on the polynomial division: The sequence of bits to be transmitted is considered to be dyadic 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 by a generator polynomial to be determined in advance ( the CRC polynomial ) modulo mod ( 2), wherein a remainder. This radical is the CRC value. During the transmission of the data block is appended to the CRC value to the original data block and transmits it with.
In order to verify that the data include no error, the received data block is interpreted with the attached CRC value as a binary sequence, again divided by the CRC polynomial modulo, and determines the remainder. If no remainder, no error either occurred or there is a (very unlikely ) error has occurred that the CRC polynomial has as a factor in polynomial representation.
It is important to ensure that it is not the representation of a number, but to a polynomial in the ones and zeros of communication with CRC. This means that the modulus operation with binary numbers ( or numbers in general ) does not lead, for example, with the calculator on the right result.
The data transmission requires certain essential Agreement. For one, the receiver must be aware that at all reliable transfer of the original data to take place. On the nature of the incoming data stream alone, this is not apparent. Furthermore, the receiver the same CRC polynomial and calculating method has to use as the transmitter. Finally, the recipient must have the information of where is the addition to the data transmitted checksum in the data stream.
Example
Here is an example, is to be calculated and checked in the binary code for a 5-bit CRC. The generator polynomial ( CRC polynomial ) is 110101 (), making it the 5th degree. The bit sequence to be transmitted, which is also referred to as a frame ( frame Data Sheet ) 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).
Now the frame is divided by Annex from the left by the generator polynomial. Here, the exclusive OR ( XOR) is used exclusively. Applying this in the first step, the number of XOR 110110 110101 000011 ( where 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0). It follows the complete example:
↓ always start with the first joint 1
1101100000 110101 ------ 0000110000 110101 ------ 101 (residual ) On the frame without the Annex to rest now is appended. This also must be made of bits. So we now depend 00101 on the frame.
Rendered Frame: 1101100101
This message can now, for example, be transmitted over a network. When the message arrives at the receiver, it can check if it has arrived correctly.
Means division by the generator polynomial may now arise in the conversion are recognized:
1101100101 110101 ------ 110101 110101 ------ 000000 The remainder of the division is zero. So it's probably no error occurred. Incorrectly transmitted message (example): 1001100101 The generator polynomial ( as described above ): 110101 1001100101 110101 ------ 100110 110101 ------ 100111 110101 ------ 100100 110101 ------ 100011 110101 ------ 10110 The remainder of dividing ( 10110 ) is equal to zero. Thus, an error has occurred. When checking for correctness following four cases can occur:
Implementation
The CRC method can be implemented in simple hardware modules as well as in software. Uses a
- Shift register having n bits (for example, a 32 bit shift register in the CRC -32) and
- Bit data stream of any length.
Pseudo code of the algorithm, the most significant bit on the far left:
Shift register: = 0000 ... ( start value) as long as bits remain in the data stream: if the leftmost bit of the shift register equal to the next bit from the data stream is: Shift register: = (shift register shift left by 1, right bit 0) XOR CRC polynomial otherwise: Shift register: = shift register shift left by 1 bit right 0 next bit in the data stream Shift register contains the result.
By using a table which for each of the 256 possible byte contains the associated CRC value approximately at a CRC -8, 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 various table entries exist. The increase in speed is realized by the direct access to the table by using the bit sequence to be calculated by the required CRC -8 calculation at the site is on the table which has the binary value to be calculated bit string as the index.
The operations left shift and exclusive-or make the CRC eminently suitable for use in logic circuits. The CRC of a data stream can be calculated by bit ( or byte-wise, etc. ) and attached by the sender to the data. The recipient of the data stream can calculate the CRC as well as the transmitter, but including the CRC. The result including the CRC must then be zero, otherwise the stream will contain bit errors.
CRC types are often distinguished on the basis of the polynomial used as a divisor ( in hexadecimal format ). One of the most commonly used CRCs ( inter alia on Ethernet, FDDI, ZIP and PNG used) is the polynomial 0x04C11DB7, known as CRC -32. It turned out that some polynomials better "protect" than others. For frequently used CRC polynomials are the result of extensive mathematical and empirical analyzes and no random numbers, even if they look like this.
Other starting values
The implementation performs a polynomial if it is used as a starting value ... 0000. We often find other starting values , about 1111 .... This corresponds to a polynomial, if the first n bits of the data stream can be inverted.
A start value is not 0000 ... is preferable because missing bits are not recognized elsewhere in the data stream within leading zeros (as well as in an ordinary Division are assigned in a polynomial leading zeros are not ).
Zero problem and post
Another problem represents the zero problem, which occurs in two forms:
The null problem in both embodiments is, whether initial values are used is equal to zero or equal to zero.
The zero problem in both versions, is avoided by the bits of the CRC result are inverted. Takes place in the receiver the CRC such that the receiver has a CRC calculated from the received data packet, the data packet from the data stream and appended CRC is given, in the case of a constant ( non-inverted ) CRC of the transmitter of the calculated CRC in the receiver, always zero. In the case of an inverted CRC, the calculated CRC of the transmitter the receiver is always the same value, it is also referred to as magic number.
Zero problem of the second embodiment can also be avoided by changing the order of the CRC bits is reversed. However, undetected is the case where the CRC is equal to zero, which is the zero problem of the first type.
The zero problem described so far thus refers to the problem of recognizing the end of the data stream in addition added or lost zeros. However, this is only necessary if you can not be assured due to the prevailing conditions, that the size of the data remains unchanged.
From zero, however, a problem is referred to at times even when it is a problem if a data stream of zeros and a CRC generated zero. A CRC is equal to zero from zero data arises independently in principle from the generator when the CRC seed value is equal to zero, and the bits of the resulting CRC are not inverted. This problem can be avoided by using a start value is set equal to zero, or else the resultant CRC bits are inverted.
The well-known CRC - 32 is used both in 1111 ... as a start value and an inverse result. At most 1 111 .. 16 CRC is also used, but the result is not inverted. In both cases, the order of the CRC bits is unchanged.
Detected errors
If the CRC polynomial well chosen, all one-bit errors, any odd number of corrupted bits, and all burst errors of length can be detected with the method described above, the degree of the CRC polynomial. In addition, all errors (including independent four-bit, six-bit, Achtbitfehler, etc ) recognized the polynomial has a smaller degree than the CRC polynomial. Two bit errors are not recognized in principle contrary to popular belief. Why this is so and how the CRC polynomial must be chosen, it follows from the next considerations.
Is the CRC polynomial ( generator polynomial ), and the polynomial representation of the CRC value to the extended bit string to be transmitted. If an error occurs during transmission, comes ( in polynomial ) the recipient does not, but at. The bit sequence to belong, has a 1 When the recipient receives the CRC value to the extended sequence of bits in each bit position that has been inverted or distorted at the bit sequence to be transmitted, he calculated. Since ( by definition of ), is the result.
Single-bit error
If a single-bit error has occurred, holds, where determines which bit is inverted. If now contains two or more terms, will never share.
Two isolated single-bit error
Are two isolated single-bit error occurred, holds, where. If we exclude from, this can be as write. Since it can not be divisible by, it is enough to demand that does not share (for all up to the maximum value of, ie, the maximum frame length). Simple polynomials of small degree, enabling secure transmission of long frames are known. For example, the term does not share for each smaller 32767.
An odd number of errors
Is an odd number of bits falsified, contains an odd number of terms (for example, but not, for example ). If one selects the CRC polynomial so that it has as a factor, all errors with an odd number of corrupted bits are detected.
Proof: For division by a polynomial with even parity ( = number of terms in the polynomial, ie number of ones in the bit string ) is the straightness or oddness of the parity of the divisor obtained because of 00 is 11, and vice versa, and is from 01 10 and vice versa.
Is the smallest polynomial with even parity. When will therefore always remain as a residual or, if odd parity has. This is not divisible by.
Burst error
Any burst errors ( only VINYL burst ) of the length, the degree of the CRC polynomial is to be detected. A burst error of length can be written as, which determines how many bit positions from the right side of the received bit sequence (or the received frame ) of the burst error is removed. If the error is to be detected, the Division of must result from a rest.
As always contains the term, and are relatively prime. That is, if, it must. However, this is not possible because the degree by adoption of smaller () as the degree of. The remainder can not be 0 and the burst error is detected.
Example
The generator polynomial (IBM CRC -16) can be factored as. Because of the factor is this CRC is able to detect all faults odd number. Furthermore, it is the smallest positive integer k, wherein the generator divides the polynomial, k = 32767. This means that all arranged as desired, are detected twice the bit error sure if the block size is smaller than 32768. Further, all burst errors of length 16 or less reliably detected. Burst errors with a length of 17 are recognized with a probability of 0.99997. All burst errors with a length of 18 or more are recognized with a probability of 0.99998.
Detected errors (after Bitfiltertheorie )
For completeness, the following should be added here:
More details can be taken of the reference analysis of the CRC method with Bitfiltern. There is also a list of optimal generator polynomials of different degrees.
Calculating a CRC checksum in C and Pascal / Delphi
CRC-32 is implemented in the C programming language
The following C program calculates the CRC - 32 of the 8 -bit data stream 10001100:
# include
# include
Standards such as Ethernet modify the algorithm:
- The starting value is 111 ... 111 is used ( this corresponds to an inversion of the first 32 bits in the data stream ).
- If the data stream of bytes, the least significant bit first.
- All bits in the result is inverted and the bit order is rotated, that is, the most significant bit first appears.
The following program calculates one modified CRC value:
# include
# include
The following Pascal program calculates a CRC-16 value is above an array of bytes and outputs:
Const Mask: Word = $ A001; var CRC: Word; N, I: Integer; B: Byte; begin CRC: = $ FFFF; 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 Mask else CRC: = CRC shr 1; end; ShowMessage ( IntToHex (CRC, 4) ); / / Output end; Polynomials and types
The MHD column indicates the minimum Hamming distance, which distinguishes between two bit strings with valid CRC value. A CRC algorithm can thus detect any error that affects as MHD bit positions within the specified maximum length less. If the maximum length is exceeded, there is at each CRC algorithm, two -bit errors that are not detected (eg, two errors exactly length positions apart ).
CRC values are often referred to as a checksum, although the calculation of the check bits is done not only by (common ) addition. The term " checksum " was first used in connection with parity bits, which can be calculated as a sum over real. Here, the term has so pervasive that it has been adopted as a name for the calculation of general control bits.
The Prüfpolynome were selected from a plurality of possible polynomials such that for the code so generated "favorable" result properties. For example, if a polynomial has an even number of terms in x has (CRC16 - CCITT: 4 and CRC16 IBM: 4, but not CRC -4: 3 ), the binomial (x 1 ) as a factor in it. This binomial causes a " parity check ", whereby all errors with an odd number of flaws are apparent in each case in the resulting code.