{ "id": "epqsjk3ac4", "slug": "cyclic-code", "title": "Cyclic code", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" } ], "geo": [ { "id": "geo.nongeo.t1800.technology.computing", "label": "Non-geographic · 1800 to 1945: Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1800", "label": "Non-geographic · 1800 to 1945", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800" }, { "id": "geo.nongeo.t1800.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology" }, { "id": "geo.nongeo.t1800.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing" } ] }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] } ], "excerpt": "A cyclic code is an error-correcting code in which every cyclic shift of a codeword is also a codeword, a property that makes encoding and decoding efficient.", "snippet": "A cyclic code is an error-correcting code in which every cyclic shift of a codeword is also a codeword, a property that makes encoding and decoding efficient.", "node": "technology.computing.ai.algorithms", "markdown": "# Cyclic code\n\nA cyclic code is a linear error-correcting code in which every cyclic shift of a codeword is again a codeword: if \\( (c_0, c_1, \\ldots, c_{n-1}) \\) is in the code, then so is \\( (c_{n-1}, c_0, c_1, \\ldots, c_{n-2}) \\).[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) This single closure property ties the code to polynomial arithmetic modulo \\( x^n - 1 \\), which is what makes its encoding and decoding unusually efficient in both algorithms and hardware.[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) Cyclic codes are particularly efficient for error detection, and many of the most widely deployed families, including BCH, Reed–Solomon, and CRC codes, are cyclic.[2](https://personal.oss.unist.hr/~mnizetic/ZASTITNO%20LINIJSKO%20KODIRANJE/SEMINARSKI%20RADOVI/CH05.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Defining property | Any cyclic shift of a codeword is also a codeword[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) |\n| Algebraic form | A linear cyclic code of length \\( n \\) over \\( \\mathbb{F}_q \\) is an ideal in \\( \\mathbb{F}_q[x]/\\langle x^n - 1 \\rangle \\)[3](https://arxiv.org/html/2410.12167) |\n| Generator polynomial | The unique monic polynomial \\( g(x) \\) of least degree in the code, which divides \\( x^n - 1 \\), with parity-check polynomial \\( h(x) = (x^n - 1)/g(x) \\)[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499) |\n| Systematic encoding | Parity \\( p(x) = -x^{n-k} m(x) \\bmod g(x) \\), computed by a shift-register circuit[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) |\n| BCH bound | \\( \\delta - 1 \\) consecutive integers in the defining set imply minimum distance \\( d \\ge \\delta \\)[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499) |\n| Quality of BCH codes | Among all binary cyclic codes of odd length \\( n \\le 125 \\), the best cyclic code is a BCH code except for two special cases[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499) |\n| Landmark application | Reed–Solomon codes were implemented in the Voyager space program in 1977 and first used commercially in mass-consumer products in 1982[5](https://www.fi.muni.cz/usr/gruska/crypto16/crypto1603_handout.pdf) |\n\n## How it works\n\nIdentify a word \\( (c_0, c_1, \\ldots, c_{n-1}) \\) with the polynomial \\( c(x) = c_0 + c_1 \\cdot x + \\cdots + c_{n-1} \\cdot x^{n-1} \\). A cyclic shift by one position then corresponds to multiplication by \\( x \\) modulo \\( x^n - 1 \\), so a linear code is cyclic exactly when its codeword polynomials form an ideal in the residue class ring \\( \\mathbb{F}_q[x]/(x^n - 1) \\).[6](https://pages.jh.edu/bcooper8/sigma_files/ERROR_CONTROL_CODING/04cyc.pdf) Because this quotient ring is a principal ideal ring, every cyclic code is generated by a single polynomial.[3](https://arxiv.org/html/2410.12167)\n\nThat generator is the unique monic polynomial of least degree in the code; it divides \\( x^n - 1 \\), and the parity-check polynomial is \\( h(x) = (x^n - 1)/g(x) \\).[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499) For an \\( (n, k) \\) binary cyclic code, \\( \\deg g(x) = n - k \\).[7](https://dept.ee.wits.ac.za/~cheng/ELEN3015/Files/cyclic_FEC.pdf) A complete classification of the cyclic codes of a given length follows from factoring \\( x^n - 1 \\) over \\( \\mathbb{F}_q \\), since each monic divisor of \\( x^n - 1 \\), built from the irreducible factors, generates the ideal of a cyclic code.[8](https://www.irishmathsoc.org/bull95/wef/Articles/Coding_History/Coding_History-wef.pdf)\n\nThe roots of \\( g(x) \\) control the minimum distance. If the defining set contains \\( \\delta - 1 \\) consecutive integers, then \\( d \\ge \\delta \\); this is the BCH bound.[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499)\n\n## How it is done\n\n**Systematic encoding** places the message in the high-order positions and appends parity. For a message polynomial \\( m(x) \\) of degree below \\( k \\), compute the remainder \\( p(x) = -x^{n-k} m(x) \\bmod g(x) \\); then \\( c(x) = p(x) + x^{n-k} m(x) \\) is a codeword, because it is divisible by \\( g(x) \\).[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) The remainder follows from polynomial division, \\( x^r m(x) = q(x) g(x) + s(x) \\) with \\( \\deg s(x) < \\deg g(x) = r \\), and the codeword is \\( x^r m(x) - s(x) \\).[9](https://users.math.msu.edu/users/halljo/classes/codenotes/Cyclic.pdf) In non-systematic form one simply sends \\( c(x) = m(x) g(x) \\).[10](https://www.ece.uvic.ca/~agullive/cycliccodes405-511-2016.pdf)\n\n**Hardware.** [Polynomial](https://www.edgepedia.org/polynomial) division is performed by a linear feedback shift register (LFSR) with feedback connections matched to the coefficients of \\( g(x) \\); after the input has been shifted through, the register holds the remainder.[10](https://www.ece.uvic.ca/~agullive/cycliccodes405-511-2016.pdf) An \\( (n-k) \\)-stage shift register with feedback accomplishes the multiplication by \\( x^{n-k} \\) and the division by \\( g(x) \\) simultaneously, producing the parity coefficients after \\( k \\) shifts.[11](http://charleslee.yolasite.com/resources/elec321/lect_cyc_enc_dec.pdf) Low-weight generator polynomials simplify this circuitry, which is one reason shortened cyclic Hamming-code subcodes serve as CRC codes.[9](https://users.math.msu.edu/users/halljo/classes/codenotes/Cyclic.pdf)\n\n**Decoding** proceeds in three steps: syndrome computation, error pattern detection, and error correction. The syndrome polynomial is \\( s(x) = r(x) \\bmod g(x) \\), and for each distinct syndrome one error pattern is selected for correction.[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) The Meggitt decoder exploits cyclicity to test the syndrome only for error patterns with an error in the highest-order position \\( x^{n-1} \\), so the same detection circuitry decodes each received digit serially; in principle it can decode any cyclic code, but its implementation complexity is very high for multiple-error correction, and error-trapping decoding is a practical variation.\n\n## Origin\n\nThe algebraic setting of cyclic codes grew out of early error-control work: R. W. Hamming's paper \"Error Detecting and Error Correcting Codes\" (Bell System Technical Journal, 1950) introduced the Hamming codes that later cyclic constructions generalize.[12](https://doi.org/10.1002/j.1538-7305.1950.tb00463.x) The wider shift toward near-capacity coding came later, when Claude Berrou, Alain Glavieux, and Punya Thitimajshima proposed [turbo codes](https://www.edgepedia.org/turbo-code) in 1993 in 'Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes', presented at the IEEE International Conference on Communications (ICC '93) in Geneva, shortly before the rediscovery of LDPC codes.[13](https://www.jstage.jst.go.jp/article/transcom/E105.B/8/E105.B_2021EBI0001/_pdf/-char/ja)\n\n## Variants\n\n**BCH codes** are the cyclic codes whose generator polynomial is the least common multiple of the minimal polynomials \\( m_{\\alpha^{j+b}, K}(x) \\) for \\( 1 \\le j \\le t \\); they have designed distance \\( t + 1 \\), minimum distance at least \\( t + 1 \\), and dimension at least \\( n - mt \\), where \\( m = \\dim_K \\mathbb{F} \\).[9](https://users.math.msu.edu/users/halljo/classes/codenotes/Cyclic.pdf) They are in many cases the best linear codes: among binary cyclic codes of odd length \\( n \\le 125 \\), the best is always a [BCH code](https://www.edgepedia.org/bch-code) except in two special cases.[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499)\n\n**Binary Hamming codes** form a cyclic family with \\( n = 2^r - 1 \\) and \\( k = n - r \\) that corrects all single errors.[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) **Reed–Solomon codes** are non-binary BCH codes, widely used in communication devices and consumer electronics.[4](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499) **CRC codes** compute check bits as \\( p(x) = x^r m(x) \\bmod g(x) \\) for a generator \\( g(x) \\) of degree \\( r \\), appending the remainder so that the resulting word is divisible by \\( g(x) \\), without constraining the message length; the CRCs defined in standards often have subtle variations.[1](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf) Other named cyclic families include [Euclidean geometry](https://www.edgepedia.org/euclidean-geometry) codes, projective geometry codes, quadratic residue codes, and Fire codes.[2](https://personal.oss.unist.hr/~mnizetic/ZASTITNO%20LINIJSKO%20KODIRANJE/SEMINARSKI%20RADOVI/CH05.pdf)\n\n**Quasi-cyclic codes** relax the shift: a quasi-cyclic code of index \\( \\ell \\) is a linear code closed under a cyclic shift by \\( \\ell \\) positions.[3](https://arxiv.org/html/2410.12167) QC-LDPC codes take this further: their parity-check matrices are arrays of circulants, isomorphic to polynomials over \\( \\mathbb{F}_2 \\) modulo \\( x^N - 1 \\), which enables efficient encoding and belief-propagation decoding.[14](https://arxiv.org/pdf/2508.07030) Cyclic structure also reaches quantum coding: additive cyclic codes over \\( \\mathbb{F}_{p^2} \\) are uniquely presented by at most two generator polynomials, a representation that yielded ten record-breaking binary quantum codes,[15](https://www.aimsciences.org/article/doi/10.3934/amc.2023036) and non-binary quantum codes have likewise been constructed from one-generator quasi-cyclic codes, identifying codewords with polynomials in \\( \\mathbb{F}_q[x]/\\langle x^n - 1 \\rangle \\).[16](https://ar5iv.labs.arxiv.org/html/2412.13613)\n\n## Applications\n\nError detection with a binary cyclic code divides the received polynomial \\( y(x) \\) by \\( g(x) \\): the remainder is zero if and only if \\( y \\) is a codeword, and the long division is implemented directly in circuitry. This is how error detection is carried out in practice in Ethernet networks.[17](https://personalpages.manchester.ac.uk/staff/yuri.bazlov/code/notes/ch9.pdf) Cyclic codes are especially useful where errors occur in bursts.[5](https://www.fi.muni.cz/usr/gruska/crypto16/crypto1603_handout.pdf) Reed–Solomon codes were implemented in the Voyager space program in 1977, and their first commercial use in mass-consumer products came in 1982.[5](https://www.fi.muni.cz/usr/gruska/crypto16/crypto1603_handout.pdf) Shortened cyclic Hamming-code subcodes remain the basis of CRC codes in networking.[9](https://users.math.msu.edu/users/halljo/classes/codenotes/Cyclic.pdf)\n\n## Limitations and alternatives\n\nThe Meggitt decoder's serial, pattern-matching approach carries very high implementation complexity when multiple errors must be corrected, which limits its use for strong codes. For capacity-approaching performance, the modern alternatives operate differently: turbo codes, proposed in 1993,[13](https://www.jstage.jst.go.jp/article/transcom/E105.B/8/E105.B_2021EBI0001/_pdf/-char/ja) and LDPC codes use iterative decoding at block lengths \\( n = 10^3 \\) to \\( 10^4 \\), and the original turbo codes remain among the best known.[18](https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1a3ad00d83d1d042da3328a8edd9edc2_chap13.pdf) [Polar codes](https://www.edgepedia.org/polar-codes) achieve capacity through channel polarization, but their finite-length performance was initially not competitive because successive-cancellation decoding is suboptimal and their minimum distance is relatively weak, and the sequential SC decoder's latency grows at least linearly with code length, creating a throughput bottleneck.[19](https://ar5iv.labs.arxiv.org/html/1504.03916) In wireless-system design, quasi-cyclic block LDPC codes and duo-binary turbo codes emerged as leading candidates, with implementation aspects such as parallelization and fixed-point behavior often neglected in code design.[20](https://www.vodafone-chair.org/pbls/legacy/e-zimmermann/Block-LDPC_Codes_vs_Duo-Binary_Turbo-Codes_for_European_Next_Generation_Wireless_Systems.pdf) Recent work on QC-LDPC codes addresses design practicalities directly, for example computing the dimension of any QC-LDPC code from minors of its polynomial parity-check matrix instead of \\( O(n^3) \\) [Gaussian elimination](https://www.edgepedia.org/gaussian-elimination).[14](https://arxiv.org/pdf/2508.07030)\n\n## References\n\n1. [Cyclic Codes (ECE 590 Error Correction Coding course notes, Duke University, Pfister)](https://pfister.ee.duke.edu/courses/ece590_ecc/cyclic.pdf)\n2. [Cyclic codes (textbook chapter, ch. 5)](https://personal.oss.unist.hr/~mnizetic/ZASTITNO%20LINIJSKO%20KODIRANJE/SEMINARSKI%20RADOVI/CH05.pdf)\n3. [Elementary Constructions of Best Known Quantum Codes (arXiv, 2024)](https://arxiv.org/html/2410.12167)\n4. [BCH cyclic codes (C. Ding and C. Li, Discrete Mathematics 347 (2024) 113918)](https://www.sciencedirect.com/science/article/abs/pii/S0012365X24000499)\n5. [Coding, Cryptography and Cryptographic Protocols (Masaryk University handout)](https://www.fi.muni.cz/usr/gruska/crypto16/crypto1603_handout.pdf)\n6. [4.0 Cyclic Codes (Johns Hopkins course notes)](https://pages.jh.edu/bcooper8/sigma_files/ERROR_CONTROL_CODING/04cyc.pdf)\n7. [Cyclic Codes (ELEN3015 notes, University of the Witwatersrand)](https://dept.ee.wits.ac.za/~cheng/ELEN3015/Files/cyclic_FEC.pdf)\n8. [Coding Theory: The story of how an engineering problem evolved into a branch of pure mathematics](https://www.irishmathsoc.org/bull95/wef/Articles/Coding_History/Coding_History-wef.pdf)\n9. [Cyclic Codes (Chapter 8, Coding Theory Notes, Michigan State University, J. Hall)](https://users.math.msu.edu/users/halljo/classes/codenotes/Cyclic.pdf)\n10. [ELEC405 Error Control Coding: Cyclic codes (University of Victoria)](https://www.ece.uvic.ca/~agullive/cycliccodes405-511-2016.pdf)\n11. [Encoding and Syndrome Decoding of Cyclic Codes (ELEC 321 lecture notes, Charles Lee)](http://charleslee.yolasite.com/resources/elec321/lect_cyc_enc_dec.pdf)\n12. [R. W. Hamming (1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal.](https://doi.org/10.1002/j.1538-7305.1950.tb00463.x)\n13. [LDPC Codes for Communication Systems: Coding Theoretic Perspective (IEICE Trans. Commun.)](https://www.jstage.jst.go.jp/article/transcom/E105.B/8/E105.B_2021EBI0001/_pdf/-char/ja)\n14. [Generalized Quasi-Cyclic LDPC Codes: Design and Efficient Encoding (arXiv, 2025)](https://arxiv.org/pdf/2508.07030)\n15. [Polynomial representation of additive cyclic codes and new quantum codes (Advances in Mathematics of Communication)](https://www.aimsciences.org/article/doi/10.3934/amc.2023036)\n16. [Some New Non-binary Quantum Codes from One-generator Quasi-cyclic Codes (arXiv, Dec 2024)](https://ar5iv.labs.arxiv.org/html/2412.13613)\n17. [Cyclic codes (lecture notes, University of Manchester)](https://personalpages.manchester.ac.uk/staff/yuri.bazlov/code/notes/ch9.pdf)\n18. [Capacity-approaching codes (MIT OCW 6.451, Ch. 13)](https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1a3ad00d83d1d042da3328a8edd9edc2_chap13.pdf)\n19. [Challenges and some new directions in channel coding (arXiv survey)](https://ar5iv.labs.arxiv.org/html/1504.03916)\n20. [Block-LDPC Codes vs Duo-Binary Turbo-Codes for European Next Generation Wireless Systems](https://www.vodafone-chair.org/pbls/legacy/e-zimmermann/Block-LDPC_Codes_vs_Duo-Binary_Turbo-Codes_for_European_Next_Generation_Wireless_Systems.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/cyclic-code", "markdown_url": "https://www.edgepedia.org/cyclic-code.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Cyclic code\", Edgepedia (EdgeChat), https://www.edgepedia.org/cyclic-code. Edgepedia Community License 1.0.", "credit_md": "\"[Cyclic code](https://www.edgepedia.org/cyclic-code)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/cyclic-code](https://www.edgepedia.org/cyclic-code). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Cyclic code\", Edgepedia (EdgeChat), https://www.edgepedia.org/cyclic-code. Edgepedia Community License 1.0.", "speakable": "A cyclic code is an error-correcting code in which every cyclic shift of a codeword is also a codeword, a property that makes encoding and decoding efficient." }