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 x 3 + x 2 + 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 leftmost 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 n + 1 produces a check value of length 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
2 Program Components
2-44
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 x 3 + x 2 + 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 leftmost 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 n + 1 produces a check value of length 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
2 Program Components
2-44