28-11-2012, 05:10 PM
CRC Generating and Checking
CRC Generating and Checking.pdf (Size: 106.62 KB / Downloads: 23)
INTRODUCTION
This application note describes the Cyclic Redundancy
Check (CRC) theory and implementation. The CRC
check is used to detect errors in a message. Two implementations
are shown:
• Table driven CRC calculation
• Loop driven CRC calculation
This application describes the implementation of the
CRC-16 polynomial. However, there are several formats
for the implementation of CRC such as
CRC-CCITT, CRC-32 or other polynomials.
CRC is a common method for detecting errors in transmitted
messages or stored data. The CRC is a very
powerful, but easily implemented technique to obtain
data reliability.
THEORY OF OPERATION
The theory of a CRC calculation is straight forward. The
data is treated by the CRC algorithm as a binary number.
This number is divided by another binary number
called the polynomial. The rest of the division is the
CRC checksum, which is appended to the transmitted
message. The receiver divides the message (including
the calculated CRC), by the same polynomial the transmitter
used. If the result of this division is zero, then the
transmission was successful. However, if the result is
not equal to zero, an error occurred during the transmission.
The CRC-16 polynomial is shown in Equation 1. The
polynomial can be translated into a binary value,
because the divisor is viewed as a polynomial with
binary coefficients. For example, the CRC-16 polynomial
translates to 1000000000000101b. All coefficients,
like x2 or x15, are represented by a logical 1 in
the binary value.
Example Calculation
In this example calculation, the message is two bytes
long. In general, the message can have any length in
bytes. Before we can start calculating the CRC value 1,
the message has to be augmented by n-bits, where n
is the length of the polynomial. The CRC-16 polynomial
has a length of 16-bits, therefore, 16-bits have to be
augmented to the original message. In this example
calculation, the polynomial has a length of 3-bits, therefore,
the message has to be extended by three zeros at
the end. An example calculation for a CRC is shown in
Example 1. The reverse calculation is shown in
Example 2.
TABLE DRIVEN CRC IMPLEMENTATION
A table driven CRC routine uses a different technique
than a loop driven CRC routine. The idea behind a
table driven CRC implementation is that instead of calculating
the CRC bit by bit, precomputed bytes are
XORed to the data. The source code for the table
driven implementation is given in Appendix B.
The advantage of the table driven implementation is
that it is faster than the loop driven solution. The drawback
is that it consumes more program memory
because of the size of the look-up table.