Next: , Previous: Discrete Fourier Transform, Up: Mathematical Packages


5.8 Cyclic Checksum

(require 'crc) Cyclic Redundancy Checks using Galois field GF(2) polynomial arithmetic are used for error detection in many data transmission and storage applications.

The generator polynomials for various CRC protocols are availble from many sources. But the polynomial is just one of many parameters which must match in order for a CRC implementation to interoperate with existing systems:

The performance of a particular CRC polynomial over packets of given sizes varies widely. In terms of the probability of undetected errors, some uses of extant CRC polynomials are suboptimal by several orders of magnitude.

If you are considering CRC for a new application, consult the following article to find the optimum CRC polynomial for your range of data lengths:


http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

There is even some controversy over the polynomials themselves.

— Constant: crc-32-polynomial

For CRC-32, http://www2.sis.pitt.edu/~jkabara/tele-2100/lect08.html gives x^32+x^26+x^23+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+1.

But http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://spinroot.com/spin/Doc/Book91_PDF/ch3.pdf, http://www.erg.abdn.ac.uk/users/gorry/course/dl-pages/crc.html, http://www.rad.com/networks/1994/err_con/crc_most.htm, and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, http://www.nobugconsulting.ro/crc.php give x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.

SLIB crc-32-polynomial uses the latter definition.

— Constant: crc-ccitt-polynomial

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www2.sis.pitt.edu/~jkabara/tele-2100/lect08.html, and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html give CRC-CCITT: x^16+x^12+x^5+1.

— Constant: crc-16-polynomial

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, and http://www.usb.org/developers/data/crcdes.pdf give CRC-16: x^16+x^15+x^2+1.

— Constant: crc-12-polynomial

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, and http://spinroot.com/spin/Doc/Book91_PDF/ch3.pdf give CRC-12: x^12+x^11+x^3+x^2+1.

But http://www.ffldusoe.edu/Faculty/Denenberg/Topics/Networks/Error_Detection_Correction/crc.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.eng.uwi.tt/depts/elec/staff/kimal/errorcc.html, http://www.ee.uwa.edu.au/~roberto/teach/itc314/java/CRC/, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, and http://www.efg2.com/Lab/Mathematics/CRC.htm give CRC-12: x^12+x^11+x^3+x^2+x+1.

These differ in bit 1 and calculations using them return different values. With citations near evenly split, it is hard to know which is correct. Thanks to Philip Koopman for breaking the tie in favor of the latter (#xC07).

— Constant: crc-10-polynomial

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html gives CRC-10: x^10+x^9+x^5+x^4+1; but http://cell-relay.indiana.edu/cell-relay/publications/software/CRC/crc10.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, http://www.techfest.com/networking/atm/atm.htm, http://www.protocols.com/pbook/atmcell2.htm, and http://www.nobugconsulting.ro/crc.php give CRC-10: x^10+x^9+x^5+x^4+x+1.

— Constant: crc-08-polynomial

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, and http://www.nobugconsulting.ro/crc.php give CRC-8: x^8+x^2+x^1+1

— Constant: atm-hec-polynomial

http://cell-relay.indiana.edu/cell-relay/publications/software/CRC/32bitCRC.tutorial.html and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html give ATM HEC: x^8+x^2+x+1.

— Constant: dowcrc-polynomial

http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html gives DOWCRC: x^8+x^5+x^4+1.

— Constant: usb-token-polynomial

http://www.usb.org/developers/data/crcdes.pdf and http://www.nobugconsulting.ro/crc.php give USB-token: x^5+x^2+1.

Each of these polynomial constants is a string of ‘1’s and ‘0’s, the exponent of each power of x in descending order.

— Function: crc:make-table poly

poly must be string of ‘1’s and ‘0’s beginning with ‘1’ and having length greater than 8. crc:make-table returns a vector of 256 integers, such that:

          (set! crc
                (logxor (ash (logand (+ -1 (ash 1 (- deg 8))) crc) 8)
                        (vector-ref crc-table
                                    (logxor (ash crc (- 8 deg)) byte))))

will compute the crc with the 8 additional bits in byte; where crc is the previous accumulated CRC value, deg is the degree of poly, and crc-table is the vector returned by crc:make-table.

If the implementation does not support deg-bit integers, then crc:make-table returns #f.

— Function: cksum file

Computes the P1003.2/D11.2 (POSIX.2) 32-bit checksum of file.

          (require 'crc)
          (cksum (in-vicinity (library-vicinity) "ratize.scm"))
          ⇒ 157103930
— Function: cksum port

Computes the checksum of the bytes read from port until the end-of-file.

cksum-string, which returns the P1003.2/D11.2 (POSIX.2) 32-bit checksum of the bytes in str, can be defined as follows:

     (require 'string-port)
     (define (cksum-string str) (call-with-input-string str cksum))
— Function: crc16 file

Computes the USB data-packet (16-bit) CRC of file.

— Function: crc16 port

Computes the USB data-packet (16-bit) CRC of the bytes read from port until the end-of-file.

crc16 calculates the same values as the crc16.pl program given in http://www.usb.org/developers/data/crcdes.pdf.

— Function: crc5 file

Computes the USB token (5-bit) CRC of file.

— Function: crc5 port

Computes the USB token (5-bit) CRC of the bytes read from port until the end-of-file.

crc5 calculates the same values as the crc5.pl program given in http://www.usb.org/developers/data/crcdes.pdf.