Polynomial representations of cyclic redundancy checks

From Wikipedia, the free encyclopedia
Jump to: navigation, search

These are polynomial representations of cyclic redundancy checks CRCs.

Name Polynomial Representations: normal / reversed / reverse of reciprocal
CRC-1 x + 1 (most hardware; also known as parity bit) 0x1 / 0x1 / 0x1
CRC-4-ITU x^4 + x + 1 (ITU-T G.704, p. 12) 0x3 / 0xC / 0x9
CRC-5-EPC x^5 + x^3 + 1 (Gen 2 RFID[1]) 0x09 / 0x12 / 0x14
CRC-5-ITU x^5 + x^4 + x^2 + 1 (ITU-T G.704, p. 9) 0x15 / 0x15 / 0x1A
CRC-5-USB x^5 + x^2 + 1 (USB token packets) 0x05 / 0x14 / 0x12
CRC-6-ITU x^6 + x + 1 (ITU-T G.704, p. 3) 0x03 / 0x30 / 0x21
CRC-7 x^7 + x^3 + 1 (telecom systems, ITU-T G.707, ITU-T G.832, MMC, SD) 0x09 / 0x48 / 0x44
CRC-8-CCITT x^8 + x^2 + x + 1 (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99) 0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim x^8 + x^5 + x^4 + 1 (1-Wire bus) 0x31 / 0x8C / 0x98
CRC-8 x^8 + x^7 + x^6 + x^4 + x^2 + 1 0xD5 / 0xAB / 0xEA[2]
CRC-8-SAE J1850 x^8 + x^4 + x^3 + x^2 + 1 0x1D / 0xB8 / 0x8E
CRC-8-WCDMA x^8 + x^7 + x^4 + x^3 + x + 1[3] 0x9B / 0xD9 / 0xCD[2]
CRC-10 x^{10} + x^9 + x^5 + x^4 + x + 1 (ATM; ITU-T I.610) 0x233 / 0x331 / 0x319
CRC-11 x^{11} + x^9 + x^8 + x^7 + x^2 + 1 (FlexRay[4]) 0x385 / 0x50E / 0x5C2
CRC-12 x^{12} + x^{11} + x^3 + x^2 + x + 1 (telecom systems[5][6]) 0x80F / 0xF01 / 0xC07[2]
CRC-13-BBC x^{13} + x^{12} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^2 + 1 [1] [2] 0x1CF5 / 0x15E7 / 0x1E7A
CRC-15-CAN x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1 0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM x^{16} + x^{15} + x^2 + 1 (Bisync, Modbus, USB, ANSI X3.28, many others; also known as CRC-16 and CRC-16-ANSI) 0x8005 / 0xA001 / 0xC002
CRC-16-CCITT x^{16} + x^{12} + x^5 + 1 (X.25, V.41, HDLC, XMODEM, Bluetooth, SD, many others; known as CRC-CCITT) 0x1021 / 0x8408 / 0x8810[2]
CRC-16-T10-DIF x^{16} + x^{15} + x^{11} + x^{9} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 (SCSI DIF) 0x8BB7[7] / 0xEDD1 / 0xC5DB
CRC-16-DNP x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1 (DNP, IEC 870, M-Bus) 0x3D65 / 0xA6BC / 0x9EB2
CRC-16-DECT x^{16} + x^{10} + x^8 + x^7 + x^3 + 1 (cordless telephones)[8] 0x0589 / 0x91A0 / 0x82C4
CRC-16-Fletcher Not a CRC; see Fletcher's checksum Used in Adler-32 A & B CRCs
CRC-24 x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{11} + x^{10} + x^8 + x^7 + x^6 + x^3 + x + 1 (FlexRay[4]) 0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64  x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1 (OpenPGP) 0x864CFB / 0xDF3261 / 0xC3267D
CRC-30 x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{6} + x^{2} + x + 1 (CDMA) 0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler Not a CRC; see Adler-32 See Adler-32
CRC-32 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 (ISO 3309, ANSI X3.66, FIPS PUB 71, FED-STD-1003, ITU-T V.42, Ethernet, SATA, MPEG-2, Gzip, PKZIP, POSIX cksum, PNG,[9] ZMODEM) 0x04C11DB7 / 0xEDB88320 / 0x82608EDB[10]
CRC-32C (Castagnoli) x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1 (iSCSI & SCTP, G.hn payload, SSE4.2) 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0[10]
CRC-32K (Koopman) x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B[10]
CRC-32Q x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^{5} + x^{3} + x + 1 (aviation; AIXM[11]) 0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-40-GSM x^{40} + x^{26} + x^{23} + x^{17} + x^3 + 1 (GSM control channel[12][13]) 0x0004820009 / 0x9000412000 / 0x8002410004
CRC-64-ISO x^{64} + x^4 + x^3 + x + 1 (HDLC — ISO 3309, Swiss-Prot/TrEMBL; considered weak for hashing[14]) 0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA-182 x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1 (as described in ECMA-182 p. 51) 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

See also[edit]

General category

Specific technological references

External links[edit]

References[edit]

  1. ^ Class-1 Generation-2 UHF RFID Protocol. 1.2.0. EPCglobal. 23 October 2008. p. 35. Retrieved 21 May 2009. 
  2. ^ a b c d Koopman, Philip; Chakravarty, Tridib (28 June – 1 July 2004). "Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks". 2004 International Conference on Dependable Systems and Networks: 145–154. doi:10.1109/DSN.2004.1311885. ISBN 0-7695-2052-9. 
  3. ^ Richardson, Andrew (17 March 2005). WCDMA Handbook. Cambridge, UK: Cambridge University Press. p. 223. ISBN 0521828155. 
  4. ^ a b FlexRay Protocol Specification. 2.1 Revision A. Flexray Consortium. 22 December 2005. p. 93. 
  5. ^ Perez, A.; Wismer & Becker (1983). "Byte-Wise CRC Calculations". IEEE Micro 3 (3): 40–50. doi:10.1109/MM.1983.291120. 
  6. ^ Ramabadran, T.V.; Gaitonde, S.S. (1988). "A tutorial on CRC computations". IEEE Micro 8 (4): 62–75. doi:10.1109/40.7773. 
  7. ^ Thaler, Pat (28 August 2003). 16-bit CRC polynomial selection. INCITS T10. Retrieved 11 August 2009. 
  8. ^ ETSI EN 300 175-3. V2.2.1. Sophia Antipolis, France: European Telecommunications Standards Institute. November 2008. 
  9. ^ Boutell, Thomas; Randers-Pehrson, Glenn; et al. (14 July 1998). "PNG (Portable Network Graphics) Specification, Version 1.2". Retrieved 3 February 2011. 
  10. ^ a b c Koopman, Philip (23–26 June 2002). "32-Bit Cyclic Redundancy Codes for Internet Applications". 2002 International Conference on Dependable Systems and Networks: 459–468. doi:10.1109/DSN.2002.1028931. ISBN 0-7695-1597-5. Retrieved 14 January 2011. 
  11. ^ AIXM Primer. 4.5. European Organisation for the Safety of Air Navigation. 20 March 2006. Retrieved 29 April 2009. 
  12. ^ Gammel, B.M. (31 October 2005). "Crypto - Codes". Retrieved 10 February 2011. 
  13. ^ Geremia, Patrick (April 1999). Cyclic redundancy check computation: an implementation using the TMS320C54x (SPRA530). Texas Instruments. p. 5. Retrieved 10 February 2011. 
  14. ^ Jones, David T. An Improved 64-bit Cyclic Redundancy Check for Protein Sequences. University College London. Retrieved 15 December 2009.