Root code for the Classical Domain
Codes for communication over classical channels
Description
Code designed for transmission of classical information through classical channels in a robust way.
A code is a subset of a set or alphabet, with each element called a codeword. An error-correcting code consists of \(K\) codewords over an alphabet with \(N\) elements such that it is possible to recover the codewords from errors \(E\) from some error set \(\mathcal{E}\).
Rate
The Shannon channel capacity (the maximum of the mutual information over input and output distributions) is the highest rate of information transmission through a classical (i.e., non-quantum) channel with arbitrarily small error rate [1]. The fault-tolerant capacity is the capacity for the more general case where the encoding and decoding maps are also assumed to undergo noise [2].
Corrections to the capacity and tradeoff between decoding error, code rate and code length are determined using small [3–5], moderate [6–8] and large [9–12] deviation analysis. Sometimes the difference from the asymptotic rate at finite block length can be characterized by the channel dispersion [5,13].
Notes
See Ref. [14] for a list of open problems in coding theory.See Refs. [15,16] for reviews of coding theory.Classical systems such as RAM [17], HPC systems [18–20], and data centers [21] suffer from noise.Cousin
- Quantum error-correcting code (QECC)— Quantum information cannot be copied using a linear process [22], so one cannot send several copies of a quantum state through a channel as can be done for classical information. The Knill-Laflamme conditions can similarly be formulated for classical codes [23; Sec. 3], although they are not as widely as used as those for quantum codes.
Member of code lists
Primary Hierarchy
Parents
Any ECC can be embedded into a quantum Hilbert space, and thus passed through a quantum channel, by associating elements of the alphabet with basis vectors in a Hilbert space over the complex numbers. In other words, classical codewords are elements of an alphabet, while quantum codewords are functions on the alphabet. Classical codes can be unified with quantum codes using various algebraic frameworks [24,25].
Error-correcting code (ECC)
Children
Group-alphabet codeModulation scheme Polytope Polyhedron Lattice-shell Spherical design Lattice-based Array MDS array STC MRD MSRD Self-dual additive Linear \(q\)-ary Evaluation Self-dual linear QR Projective geometry Tanner \(q\)-ary LDPC Divisible Gray AG Editing GRM OA Perfect Nearly perfect Perfect binary Combinatorial design MDS GRS Balanced \(q\)-ary linear code over \(\mathbb{Z}_q\)
Block codeModulation scheme Polytope Polyhedron Lattice-shell Lattice-based STC Constant-weight FP Distributed-storage Array MDS array MRD MSRD LRC LCC LDC LTC Quantum-inspired classical block Small-distance block Skew-cyclic Constacyclic Cyclic \(t\)-design Spherical design Universally optimal Sharp configuration Convolutional Self-dual additive Linear \(q\)-ary Evaluation Self-dual linear QR Projective geometry Tanner \(q\)-ary LDPC Divisible Balanced OA MDS Combinatorial design Gray AG GRS Editing GRM Perfect Nearly perfect Perfect binary \(q\)-ary linear code over \(\mathbb{Z}_q\)
Finite-dimensional error-correcting code (ECC)Array MDS array STC MRD MSRD AG Editing OA Perfect Nearly perfect Perfect binary Combinatorial design Balanced \(q\)-ary linear code over \(\mathbb{Z}_q\) Linear \(q\)-ary MDS Gray Evaluation GRS GRM QR Projective geometry Tanner \(q\)-ary LDPC Divisible Self-dual additive Self-dual linear
Group-orbit codeLattice-based Linear \(q\)-ary Gray Evaluation MDS GRS GRM Projective geometry Tanner \(q\)-ary LDPC Divisible Self-dual additive Self-dual linear \(q\)-ary linear code over \(\mathbb{Z}_q\) Cyclic QR Polytope Polyhedron
Not all codes are group-orbit codes, and more generally one can classify codewords into orbits of the automorphism group [26].
References
- [1]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
- [2]
- M. Christandl and A. Müller-Hermes, “Fault-Tolerant Coding for Quantum Communication”, IEEE Transactions on Information Theory 70, 282 (2024) arXiv:2009.07161 DOI
- [3]
- V. Strassen, “Asymptotische Absch¨atzungen in Shannons Informationstheorie,” Trans. Third Prague Conference on Information Theory, Prague, 689–723, (1962)
- [4]
- M. Hayashi, “Information Spectrum Approach to Second-Order Coding Rate in Channel Coding”, IEEE Transactions on Information Theory 55, 4947 (2009) arXiv:0801.2242 DOI
- [5]
- Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel Coding Rate in the Finite Blocklength Regime”, IEEE Transactions on Information Theory 56, 2307 (2010) DOI
- [6]
- Y. Altug and A. B. Wagner, “Moderate Deviations in Channel Coding”, (2012) arXiv:1208.1924
- [7]
- Y. Polyanskiy and S. Verdu, “Channel dispersion and moderate deviations limits for memoryless channels”, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) 1334 (2010) DOI
- [8]
- C. T. Chubb, V. Y. F. Tan, and M. Tomamichel, “Moderate Deviation Analysis for Classical Communication over Quantum Channels”, Communications in Mathematical Physics 355, 1283 (2017) arXiv:1701.03114 DOI
- [9]
- R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [10]
- I. Csiszár and J. Körner, Information Theory (Cambridge University Press, 2011) DOI
- [11]
- S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels (Corresp.)”, IEEE Transactions on Information Theory 19, 357 (1973) DOI
- [12]
- G. Dueck and J. Korner, “Reliability function of a discrete memoryless channel at rates above capacity (Corresp.)”, IEEE Transactions on Information Theory 25, 82 (1979) DOI
- [13]
- S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-Length Scaling for Polar Codes”, IEEE Transactions on Information Theory 60, 5875 (2014) DOI
- [14]
- S. Dougherty, J.-L. Kim, and P. Solé, “Open Problems in Coding Theory”, Noncommutative Rings and Their Applications 79 (2015) DOI
- [15]
- A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI
- [16]
- D. J. Costello Jr. and G. D. Forney Jr, “Channel Coding: The Road to Channel Capacity”, (2006) arXiv:cs/0611112
- [17]
- B. Schroeder, E. Pinheiro, and W.-D. Weber, “DRAM errors in the wild”, Communications of the ACM 54, 100 (2011) DOI
- [18]
- S. Levy, K. B. Ferreira, N. DeBardeleben, T. Siddiqua, V. Sridharan, and E. Baseman, “Lessons Learned from Memory Errors Observed Over the Lifetime of Cielo”, SC18: International Conference for High Performance Computing, Networking, Storage and Analysis (2018) DOI
- [19]
- K. B. Ferreira, S. Levy, J. Hemmert, and K. Pedretti, “Understanding Memory Failures on a Petascale Arm System”, Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing (2022) DOI
- [20]
- C. Di Martino, Z. Kalbarczyk, R. K. Iyer, F. Baccanico, J. Fullop, and W. Kramer, “Lessons Learned from the Analysis of System Failures at Petascale: The Case of Blue Waters”, 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (2014) DOI
- [21]
- J. Meza, Q. Wu, S. Kumar, and O. Mutlu, “Revisiting Memory Errors in Large-Scale Production Data Centers: Analysis and Modeling of New Trends from the Field”, 2015 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (2015) DOI
- [22]
- W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned”, Nature 299, 802 (1982) DOI
- [23]
- B. Yoshida, “Decoding the Entanglement Structure of Monitored Quantum Circuits”, (2021) arXiv:2109.08691
- [24]
- M. K. Patra and S. L. Braunstein, “An algebraic framework for information theory: Classical Information”, (2009) arXiv:0910.1536
- [25]
- G. Kuperberg and N. Weaver, “A von Neumann algebra approach to quantum metrics”, (2010) arXiv:1005.0353
- [26]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
Page edit log
- Victor V. Albert (2022-11-06) — most recent
Cite as:
“Error-correcting code (ECC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ecc
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/ecc.yml.