CRC RevEng

CRC RevEng

[ Home | Up | Prev | Next | Disclaimer ]

Summary of the CRC Catalogue

Summary of the CRC catalogue
CRC width (bits) Records
Attested Confirmed Academic Third-party Total
322
422
51113
6235
733
897117
10123
11112
1244
1311
14112
15112
161942429
1711
2111
24437
3011
3111
327310
4011
641214
8211
Total4910376102

Legend

Evidence classes

I
Primary documents. Evidence from a standards document (official or de facto) defining a protocol that uses the CRC algorithm.
II
Implementations. A widely-available implementation that can calculate CRCs for any desired message.
III
Secondary documents. Evidence from documents other than standards documents.
IV
Codewords. Valid message-CRC pairs from any source. Trivial codewords are simple sums of the algorithm parameters and/or simple multiples of the generator polynomial, and show insufficient calculation complexity to validate an algorithm. These are collected in the Catalogue only for illustration.

Model classes

Attested
The algorithm is evidenced by its definition in a primary document, plus one or more of the following:
Confirmed
The algorithm is evidenced by a widely-available implementation that can calculate CRCs for any desired message.
Academic
It has not been confirmed that CRCs are actually calculated in the field according to this record.
Third-party
All parameters and codewords originate from unofficial sources.

Model parameters

width
The number of bit cells in the linear feedback shift register; the degree of the generator polynomial, less one.
poly
The generator polynomial that sets the feedback tap positions of the shift register. poly is written in the hexadecimal, direct notation found in MSB-first code. The least significant bit corresponds to the inward end of the shift register, and is always set. The highest-order term is omitted.
init
The settings of the bit cells at the start of each calculation, before reading the first message bit. init is written in the hexadecimal, direct notation found in MSB-first code. The least significant bit corresponds to the inward end of the shift register.
refin
If equal to false, specifies that the characters of the message are read bit-by-bit, most significant bit (MSB) first; if equal to true, the characters are read bit-by-bit, least significant bit (LSB) first. Each sampled message bit is then XORed with the bit being simultaneously shifted out of the register at the most significant end, and the result is passed to the feedback taps.
refout
If equal to false, specifies that the contents of the register after reading the last message bit are unreflected before presentation; if equal to true, it specifies that they are reflected, character-by-character, before presentation. For the purpose of this definition, the reflection is performed by swapping the content of each cell with that of the cell an equal distance from the opposite end of the register; the characters of the CRC are then true images of parts of the reflected register, the character containing the original MSB always appearing first.
xorout
The XOR value applied to the contents of the register after the last message bit has been read and after the optional reflection. xorout is written in hexadecimal notation, having the same endianness as the CRC such that its true image appears in the characters of the CRC.
check
The contents of the register after initialising, reading the UTF-8 string "123456789" (as 8-bit characters), optionally reflecting, and applying the final XOR.
residue
The contents of the register after initialising, reading an error-free codeword and optionally reflecting the register (if refout=true), but not applying the final XOR. This is mathematically equivalent to initialising the register with the xorout parameter, reflecting it as described (if refout=true), reading as many zero bits as there are cells in the register, and reflecting the result (if refin=true). The residue of a crossed-endian model is calculated assuming that the characters of the received CRC are specially reflected before submitting the codeword.
name
The name assigned to the model in this Catalogue.

Model notes

Unique effective solution of codeword set
This model is the only one at the specified width that solves all the codewords listed in the model entry. Aliases of the model may exist (differing in Init, XorOut and Residue values) but they produce identical results at all message lengths.

References

Robert Bosch GmbH (September 1991), CAN 2.0 Specification.

Robert Bosch GmbH, E-Ray FlexRay IP Module Documentation and Application Notes.

Dipl. Inf. Johann N. Löfflmann (30 July 2006), Jacksum. CRC and hash calculator in Java.

Thomas Pircher (6 January 2016), pycrc. Python based parametrised CRC calculator and C code generator.

William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling (1992), Numerical recipes in C: The art of scientific computing. 2nd ed. Cambridge: Cambridge University Press. ISBN 0-521-43108-5

Ross N. Williams (19 August 1993), "A Painless Guide to CRC Error Detection Algorithms".

Useful links

Lammert Bies (August 2011), "On-line CRC calculation and free library".

Lammert Bies, "Error detection and correction" Web forum.

Wolfgang Ehrhardt (27 March 2012), CRC / HASH utilities and plugin for FAR Manager.

Jonathan Graham Harston (21–23 June 2011), "Source Code for Calculating CRCs".

PicList MassMind, "Cyclic Redundancy Check error detection".

Sven Reifegerste (30 October 2006), Parametrised online CRC calculator.

Tom Torfs, IOCCC winning entry, 1998, CRC generator.

Disclaimer

Every effort has been made to ensure accuracy, however there may be occasional errors or omissions. All trademarks and registered trademarks are the intellectual property of their respective owners. The code and documentation included in this document are supplied without warranty, not even the implied warranties of merchantability or fitness for a particular purpose. In no event shall the author or his suppliers be liable for any loss, damage, injury or death, of any nature and howsoever caused, arising from the use of, or failure, inability or unwillingness to use, this software or documentation.

[ Top of page ]


Appendix

Map of common 16-bit CRC algorithms.

Karnaugh map of the most common 16-bit CRCs, with Check values and algorithm citations. All values are hexadecimal.
"123456789"
(UTF-8)
Polynomial 1021 8005
Reflected? False True False
Initial value Final XOR
0000 0000 31C3
(XMODEM)
2189
(KERMIT)
BB3D
(ARC)
FEE8
(BUYPASS)
FFFF CE3C
(GSM)
DE76
(–)
44C2
(MAXIM)
0117
(–)
FFFF D64E
(GENIBUS)
906E
(X.25)
B4C8
(USB)
5118
(–)
0000 29B1
(FALSE CCITT)
6F91
(MCRF4XX)
4B37
(MODBUS)
AEE7
(CMS)

Greg Cook, [email address]
http://reveng.sourceforge.net/crc-catalogue/legend.htm Last updated 20 June 2017
Links last verified 20 October 2016

Valid HTML 4.01 Strict. Project web hosted by SourceForge.net

[ Top of page ]