Next: Graphing, Previous: Discrete Fourier Transform, Up: Mathematical Packages [Contents][Index]

`(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 byte-order and bit-order of the data stream;
- whether the CRC or its inverse is being calculated;
- the initial CRC value; and
- whether and where the CRC value is appended (inverted or non-inverted) to the data stream.

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:

- Philip Koopman and Tridib Chakravarty,

“Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks”,

The International Conference on Dependable Systems and Networks, DSN-2004.

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`.

- 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.

Next: Graphing, Previous: Discrete Fourier Transform, Up: Mathematical Packages [Contents][Index]