Main Content

This example shows how to perform a *cyclic redundancy check* (CRC) on the bits of a number. CRCs are used to detect errors in the transmission of data in digital systems. When a piece of data is sent, a short *check value* is attached to it. The check value is obtained by polynomial division with the bits in the data. When the data is received, the polynomial division is repeated, and the result is compared with the check value. If the results differ, then the data was corrupted during transmission.

Start with a 16-bit binary number, which is the message to be transmitted:

1101100111011010

To obtain the check value, divide this number by the polynomial ${\mathit{x}}^{3}+{\mathit{x}}^{2}+\mathit{x}+1$. You can represent this polynomial with its coefficients: `1111`

.

The division is performed in steps, and after each step the polynomial divisor is aligned with the left-most 1 in the number. Because the result of dividing by the four term polynomial has three bits (in general dividing by a polynomial of length $\mathit{n}+1$ produces a check value of length $\mathit{n}$), append the number with `000`

to calculate the remainder. At each step, the result uses the bit-wise XOR of the four bits being operated on, and all other bits are unchanged.

The first division is

1101100111011010 000 1111 ---------------- 0010100111011010 000

Each successive division operates on the result of the previous step, so the second division is

0010100111011010 000 1111 ---------------- 0001010111011010 000

The division is completed once the dividend is all zeros. The complete division, including the above two steps, is

1101100111011010 000 1111 0010100111011010 000 1111 0001010111011010 000 1111 0000101111011010 000 1111 0000010011011010 000 1111 0000001101011010 000 1111 0000000010011010 000 1111 0000000001101010 000 1111 0000000000010010 000 1111 0000000000001100 000 1111 0000000000000011 000 11 11 0000000000000000 110

The remainder bits, `110`

, are the check value for this message.

In MATLAB®, you can perform this same operation to obtain the check value using bit-wise operations. First, define variables for the message and polynomial divisor. Use unsigned 32-bit integers so that extra bits are available for the remainder.

message = 0b1101100111011010u32; messageLength = 16; divisor = 0b1111u32; divisorDegree = 3;

Next, initialize the polynomial divisor. Use `dec2bin`

to display the bits of the result.

divisor = bitshift(divisor,messageLength-divisorDegree-1); dec2bin(divisor)

ans = '1111000000000000'

Now, shift the divisor and message so that they have the correct number of bits (16 bits for the message and 3 bits for the remainder).

divisor = bitshift(divisor,divisorDegree); remainder = bitshift(message,divisorDegree); dec2bin(divisor)

ans = '1111000000000000000'

dec2bin(remainder)

ans = '1101100111011010000'

Perform the division steps of the CRC using a `for`

loop. The `for`

loop always advances a single bit each step, so include a check to see if the current digit is a 1. If the current digit is a 1, then the division step is performed; otherwise, the loop advances a bit and continues.

for k = 1:messageLength if bitget(remainder,messageLength+divisorDegree) remainder = bitxor(remainder,divisor); end remainder = bitshift(remainder,1); end

Shift the bits of the remainder to the right to get the check value for the operation.

CRC_check_value = bitshift(remainder,-messageLength); dec2bin(CRC_check_value)

ans = '110'

You can use the check value to verify the integrity of a message by repeating the same division operation. However, instead of using a remainder of `000`

to start, use the check value `110`

. If the message is error free, then the result of the division will be zero.

Reset the remainder variable, and add the CRC check value to the remainder bits using a bit-wise OR. Introduce an error into the message by flipping one of the bit values with `bitset`

.

remainder = bitshift(message,divisorDegree); remainder = bitor(remainder,CRC_check_value); remainder = bitset(remainder,6); dec2bin(remainder)

ans = '1101100111011110110'

Perform the CRC division operation and then check if the result is zero.

for k = 1:messageLength if bitget(remainder,messageLength+divisorDegree) remainder = bitxor(remainder,divisor); end remainder = bitshift(remainder,1); end if remainder == 0 disp('Message is error free.') else disp('Message contains errors.') end

Message contains errors.

[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.