Download Programming Embedded Systems By Michael Barr, Anthony Massa

Chapter 6. Memory
Page 15 of 18
data errorsor even how they are implementedto take advantage of their ability to detect errors.
Here's a very brief explanation of the mathematics. When computing a CRC, think of the set of data as a very long string of 1s and 0s
(called the message). This binary string is dividedin a rather peculiar wayby a smaller fixed binary string called the generator polynomial.
The remainder of this binary long division is the CRC checksum. By carefully selecting the generator polynomial for certain desirable
mathematical properties, you can use the resulting checksum to detect most (but never all) errors within the message. The strongest of
these generator polynomials are able to detect all single- and double-bit errors, and all odd-length strings of consecutive error bits. In
addition, greater than 99.99 percent of all burst errorsdefined as a sequence of bits that has one error at each endcan be detected.
Together, these types of errors account for a large percentage of the possible errors within any stored or transmitted binary message.
Generator polynomials with the best error-detection capabilities are frequently adopted as international standards. Two such standards are
described in Table 6-4. Associated with each standard are its width (in bits), the generator polynomial, a binary representation of the
polynomial (called the divisor), an initial value for the remainder, and a value to exclusive OR operation (XOR) with the final remainder.
[*]
[*] The divisor is simply a binary representation of the coefficients of the generator polynomial, each of which is either 0 or
1. To make this even more confusing, the highest-order coefficient of the generator polynomial (always a 1) is left out of the
binary representation. For example, the polynomial in CRC16 has four nonzero coefficients. But the corresponding binary
representation has only three 1s in it (bits 15, 2, and 0).
Table 6-4. International standard CRC parameters
Parameters
CRC16
CRC32
Checksum size (width)
16 bits
Generator polynomial
x16
Divisor (polynomial)
0x8005
0x04C11DB7
Initial remainder
0x0000
0xFFFFFFFF
Final XOR value
0x0000
0xFFFFFFFF
+ x15
32 bits
+ x2
+1
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1
The following code can be used to compute any CRC formula that has a similar set of parameters. To make this as easy as possible, we
have defined all of the CRC parameters as constants. To select the CRC parameters according to the desired standard, define one (and
only one) of the macros CRC16 or CRC32.
/* The CRC parameters. Currently configured for CRC16. */
#define CRC_NAME
"CRC16"
#define POLYNOMIAL
0x8005
#define INITIAL_REMAINDER
0x0000
#define FINAL_XOR_VALUE
0x0000
#define REFLECT_DATA
TRUE
#define REFLECT_REMAINDER
TRUE
#define CHECK_VALUE
0xBB3D
/* The width of the CRC calculation and result. */
typedef uint16_t crc_t;
#define WIDTH
#define TOPBIT
(8 * sizeof(crc_t))
(1 << (WIDTH - 1))
The function crcCompute can be called over and over from your application to compute and verify CRC checksums.
/*********************************************************************
*
* Function:
crcCompute
*
* Description: Compute the CRC of a given message.
*
* Notes:
*
* Returns:
The CRC of the message.
*
*********************************************************************/
crc_t crcCompute(uint8_t const message[], uint32_t numBytes)
{
crc_t
remainder = INITIAL_REMAINDER;
uint32_t byte;
int
nBit;
file://C:\Documents and Settings\Amir\Local Settings\Temp\~hhEF0E.htm
3/30/2007