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 +

See also:

• http://homepages.tesco.net/~rainstorm/crc-catalogue.htm Catalogue of known CRC algorithms with fast code for 6502, ARM and 8080/Z80+

Code:

  .