-
Notifications
You must be signed in to change notification settings - Fork 0
[[App Note 27|http://www.maxim-ic.com/app-notes/index.mvp/id/27]] shows both a 256 byte table lookup method and a tableless non-looping computation (CRC16)
[[avr-libc crc-16|http://www.nongnu.org/avr-libc/user-manual/grouputilcrc.html]] links to the dalas appnote 27 and has looping calculations for crc-16, and crc-xmodem. Non-looping calculation for crc-ccitt.
[[Error Correction and Detection|http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/ecc.html]] explains the equivalence between crc and modulo-2 division
[[Painless guide to crc error detection algorithms|http://www.repairfaq.org/filipg/LINK/F_crc_v32.html]]
[[CRC Selection for Embedded Network Messages|http://www.ece.cmu.edu/~koopman/crc/index.html]] has a large listing of various CRC polynomials with their efficiency and ability to detect errors of various hamming distances.
Another variations that is faster than the original bit-by-bit approach and that also eliminates the look-up storage of the table approach is the bytewide shifting algorithm. A bytewide approach eliminates seven bit-by-bit test-and-jump operations which are a significant overhead in the bit-by-bit version, and also takes advantage of fast shift and parallel-logic operations available on most processors (as well as some high-level languages such as Turbo Pascal or C).
First we need some algebra: By giving each CRC register bit and each data bit a separate symbol, we can express the result of a CRC operation symbolically. Each bit of the CRC register will be represented by a formula showing all the data and original CRC bits which affect that bit in the result. If we take the exclusive-OR of the bits specified by the formula, we can directly compute any bit of the CRC result.
In order to generate the formulas for each bit of the CRC register, we create an algebraic analog of the shifting and combining process of the bit-by-bit CRC algorithm. Instead of shifting bit values (as in a normal shift register), we instead move the whole symbolic formula for each bit to the next higher bit position. Instead of actually performing an exclusive-OR operation, we concatenate the formula for the data bit to each of the affected bits in the CRC register, with a symbol indicating an exclusive-OR operation. If ever we find that we have two identical variables in any one formula, we can cancel and eliminate them both (because anything exclusive-ORed with itself is zero, and zero exclusive-ORed with any value is just that value).
After symbolically processing a whole byte of data, and eliminating common terms, we come up with a symbolic representation for each bit of the result. By factoring this expression into convenient computer operations, a program is obtained which utilizes the bit parallelism available in software.