8.3 Detection and Control of Errors
337
polynomial is that it is simple to visualize and perform the division mathematically.
Numerous varieties of cyclic redundancy check polynomials have been incorporated
into technical standards. This can be confusing to developers because they need to
select a polynomial according to the application requirements. Table 8.3 shows examples of several commonly used polynomials and their binary equivalents for the CRC
generation [31, 32]. The most commonly used polynomial lengths are designated as
CRC-8, CRC-16, CRC-32, and CRC-64. The numbers 8, 16, 32, and 64, respectively,
refer to the size of the CRC remainder. Thus the CRC divisors for these polynomials
are 9, 17, 33, and 65 bits, respectively. Various CRC-8 polynomials are used in applications such as Bluetooth and mobile wireless networks, whereas a usage example
of CRC-32 is in IEEE-802 LANs. CRC-16 is used in bit-oriented protocols, such as
the High-Level Data Link Control (HDLC) Standard, where frames are viewed as a
collection of bits. A polynomial needs to have the following properties:
• It should not be divisible by x. This condition guarantees that the CRC can detect
all burst errors that have a length less than or equal to the degree of the polynomial.
• It should be divisible by x + 1. This allows the CRC to detect all bursts that affect
an odd number of bits.
Given these two rules, the CRC also can find with an error-detection probability.
P ed = 1 − 1/2
N
(8.29)
any burst errors that have a length greater than the degree N of the generator
polynomial.
Example 8.9 The generator polynomial x
7
+ x
5
+ x
2
+ x + 1 can be written as
1 × x
7
+ 0 × x
6
+ 1 × x
5
+ 0 × x
4
+ 0 × x
3
+ 1 × x
2
+ 1 × x
1
+ 1 × x
0
where the exponents on the variable x represent bit positions in a binary number
and the coefficients correspond to the binary digits at these positions. Thus the
generator polynomial given here corresponds to the 8-bit binary representation
10100111.
Example 8.10 The generator polynomial x
3
+ x + 1 can be written in binary form
as 1011. For the example information unit 11110 the CRC can be found through
either binary or algebraic division using steps 1 through 3 outlined earlier. Because
Table 8.3 Commonly used polynomials and their binary equivalents for CRC generation
CRC type Generator polynomial
Binary equivalent
CRC-8
x 8 + x 2 + x + 1
100000111
CRC-16 x 16 + x 15 + x 2 + 1
11000000000000101
CRC-32 x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11
+ x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1
100000100110000010001110110110111
337
polynomial is that it is simple to visualize and perform the division mathematically.
Numerous varieties of cyclic redundancy check polynomials have been incorporated
into technical standards. This can be confusing to developers because they need to
select a polynomial according to the application requirements. Table 8.3 shows examples of several commonly used polynomials and their binary equivalents for the CRC
generation [31, 32]. The most commonly used polynomial lengths are designated as
CRC-8, CRC-16, CRC-32, and CRC-64. The numbers 8, 16, 32, and 64, respectively,
refer to the size of the CRC remainder. Thus the CRC divisors for these polynomials
are 9, 17, 33, and 65 bits, respectively. Various CRC-8 polynomials are used in applications such as Bluetooth and mobile wireless networks, whereas a usage example
of CRC-32 is in IEEE-802 LANs. CRC-16 is used in bit-oriented protocols, such as
the High-Level Data Link Control (HDLC) Standard, where frames are viewed as a
collection of bits. A polynomial needs to have the following properties:
• It should not be divisible by x. This condition guarantees that the CRC can detect
all burst errors that have a length less than or equal to the degree of the polynomial.
• It should be divisible by x + 1. This allows the CRC to detect all bursts that affect
an odd number of bits.
Given these two rules, the CRC also can find with an error-detection probability.
P ed = 1 − 1/2
N
(8.29)
any burst errors that have a length greater than the degree N of the generator
polynomial.
Example 8.9 The generator polynomial x
7
+ x
5
+ x
2
+ x + 1 can be written as
1 × x
7
+ 0 × x
6
+ 1 × x
5
+ 0 × x
4
+ 0 × x
3
+ 1 × x
2
+ 1 × x
1
+ 1 × x
0
where the exponents on the variable x represent bit positions in a binary number
and the coefficients correspond to the binary digits at these positions. Thus the
generator polynomial given here corresponds to the 8-bit binary representation
10100111.
Example 8.10 The generator polynomial x
3
+ x + 1 can be written in binary form
as 1011. For the example information unit 11110 the CRC can be found through
either binary or algebraic division using steps 1 through 3 outlined earlier. Because
Table 8.3 Commonly used polynomials and their binary equivalents for CRC generation
CRC type Generator polynomial
Binary equivalent
CRC-8
x 8 + x 2 + x + 1
100000111
CRC-16 x 16 + x 15 + x 2 + 1
11000000000000101
CRC-32 x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11
+ x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1
100000100110000010001110110110111