Communications Blockset™

Cyclic Redundancy Check Coding

Section 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 Blockset library. Open the CRC sublibrary by double-clicking on its icon in the Error Detection and Correction library.

Back to Top

CRC-Coding Features of the Blockset

The CRC library contains four blocks that implement the CRC algorithm:

• General CRC Generator

• General CRC Syndrome Detector

• CRC-N Generator

• CRC-N Syndrome Detector

The General CRC Generator block computes a checksum for each input frame, appends it to the message word, and transmits the result. The General CRC Syndrome Detector block receives a transmitted word and calculates its checksum. The block has two outputs. The first is the message word without the transmitted checksum. The second output is a binary error flag, which is 0 if the checksum computed for the received word is zero, and 1 otherwise.

The CRC-N Generator block and CRC-N Syndrome Detector block are special cases of the General CRC Generator block and General CRC Syndrome Detector block, which use a predefined CRC-N polynomial, where N is the number of bits in the checksum.

Back to Top

CRC Algorithm

The CRC algorithm accepts a binary data frame, corresponding to a polynomial M, and appends a checksum of r bits, corresponding to a polynomial C. The concatenation of the input frame and the checksum then corresponds to the polynomial T = M*x^r + C, since multiplying by x^r corresponds to shifting the input frame 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 General CRC Generator block and the CRC-N Generator block, which implement the transmission phase of the CRC algorithm, do the following:

1. Left shift the input data frame by r bits and divide the corresponding polynomial by P.

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

3. Append the checksum to the input data frame. The result is the output frame.

The General CRC Syndrome Detector block and the CRC-N Syndrome Detector block implement the detection phase of the CRC algorithm. Each of these blocks computes the checksum for its entire input frame, as described above. The block's second output port issues a 0 if the checksum computation yields a zero value, and a 1 otherwise.

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.

Example

Suppose the input frame is [1 1 0 0 1 1 0]', corresponding to the polynomial M = x⁶ +x ⁵ + x² + x, and the generator polynomial is P = x³ + x² + 1, of degree r = 3. By polynomial division, M*x³ = (x⁶ + x³ + x)*P + x. The remainder is R = x, so that the checksum is then [0 1 0]'. An extra 0 is added on the left to make the checksum have length 3.

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