Learn more about Communications Toolbox

Cyclic Redundancy Check Coding

On this page…
Overview CRC Algorithm Selected Bibliography for CRC Coding

Overview

Cyclic redundancy check (CRC) coding is an error-control coding technique for detecting errors that occur when a message is transmitted. Unlike block or convolutional codes, CRC codes do not have a built-in error-correction capability. Instead, when an error is detected in a received message word, the receiver requests the sender to retransmit the message word.

In CRC coding, the transmitter applies a rule to each message word to create extra bits, called the checksum, or syndrome, and then appends the checksum to the message word. After receiving a transmitted word, the receiver applies the same rule to the received word. If the resulting checksum is nonzero, an error has occurred, and the transmitter should resend the message word.

Open the Error Detection and Correction library by double-clicking its icon in the main Communications Toolbox library. Open the CRC sublibrary by double-clicking on its icon in the Error Detection and Correction library.

Back to Top

CRC Algorithm

The CRC algorithm accepts a binary data vector, corresponding to a polynomial M, and appends a checksum of r bits, corresponding to a polynomial C. The concatenation of the input vector and the checksum then corresponds to the polynomial T = M*x^r + C, since multiplying by x^r corresponds to shifting the input vector r bits to the left. The algorithm chooses the checksum C so that T is divisible by a predefined polynomial P of degree r, called the generator polynomial.

The algorithm divides T by P, and sets the checksum equal to the binary vector corresponding to the remainder. That is, if T = Q*P + R, where R is a polynomial of degree less than r, the checksum is the binary vector corresponding to R. If necessary, the algorithm prepends zeros to the checksum so that it has length r.

The CRC generation feature, which implements the transmission phase of the CRC algorithm, does the following:

1. Left shifts the input data vector by r bits and divides the corresponding polynomial by P.

2. Sets the checksum equal to the binary vector of length r, corresponding to the remainder from step 1.

3. Appends the checksum to the input data vector. The result is the output vector.

The CRC detection feature computes the checksum for its entire input vector, as described above.

The CRC algorithm uses binary vectors to represent binary polynomials, in descending order of powers. For example, the vector [1 1 0 1] represents the polynomial x³ + x² + 1.

Note   The implementation described in this section is one of many valid implementations of the CRC algorithm. Different implementations can yield different numerical results.

Bits enter the linear feedback shift register (LFSR) from the lowest index bit to the highest index bit. The sequence of input message bits represents the coefficients of a message polynomial in order of decreasing powers. The message vector is augmented with r zeros to flush out the LFSR, where r is the degree of the generator polynomial. If the output from the leftmost register stage d(1) is a 1, then the bits in the shift register are XORed with the coefficients of the generator polynomial. When the augmented message sequence is completely sent through the LFSR, the register contains the checksum [d(1) d(2) . . . d(r)]. This is an implementation of binary long division, in which the message sequence is the divisor (numerator) and the polynomial is the dividend (denominator). The CRC checksum is the remainder of the division operation.

Back to Top

Selected Bibliography for CRC Coding

[1] Sklar, Bernard., Digital Communications: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice Hall, 1988.

[2] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.

Back to Top

Convolutional Coding

Interleaving

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS