ITWissen.info - Tech know how online

cyclic redundancy checksum (CRC)

Cyclic block check, Cyclic RedundancyChecksum (CRC), is an error detection method in which check characters are formed on the basis of binary numbers by summing the data groups before they are transmitted.

Cyclic block checking is based on the division of polynomials. In this method, the n bits of a data block are interpreted as coefficients of a polynomial U(x) of degree n-1. The generated polynomial G(x) depends on the degree k. A polynomial with k = 16, as provided by the International Telecommunication Union (ITU), looks like this: x exp16 + x exp12 + x exp5 + 1.

The principle of cyclic block checking

Various generator polynomials of the cyclic block check (CRC)

Various generator polynomials of the cyclic block check (CRC)

In principle, in the cyclic block check the bits to be monitored are shifted one after the other into a feedback shift register. The length as well as the number and position of the feedback taps are specified depending on the procedure; thus, a checksum procedure with a four-digit register is called CRC-4. The checksum procedure detects single errors reliably, multiple errors with high probability. The receiver checks the CRC value of each received data packet and removes the check function before releasing the data packet to the receiving station. For each bit pattern to be transmitted, either 16 or 32, sometimes 64, check bits are calculated and transmitted after the information section in the FCS field.

The block check and the generator polynomial

Code-unbound error checking (CRC) is performed using a suitable generator polynomial, e.g., x exp16 + x exp12 + x exp5 + 1. The binary characters of the data block to be saved are used as the coefficient of the polynomial and divided by said polynomial modulo 2. The remainder after the division represents the block check string and is sent out with the data block to be transmitted. In the receiving station, transmission errors are detected with a very high probability when the above rule is applied, because the modulo 2 division of the fixed sequence of binary characters by the generator polynomial should result in a constant remainder, and a deviation due to a transmission error immediately leads to another remainder class.

The safety of the method is based on the most "favorable" residue class decomposition possible, which in turn depends on the chosen generator polynomial. The more different residue classes are generated, the lower the probability that an original bit sequence and a corrupted bit sequence fall into the same residue class after the operation. However, the number of residue classes is also limited by the number of bits available in the data packet for representing the residue.

Informationen zum Artikel
Englisch: cyclic redundancy checksum - CRC
Updated at: 03.01.2019
#Words: 775
Links: