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:
To obtain the check value, divide this number by the polynomial . You can represent this polynomial with its coefficients:
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 produces a check value of length ), 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'
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
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.
 Sklar, Bernard. Digital Communications: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.
 Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.