Cyclic redundancy check (CRC) code

Cyclic redundancy check (CRC) code[1–3]

Also known as Frame check sequence (FCS).

Description

A generalization of the single parity-check code in which the generalization of the parity bit is the remainder of the data string (mapped into a polynomial via the Cyclic-to-polynomial correspondence) divided by some generator polynomial. A notable family of codes is referred to as CRC-(\(m-1\)), where \(m\) is the length of the generator polynomial.

Protection

Detects any burst error up to the length of the generator polynomial.

Decoding

GRAND [4].

Realizations

CRC-16 and CRC-32 are used in data transmission, e.g., IEEE 802.16e, IEEE 802.3 [5] and TCP/IP communication [6; Sec. 2.3.3].

Notes

See Ref. [7] and book [8] for introductions to CRC codes.See Refs. [9,10] for exhaustive lists of CRC polynomials, as well as the CRC Polynomial Zoo website by Philip Koopman.

Parent

Cyclic linear binary code

Child

Single parity-check (SPC) code — A CRC using the divisor 11 is a single parity-check code [6; Sec. 2.3.3].

Cousin

Polar code — CRC codes concataned with polar codes yield improved performance of the SCL polar-code decoder [11–13].

References

[1]: W. Peterson and D. Brown, “Cyclic Codes for Error Detection”, Proceedings of the IRE 49, 228 (1961) DOI
[2]: W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
[3]: S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
[4]: W. An, M. Medard, and K. R. Duffy, “CRC Codes as Error Correction Codes”, ICC 2021 - IEEE International Conference on Communications (2021) arXiv:2104.13663 DOI
[5]: Borrelli, Chris. "IEEE 802.3 cyclic redundancy check." application note: Virtex Series and Virtex-II Family, XAPP209 (v1. 0) (2001).
[6]: M. Ergen, “Basics of Cellular Communication”, Mobile Broadband 19 (2008) DOI
[7]: S. Sheng-Ju, “Implementation of Cyclic Redundancy Check in Data Communication”, 2015 International Conference on Computational Intelligence and Communication Networks (CICN) (2015) DOI
[8]: Wells, Richard B. Applied coding and information theory for engineers. Prentice-Hall, Inc., 1998.
[9]: P. Koopman, “32-bit cyclic redundancy codes for Internet applications”, Proceedings International Conference on Dependable Systems and Networks DOI
[10]: P. Koopman and T. Chakravarty, “Cyclic redundancy code (CRC) polynomial selection for embedded networks”, International Conference on Dependable Systems and Networks, 2004 (2004) DOI
[11]: B. Li, H. Shen, and D. Tse, “An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check”, IEEE Communications Letters 16, 2044 (2012) DOI
[12]: I. Tal and A. Vardy, “List Decoding of Polar Codes”, IEEE Transactions on Information Theory 61, 2213 (2015) DOI
[13]: L. Xiang, Z. B. Kaykac Egilmez, R. G. Maunder, and L. Hanzo, “CRC-Aided Logarithmic Stack Decoding of Polar Codes for Ultra Reliable Low Latency Communication in 3GPP New Radio”, IEEE Access 7, 28559 (2019) DOI

Page edit log

Victor V. Albert (2024-02-25) — most recent
Gage Erwin (2023-08-11)

Cite as:

“Cyclic redundancy check (CRC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/crc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/easy/crc.yml.