Cyclic Redundancy Check Data Link Error Detection / Correction Method

CRC error detection computes the remainder of a polynomial division of a generator polynomial into a message. The remainder, which is usually 16 or 32 bits, is then appended to the message. When another remainder is computed, a nonzero value indicates an error. Depending on the generator polynomial's size, the process can fail in several ways, however. It is very difficult to determine how effective a given CRC will be at detecting errors.

The probability p that a completely random (bad) message will be incorrectly accepted as valid (not detected as a CRC error), is completely a function of the code rate: p = 2^-r = 2^{-(n - k)}. Where

r is the number of redundant bits (32 bits for CRC-32) (equal to n-k)
k is the number of original bits of data
n is the number of bits of the transmitted message = k+r

Use of the CRC technique for error correction normally requires the ability to send retransmission requests back to the data source.

Dr. Imre Bartfai's CRC16 and 32 for the PIC and SX microcontrollers see also: http://www.dalsemi.com/DocControl/PDFs/app27.pdf
Super fast CRC16 By Nikolai Golovchenko for the SX microcontroller
CRC16 by Charles Ader with matching CRC routines for SX, PIC, 8051, and x86
PIC Microcontroller Bit Math Method - CRC16 - standard X.25 (and XMODEM)
Ken Websters PIC16C74 serial port multiplexer. This includes checksum code for both the PIC and C++ code for the PC.
Painless guide to CRC by Ross Williams; The CRC Pitstop by Ross Williams
CRC online Calculator and Examples
CRC C code
a very compact (no-tables) CRC-16 function in C (for Modbus) from Spehro Pefhany. (CRC-16 implementations using tables are *much* faster, but also require more program space).
a very compact (no-tables) CRC-32 function in x86 machine language from Wayne Diamond
"winzip crc function": very compact (no tables) CRC-32 function written in standard C language, no branch misprediction by by Scott Duplichan
"Using Cyclical Redundancy Codes (CRC-16, CRC-32 etc.) on microcontrollers": CRC-16 and CRC-32 in C, both with and without tables. by Derek.
"How do I generate a CRC (Cyclic Redundancy Check) using a PIC?" a very compact (no-tables) CRC-16 function in PIC assembly (for X.25 and XMODEM) from Andrew Warren.
CRC Delphi and BASM Code
16 BIT CRC for XMODEM
Quick CRC Methods for XMODEM
see also:
- http://atlas.csd.net/~cgadd/knowbase/CRC0001.HTM for x86 asm code
- http://www.agt.net/public/aerosoft/checks.htm
- "Anyone want to do a term paper on CRCs?" http://blog.softwaresafety.net/2009/03/any-one-want-to-do-term-paper-on-crcs.html

Comments:

There is a little mistake in the sentence regarding the probability that a random code word is not detectable as an error: It is not 1 - 2^-r but 2^-r instead (r = n - k). 1 - 2^-r gives the rate of detectable errors !
Oops, you are right. I hope it's fixed now. Thank you.

David A Cary Says:

16-bit CRC routine (isochronous) for the polynomial 0x8005
Scott Dattalo, Dave Dribin (2002-08-24)
http://www.piclist.com/techref/postbot.asp?by=time&id=piclist\2002\08\24\233838a&tgt=post

A quick guide to CRC: With example calcuation of CRC 16 by Pierre Desrochers