Communications Blockset    

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*xr + C, since multiplying by xr 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, then 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, which implement the detection phase of the CRC algorithm, do the following:

  1. Remove the checksum from the received input frame.
  2. Compute the checksum for the received message word as in the transmission phase.
  3. Compare the new checksum with the received checksum.
  4. Output a 0 if the two checksums agree 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 x3 + x2 + 1.

Example

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


  CRC Coding Features of the Blockset Interleaving