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
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 et al., “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.