Perform Cyclic Redundancy Check

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.

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

References

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