Perform Cyclic Redundancy Check

Calculate Check Value by Hand

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.

Calculate Check Value Programmatically

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'

Check Message Integrity

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.