Here is a list of all classical codes that specify what rate they have.

[Jump to code graph excerpt]

Name Rate
Alamouti code The only complex OSTBC with full rate, i.e., one complex information symbol per channel use [1,2].
Algebraic-geometry (AG) code Several sequences of linear AG codes beat the GV bound and/or are asymptotically good [3–5][6; Thm. 15.4.3] (see Ref. [7] for details). For square \(q\), there exist sequences of linear AG codes whose asymptotic rate and relative distance satisfy \begin{align} \frac{k}{n} \geq 1 - \frac{d}{n} - \frac{1}{\sqrt{q}-1}~, \tag*{$(1)$}\end{align}which follows from the Drinfeld-Vladut bound [8]. Nonlinear AG codes can outperform this bound [6; Thm. 15.4.6].
Barg-Tamo-Vladut code Barg-Tamo-Vladut codes on asymptotically maximal curves improve upon the asymptotic LRC GV bound [9].
Berman code Achieve capacity of the BEC and BMS channels [10].
Binary BCH code Primitive BCH codes are asymptotically bad [11; Thm. 2.6.3].
Binary PSK (BPSK) modulation format Achieves capacity of AWGN in the low signal-to-noise regime [12] (see also [13]). BPSK concatenated with classical-quantum polar codes approaches the Holevo capacity of the pure-loss optical channel in the low-photon-number regime [14].
Binary code The rate of a binary code is usually defined as \(R=\frac{1}{n}\log_{2}K\) bits per symbol. The maximum rate of a binary code with linear distance is upper bounded by the McEliece, Rodemich, Rumsey and Welch (MRRW) bound [15] (see Refs. [16–21] for other proofs). Two-point linear-programming bounds strictly improve the MRRW bound for every relative distance \(0<\delta<1/2\) [22; Ch. 2, Thm. 1.1]. Rate bounds derived from classical-quantum channels and the pretty good measurement also strictly improve the MRRW bound [23]. The two approaches yield the same improvement of the first MRRW bound [24].
Block code Ideal decoding error is suppressed exponentially with the number of subsystems \(n\), and the exponent has been studied in Ref. [25–27].
Bose–Chaudhuri–Hocquenghem (BCH) code Primitive BCH codes are asymptotically bad [11; Thm. 2.6.3][28; pg. 269].
Cartier code Cartier codes share similar asymptotic properties to subfield subcodes of residue AG codes, with both families admitting sequences of codes that achieve the GV bound.
Code in permutations Asymptotically good codes in the Ulam metric exist [29].
Concatenated code There exist bounds on distance and rate of concatenated codes with a fixed outer and random inner code [30,31].
Constantin-Rao (CR) code CR codes for particular groups have higher rates than distance-one codes under the binary asymmetric channel for all lengths except \(n = 2^r - 1\), in which case CR codes reduce to Hamming codes [32]; see Ref. [33]. Size analysis is presented in Refs. [34,35].
Convolutional code Depends on the polynomials used. Using puncturing [36], the rate for the code can be increased from \(\frac{1}{t}\) to \(\frac{s}{t}\), where \(t\) is the number of output bits, and \(s\) depends on the puncturing done. This is done by deleting some pieces of the encoder output such that maximum-likelihood decoders remain effective.
Cycle LDPC code Cycle codes are not asymptotically good [37].
Editing code An asymptotically good linear code against bit-flip errors can be converted into an asymptotically good code against insertion-deletion errors [38].
Error-correcting code (ECC)

The Shannon channel capacity (the maximum of the mutual information over input distributions) is the highest rate of information transmission through a classical (i.e., non-quantum) channel with arbitrarily small error rate [39]. The fault-tolerant capacity is the capacity for the more general case where the encoding and decoding maps are also assumed to undergo noise [40].

Corrections to the capacity and tradeoff between decoding error, code rate and code length are determined using small [41–43], moderate [44–46] and large [47–50] deviation analysis. Sometimes the difference from the asymptotic rate at finite block length can be characterized by the channel dispersion [43,51]. Doeblin coefficients [52] for classical channels have been studied [53].
Expander code The rate is at least \(1 - m/n\), where \(n\) is the number of left nodes and \(m\) is the number of right nodes in the bipartite expander graph. Expander codes yield an explicit (i.e., non-random) asymptotically good LDPC code family [54].
Folded RS (FRS) code FRS codes achieve relaxed generalized Singleton bounds [55].
Fountain code Random linear fountain codes approach the Shannon limit as the file size \(K\) increases. However, they do not have a fixed encoding rate.
Frameproof (FP) code FP codes tend to have large minimum distance and low rate [56]. Specifically, for any positive integers \(n\) and \(c\), if \(l = 16c^{2}\log n\), then there exists a \(c\)-FP \( (l,n) \)-code which has rate \((\log n)/l\) [56]. See Ref. [57] for other bounds on FP codes.
Gallager (GL) code GL codes nearly achieve Shannon capacity against binary-input additive Gaussian white noise using iterative decoding [58,59]. GL codes can outperform RS codes at short block length [60].
Generalized RM (GRM) code Affine GRM codes achieve capacity on sufficiently symmetric non-binary channels [61].
Generalized RS (GRS) code Concatenations of GRS codes with random linear codes almost surely attains the GV bound [62].
Goethals code The rate is \({2^m -3m +1}/2^m\), going to 1 as block length goes to infinity.
Hermitian code For the standard one-point code \(C_L(D,mP_\infty)\) with genus \(g=q(q-1)/2\), Riemann-Roch gives \begin{align} k=m-g+1\tag*{$(2)$} \end{align}whenever \(2g-2 < m < n=q^3\).
Hsu-Anastasopoulos LDPC (HA-LDPC) code HA-LDPC codes achieve capacity on the BEC channel under BP decoding [63] and the memoryless binary-input output-symmetric (MBIOS) channels under ML decoding [63] and under MAP decoding [64]. Bounded-density spatially coupled HA-LDPC codes have BEC BP thresholds close to the Shannon limit [64]. For \(l\geq 4\), \((l,r,r)\)-HA-LDPC codes attain the GV bound with high probability for all sufficiently large \(r\) [63; Thm. 1 and Cor. 2]. At fixed degree, \((l,r,r)\)-HA-LDPC codes sampled from the configuration-model ensemble attain the GV bound with high probability for the 56 pairs with even \(r\leq 30\), \(4\leq l\leq 10\), and \(l<r/2\) [65; Thm. 3.2]. The same holds for \((j,2j,2j)\)-HA-LDPC codes with \(4\leq j\leq 15\) [65; Prop. 6.1].
Identifiable parent property (IPP) code A hypergraph approach can be used to show that, for any \(t \leq q\), there exists a sequence of IPP codes with asymptotically non-vanishing rate [66].
Irregular LDPC code Nearly achieve capacity against binary-input additive Gaussian white noise using iterative decoding [67,68]. Such sequences have sublinearly growing distance per block length [69].
Irregular repeat-accumulate (IRA) code IRA codes nearly achieve the Shannon capacity of the binary erasure channel using iterative decoding [70]. Puncturing lessens the decoding complexity while still allowing sequences of codes to achieve capacity [71].
Justesen code

The first asymptotically good codes. Rate is \(R_m=k/n=K/2N\geq R\) and the relative minimum distance satisfies \(\delta_m=d_m/n\geq 0.11(1-2R)\), where \(K=\left\lceil 2NR\right\rceil\) for asymptotic rate \(0<R<1/2\); see [28; pg. 311].

The code can be improved and the range of \(R\) extended from 0 to 1 by puncturing, i.e., by erasing \(s\) digits from each inner codeword. This yields a code of length \(n=(2m-s)N\) and rate \(R=mk/(2m-s)N\). The lower bound on the relative distance of the punctured code approaches \(d_m/n=(1-R/r)H^{-1}(1-r)\) as \(m\) goes to infinity, where \(r\) is the maximum of 1/2 and the solution to \(R=r^2/( 1+\log( 1-h^{-1}(1-r) ) )\), and \(h\) is the binary entropy function.
Kerdock code The transmission rate is \(2m/2^m\) which tends to 0 as \(m\) becomes large, hence these codes are asymptotically poor.
Laplacian code Generic sparse-graph Laplacian-code families have vanishing rate with only \(O(1)\) logical bits, whereas more symmetric families can exhibit enhanced rank deficiency [72].
Lattice Lattices with minimal-distance decoding achieve the capacity of the AWGN channel [73–76].
Linear \(q\)-ary code Any code admitting a two-transitive automorphism group achieves capacity under the binary erasure channel [77–79].
Linear binary code

A family of linear codes \(C_i = [n_i,k_i,d_i]\) is asymptotically good if the asymptotic rate \(\lim_{i\to\infty} k_i/n_i\) and asymptotic distance \(\lim_{i\to\infty} d_i/n_i\) are both positive. Nearly all good linear binary codes for the asymmetric channel are also good for the symmetric channel [80]; this is not the case for non-binary codes [33].

Binary linear codes on \(D\)-dimensional Euclidean lattices are limited by the classical Bravyi-Poulin-Terhal (BPT) bound [81,82], which states that \(d = O(n^{1-1/D})\) and that \(k d^{1/D} = O(n)\) (using asymptotic notation). This bound is the classical analogue of the BPT bound for qubit stabilizer codes and the subsystem BT bound for subsystem qubit stabilizer codes.
Linear code over \(G\) Linear codes over non-Abelian \(G\) cannot have better parameters than those for Abelian groups [83] and are asymptotically bad [84,85].
Linear code with complementary dual (LCD) Asymptotically good LCD codes exist [86].
Locally decodable code (LDC) Families of LDCs with query complexity \(r=2\) need \(n\) to scale exponentially with \(k\) [87,88]. This was first shown for linear LDCs [89]. A binary 2-query LDC with recovery probability at least \(1/2+\epsilon\) at corruption rate \(\delta\) satisfies \(n \geq 2^{ck-1}\) with \(c = 1-H(1/2+3\delta\epsilon/14)\) [87; Thm. 4]. Here, \(H\) is the binary entropy function. Weaker exponential lower bounds hold for adaptive queries and for alphabets of fixed size [87; Sec. 3.3 and Appx. B]. LDCs with \(r=1\) do not exist for \(k\) above a constant depending on \(\delta\) and \(\epsilon\) [90].
Locally recoverable code (LRC) The rate of an \((n,k,r)\) LRC satisfies \begin{align} \frac{k}{n}\leq\frac{r}{r+1}~.\tag*{$(3)$} \end{align}Various asymptotic lower [9,91] and upper bounds [92] exist.
Low-density generator-matrix (LDGM) code Certain LDGM codes come close to achieving Shannon capacity [93].
Low-density parity-check (LDPC) code Some LDPC codes achieve the Shannon capacity of the binary symmetric channel under maximum-likelihood decoding [59,94,95]. Other LDPC codes achieve capacity for smaller block lengths under belief-propagation decoding [96]. Random LDPC codes achieve list-decoding capacity [97].
MacKay-Neal LDPC (MN-LDPC) code Certain sequences of optimally decoded codes can nearly achieve the Shannon capacity [59,98]. MN-LDPC codes with bounded degrees were conjectured to achieve the capacity of memoryless binary-input symmetric-output channels under MAP decoding [64]. This was proven for \((l,3,3)\)-MN-LDPC codes with \(l \geq 4\) [99; Thm. 1]. On any such channel with capacity above the rate \(3/l\), their ensemble-average MAP block error probability is of order \(O(\log N/N)\) in the block length \(N\) [99; Thm. 1]. Standard MN-LDPC codes have no BP threshold, while bounded-density spatially coupled MN-LDPC codes have BEC BP thresholds close to the Shannon limit [64]. At rate \(1/2\), \((2j,j,2j)\)-MN-LDPC codes sampled from the configuration-model ensemble attain the GV bound with high probability at fixed degree for every \(4\leq j\leq 15\) [65; Prop. 6.1]. \((k,k-j_Z,k)\)-MN-LDPC codes whose \(H_1^{T}\) stacks two independent regular matrices also attain the GV bound with high probability at fixed degree for the 56 pairs with even \(k\leq 30\), \(4\leq j_Z\leq 10\), and \(j_Z<k/2\) [65; Thm. 4.2].
Multiplicity code Multiplicity codes achieve relaxed generalized Singleton bounds [55].
Nonlinear AG code Certain nonlinear code sequences beat the Tsfasman-Vladut-Zink bound, outperforming linear AG codes [6; Thm. 15.4.6].
Orthogonal Spacetime Block Code (OSTBC) The greatest rate which can be achieved is \(\frac{n_0+1}{2n_0}\), where either \(n=2n_0\) or \(n=2n_0-1\) for the orthogonal case [2].
Permutation spherical code Number of codewords cannot increase exponentially with dimension \(n\) [100]
Phase-shift keying (PSK) modulation format As the constellation size \(q\) grows, \(q\)-PSK approaches the Shannon AWGN capacity of the corresponding two-dimensional signal set [101; Fig. 11.7].
Pinwheel code The encoding rate vanishes asymptotically because \(k\sim\sqrt{n}\) while the block length grows with the substitution generation [72].
Polar code Supports reliable transmission at rates \(K/N\) approaching the Shannon capacity of the channel under the successive cancellation decoder [102,103]; see also Refs. [104,105].
Preparata code The rate is \(\frac{2^{m+1}-2m-2}{2^{m+1}}\), tending to 1 as \(m\) becomes large.
Quadratic-residue (QR) code Achieve capacity of the binary erasure channel; see Ref. [79].
Quadrature-amplitude modulation (QAM) format High-order QAM, especially with appropriate shaping and coding, can operate close to Shannon AWGN capacity at high signal-to-noise ratio [101; Fig. 11.8].
Random code Typical random codes (TRC) or typical random linear codes (TLC) refer to codes in the respective ensemble that satisfy a certain minimum-distance property. The relative fraction of typical codes in the ensemble approaches one as \(n\) goes to infinity [39] (see also Ref. [106]). Asymptotically, given relative distance \(\delta=d/n\), the maximum rate for a TRC is \(R=\frac{1}{2}R_{GV}(\delta)\), where \(R_{GV}(\delta)=1-h(\delta)\) is the Gilbert-Varshamov (GV) bound and \(h(\delta)\) is the binary entropy function. The maximum rate for a TLC is \(R=R_{GV}(\delta)\), meaning that TLCs achieve the asymptotic GV bound.
Rank-modulation code Rank modulation codes with code distance of order \(d=\Theta(n^{1+\epsilon})\) for \(\epsilon\in[0,1]\) achieve a rate of \(1-\epsilon\) [107].
Reed-Muller (RM) code Achieves capacity of the binary erasure channel [77,78], the binary memoryless symmetric (BMS) channel under bitwise maximum-a-posteriori decoding [108] (see also Ref. [109]), and the binary symmetric channel (BSC), solving a long-standing conjecture [110].
Regular LDPC code An ensemble of \((j,k)\)-regular LDPC codes has a design rate \(1 - j/k\). This is a lower bound on the true rate, is the true rate if all constraints are linearly independent, and equals the rate asymptotically [111][112; Sec. 3.4].
Regular binary Tanner code For a short code \(C_0\) with rate \(R_0\), the Tanner code has rate \(R \geq 2R_0-1\). If \(C_0\) satisfies the GV bound, i.e., \(R_0 \geq 1-h(\delta_0)\), then \(R \geq 1-2h(\delta_0)\), where \(\delta_0\) is the relative distance of \(C_0\) and \(h\) is the binary entropy function.
Repeat-accumulate (RA) code RA codes are not asymptotically good [113].
Repeat-accumulate-accumulate (RAA) code Some sequences of non-deterministic RAA codes are asymptotically good [113,114].
Repetition code Code rate is \(\frac{1}{n}\), code distance is \(n\).
Simplex integer-based code For \(\alpha>0\), \(\epsilon>0\), and sufficiently small \(\delta>0\), there exist positive-rate codes in \(\Delta_{\alpha N,N}\) with \(\ell_1\) distance at least \(2\lfloor\delta N\rfloor\) and all coordinates below \((1+\epsilon)\log_{1+\alpha}N\) [115; Prop. 15]. Codes of sufficiently small positive rate whose codewords are drawn independently and uniformly from \(\Delta_{\alpha N,N}\) have \(\ell_1\) distance linear in \(N\) with high probability [115; Prop. 16]. Each codeword then has coordinates of order \(O(\log N)\) with probability \(1-o(1)\) [115; Sec. 6.1]. Drawing codewords from the multinomial distribution instead lowers the typical coordinate bound to \(O(\log N/\log\log N)\), with a smaller guaranteed rate [115; Prop. 17 and Lemma 19].
Spacetime block code (STBC) If a codeword encodes \(k\) information symbols over \(T\) channel uses, then its rate is \(k/T\) symbols per channel use. A spacetime block code is said to be full rate when this equals the number \(n\) of transmit antennas, i.e., when \(k=nT\).
Spacetime code (STC) Shannon capacity of various multiple-input multiple-output (MIMO) channels has been determined [116–119]. MIMO channel capacity when the channel is unknown to the sender and receiver [120,121] can be interpreted as a problem of placing points on the Grassmannian [122].
Spatially coupled LDPC (SC-LDPC) code Spatial coupling of LDPC codes can increase the achievable rate against BEC, coming close to the capacity [123–125]. SC-LDPC codes achieve capacity of the binary memoryless symmetric (BMS) channel [96,126]. Spatial coupling of MN-LDPC and HA-LDPC codes yields bounded-density SC-MN and SC-HA families whose BEC BP thresholds are empirically close to the Shannon limit [64].
Sphere packing

The rate of a code consisting of \(M\) codewords that represent a signal of bandwidth \(W\) and duration \(T\) is defined as \begin{align} R=\frac{1}{T}\log_{2}M\quad\quadbits/s~.\tag*{$(4)$} \end{align}

The Shannon capacity of the AWGN channel for a signal whose power is \(P\) is \begin{align} C=W\log_{2}\left(1+\frac{P}{\sigma^{2}}\right)\,.\tag*{$(5)$} \end{align}Random sphere packings achieve this capacity [25]; see the book [127] for more details. Tradeoffs between various parameters have been analyzed [128]. Deterministic sets of constellations from quadrature rules can also achieve capacity [12].

Spherical code The Kabatiansky-Levenshtein bound [129][127; Ch. 9] is an upper bound on the rate of a spherical code with fixed Euclidean distance. A hierarchy of two-point linear-programming bounds strictly improves the optimized Kabatiansky-Levenshtein bound, including its spherical-cap optimization, for every fixed maximum inner product \(0<s<1\) [22; Ch. 2, Thm. 1.2 and Cor. 1.3].
Tensor-product code Rate of the tensor-product code \(C_A \otimes C_B\) is a product of the rates of the codes \(C_A\) and \(C_B\).
Tornado code Tornado-code ensembles can come arbitrarily close to the capacity of the binary erasure channel [130].
Traceability code

Suppose \(n\) is the number of users, \(k\) is the number of users known by the pirates, and \(p\) is the probability that the pirates cannot be traced. An open (public) resilient scheme using a hash function has users’ personal keys consisting of \(O(k^{2}\log n)\) decryption keys, which is the number of decryptions needed to reveal the information. The amount of data redundancy overhead is about \(O(k^{4}\log n)\) [131].

A secret resilient scheme using a hash function has users’ personal keys consisting of \(O( k \log(n/p) )\) decryption keys, which is the number of decryptions needed to reveal the information. The amount of data redundancy overhead is about \(O( k^{2} \log(n/p) )\) [131].

A threshold (secret) scheme using a hash function that is successful against pirates which decrypt with probability \(> q\) has users’ personal keys consisting of \((4k/3q)\log(n/p)\) decryption keys (note that this is the same as in the secret resilient scheme above). These types of schemes only need order \(O(1)\) decryption operations performed by users to decrypt the information successfully. Finally, the amount of data redundancy overhead is 4k encrypted keys, a large improvement compared to the above [131].
Tsfasman-Vladut-Zink (TVZ) code TVZ codes, either in the residue AG or evaluation AG constructions, exceed the asymptotic GV bound [3] (see also Ref. [132]). For square \(q \geq 49\), these codes improve on the GV bound; for smaller \(q\), they do not [6; Sec. 15.4.2]. Roughly speaking, this result implies that AG codes can outperform random codes.
Turbo code Turbo codes nearly achieve the Shannon capacity [133].
Varshamov-Tenengolts (VT) code Has asymptotic rate \(1\). The redundancy is about \(\log_2(n+1)\) bits, making the construction nearly optimal for single-deletion correction.
Wozencraft ensemble code Meets the GV bound for most choices of \(\alpha\). Puncturing the code yields a higher rate with also meeting the GV bound; see Ref. [134]. These codes can be used to asymptotically improve over the GV bound [135].
Wrapped spherical code Asymptotically maximal spherical coding density is obtained with the densest possible sphere packing.
Zetterberg code The rate is given by \(1-\frac{4s}{n}\), which is asymptotically good, with a minimum distance of 5.
\([2^r-1,2^r-r-1,3]\) Hamming code Asymptotic rate \(k/n = 1-\frac{\log n}{n} \to 1\) and normalized distance \(d/n \to 0\).
\([2q+2,q+1]_3\) Pless symmetry code Achieve capacity of the ternary erasure channel; see Ref. [79].
\([n,n-1,2]\) Single parity-check (SPC) code The code rate is \(\frac{n-1}{n}\to 1\) as \(n\to\infty\).
\(q\)-ary LDPC code An \((n,j,k)\) \(q\)-ary LDPC code has rate at least \(1-j/k\) by parity-check counting, and Gallager extended the corresponding regular-ensemble analysis to arbitrary alphabet sizes [111; Ch. 5]. Asymptotically good non-binary expander codes can be constructed [137][136; Thm. 7.16] by generalizing the originally binary expander constructions [54,138].
\(q\)-ary code The rate of a \(q\)-ary code is usually defined as \(R=\frac{1}{n}\log_q K\) dits per symbol. The maximum rate of a \(q\)-ary code with linear distance is lower bounded by the asymptotic GV bound and upper bounded by the \(q\)-ary version of the MRRW LP bound [139].
\(q\)-ary repetition code Code rate is \(1/n\), and code distance is \(n\).
List (property_set_in_domain): All codes in Classical Domain with Rate.

References

  1. [1]

    V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block codes from orthogonal designs”, IEEE Transactions on Information Theory 45, 1456 (1999) DOI

  2. [2]

    Xue-Bin Liang, “Orthogonal designs with maximal rates”, IEEE Transactions on Information Theory 49, 2468 (2003) DOI

  3. [3]

    M. A. Tsfasman, S. G. Vlădutx, and Th. Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov‐Gilbert bound”, Mathematische Nachrichten 109, 21 (1982) DOI

  4. [4]

    A. Garcia and H. Stichtenoth, “A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound”, Inventiones Mathematicae 121, 211 (1995) DOI

  5. [5]

    A. Garcia and H. Stichtenoth, “On the Asymptotic Behaviour of Some Towers of Function Fields over Finite Fields”, Journal of Number Theory 61, 248 (1996) DOI

  6. [6]

    A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 311-362 DOI

  7. [7]

    T. Høholdt, J. H. van Lint, and R. Pellikaan, “Algebraic geometry codes”, in Handbook of Coding Theory, Vol. I, Part 1, eds. V. S. Pless and W. C. Huffman (Elsevier, 1998), pp. 871-961

  8. [8]

    S. G. Vlăduţ and V. G. Drinfeld, “Number of points of an algebraic curve”, Funktsional’nyi Analiz i ego Prilozheniya 17(1), 68–69 (1983); Functional Analysis and Its Applications 17(1), 53–54 (1983)

  9. [9]

    A. Barg, I. Tamo, and S. Vlăduţ, “Locally recoverable codes on algebraic curves”, 2015 IEEE International Symposium on Information Theory (ISIT) 1252 (2015) arXiv:1603.08876 DOI

  10. [10]

    L. P. Natarajan and P. Krishnan, “Berman Codes: A Generalization of Reed-Muller Codes that Achieve BEC Capacity”, (2023) arXiv:2202.09981

  11. [11]

    C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI

  12. [12]

    Y. Wu and S. Verdu, “The impact of constellation cardinality on Gaussian channel capacity”, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) 620 (2010) DOI

  13. [13]

    C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 623 (1948) DOI

  14. [14]

    S. Guha and M. M. Wilde, “Polar coding to achieve the Holevo capacity of a pure-loss optical channel”, 2012 IEEE International Symposium on Information Theory Proceedings 546 (2012) arXiv:1202.0533 DOI

  15. [15]

    R. McEliece, E. Rodemich, H. Rumsey, and L. Welch, “New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities”, IEEE Transactions on Information Theory 23, 157 (1977) DOI

  16. [16]

    M. Navon and A. Samorodnitsky, “Linear Programming Bounds for Codes via a Covering Argument”, Discrete &amp; Computational Geometry 41, 199 (2008) DOI

  17. [17]

    J. Friedman and J.-P. Tillich, “Generalized Alon–Boppana Theorems and Error-Correcting Codes”, SIAM Journal on Discrete Mathematics 19, 700 (2005) DOI

  18. [18]

    A. Barg and D. Nogin, “A Functional View of Upper Bounds on Codes”, Coding and Cryptology 15 (2008) DOI

  19. [19]

    A. M. Barg and D. Yu. Nogin, “Spectral approach to linear programming bounds on codes”, Problems of Information Transmission 42, 77 (2006) DOI

  20. [20]

    A. Samorodnitsky, “One more proof of the first linear programming bound for binary codes and two conjectures”, (2021) arXiv:2104.14587

  21. [21]

    N. Linial and E. Loyfer, “An Elementary Proof of the First LP Bound on the Rate of Binary Codes”, (2023) arXiv:2303.16619

  22. [22]

    OpenAI, Ten Advances in Mathematics and Theoretical Computer Science (2026) URL

  23. [23]

    O. Alrabiah and V. Guruswami, “Binary code rate bounds via classical–quantum channels”, (2026) arXiv:2608.09347

  24. [24]

    A. Barg, “Comments on the recent improvements of the MRRW bounds”, (2026) arXiv:2609.01860

  25. [25]

    C. E. Shannon, “Probability of Error for Optimal Codes in a Gaussian Channel”, Bell System Technical Journal 38, 611 (1959) DOI

  26. [26]

    C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I”, Information and Control 10, 65 (1967) DOI

  27. [27]

    R. M. Fano. The transmission of information. 65. Cambridge, MA, USA: Massachusetts Institute of Technology, Research Laboratory of Electronics, 1949

  28. [28]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  29. [29]

    E. Goldenberg, M. Habib, and K. C. S, “Explicit Good Codes Approaching Distance 1 in Ulam Metric”, (2024) arXiv:2401.17235

  30. [30]

    A. Barg, J. Justesen, and C. Thommesen, “Concatenated codes with fixed inner code and random outer code”, IEEE Transactions on Information Theory 47, 361 (2001) DOI

  31. [31]

    D. Doron, J. Mosheiff, and M. Wootters, “When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?”, (2024) arXiv:2405.08584

  32. [32]

    T. Kløve, “Error correcting codes for the asymmetric channel”, Department of Pure Mathematics, University of Bergen, 1981

  33. [33]

    M. Grassl, P. W. Shor, G. Smith, J. Smolin, and B. Zeng, “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI

  34. [34]

    R. J. McEliece and E. R. Rodemich, “The constantinrao construction for binary asymmetric error-correcting codes”, Information and Control 44, 187 (1980) DOI

  35. [35]

    K. A. S. Abdel-Ghaffar and H. C. Ferreira, “Systematic encoding of the Varshamov-Tenengol’ts codes and the Constantin-Rao codes”, IEEE Transactions on Information Theory 44, 340 (1998) DOI

  36. [36]

    L. Sari, “Effects of Puncturing Patterns on Punctured Convolutional Codes”, TELKOMNIKA (Telecommunication, Computing, Electronics and Control) 10, (2012) DOI

  37. [37]

    L. Decreusefond and G. Zemor, “On the error-correcting capabilities of cycle codes of graphs”, Proceedings of 1994 IEEE International Symposium on Information Theory 307 DOI

  38. [38]

    K. Cheng, V. Guruswami, B. Haeupler, and X. Li, “Efficient Linear and Affine Codes for Correcting Insertions/Deletions”, (2022) arXiv:2007.09075

  39. [39]

    C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI

  40. [40]

    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

  41. [41]

    V. Strassen, “Asymptotische Absch¨atzungen in Shannons Informationstheorie”, Trans. Third Prague Conference on Information Theory, Prague, 689–723, (1962)

  42. [42]

    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

  43. [43]

    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

  44. [44]

    Y. Altug and A. B. Wagner, “Moderate Deviations in Channel Coding”, (2012) arXiv:1208.1924

  45. [45]

    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

  46. [46]

    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

  47. [47]

    R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI

  48. [48]

    I. Csiszár and J. Körner, Information Theory (Cambridge University Press, 2011) DOI

  49. [49]

    S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels (Corresp.)”, IEEE Transactions on Information Theory 19, 357 (1973) DOI

  50. [50]

    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

  51. [51]

    S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-Length Scaling for Polar Codes”, IEEE Transactions on Information Theory 60, 5875 (2014) DOI

  52. [52]

    W. Doeblin, “Sur les propriétés asymptotiques de mouvement régis par certains types de chaines simples”, Bulletin mathématique de la Société roumaine des sciences 39(1), 57-115 (1937)

  53. [53]

    A. Makur and J. Singh, “Doeblin Coefficients and Related Measures”, IEEE Transactions on Information Theory 70, 4667 (2024) arXiv:2309.08475 DOI

  54. [54]

    M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI

  55. [55]

    Y. Chen and Z. Zhang, “Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds”, (2025) arXiv:2408.15925

  56. [56]

    D. Boneh and J. Shaw, “Collusion-Secure Fingerprinting for Digital Data”, Lecture Notes in Computer Science 452 (1995) DOI

  57. [57]

    C. Shangguan, X. Wang, G. Ge, and Y. Miao, “New Bounds For Frameproof Codes”, (2014) arXiv:1411.5782

  58. [58]

    D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density paritycheck codes”, Electronics Letters 33, 457 (1997) DOI

  59. [59]

    D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transactions on Information Theory 45, 399 (1999) DOI

  60. [60]

    D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, The IMA Volumes in Mathematics and its Applications 113 (2001) DOI

  61. [61]

    G. Reeves and H. D. Pfister, “Achieving Capacity on Non-Binary Channels with Generalized Reed-Muller Codes”, (2023) arXiv:2305.07779

  62. [62]

    C. Thommesen, “The existence of binary linear concatenated codes with Reed - Solomon outer codes which asymptotically meet the Gilbert- Varshamov bound”, IEEE Transactions on Information Theory 29, 850 (1983) DOI

  63. [63]

    C.-H. Hsu and A. Anastasopoulos, “Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels”, (2005) arXiv:cs/0509062

  64. [64]

    K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI

  65. [65]

    K. Kasai, “Finite-Degree Quantum LDPC Codes Reaching the Gilbert-Varshamov Bound”, (2026) arXiv:2603.24588

  66. [66]

    A. Barg, G. Cohen, S. Encheva, G. Kabatiansky, and G. Zémor, “A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents”, SIAM Journal on Discrete Mathematics 14, 423 (2001) DOI

  67. [67]

    T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes”, IEEE Transactions on Information Theory 47, 619 (2001) DOI

  68. [68]

    Sae-Young Chung, G. D. Forney, T. J. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit”, IEEE Communications Letters 5, 58 (2001) DOI

  69. [69]

    C. Di, T. J. Richardson, and R. L. Urbanke, “Weight Distribution of Low-Density Parity-Check Codes”, IEEE Transactions on Information Theory 52, 4839 (2006) DOI

  70. [70]

    H. Jin, A. Khandekar, and R. J. McEliece, “Irregular repeat-accumulate codes”, Proc. 2nd Int. Symp. Turbo Codes and Related Topics, 2000

  71. [71]

    H. D. Pfister, I. Sason, and R. Urbanke, “Capacity-Achieving Ensembles for the Binary Erasure Channel With Bounded Complexity”, IEEE Transactions on Information Theory 51, 2352 (2005) DOI

  72. [72]

    Y. Tan, B. Roberts, N. Tantivasadakarn, B. Yoshida, and N. Y. Yao, “Fracton models from product codes”, Physical Review Research 7, (2025) arXiv:2312.08462 DOI

  73. [73]

    R. Urbanke and B. Rimoldi, “Lattice codes can achieve capacity on the AWGN channel”, IEEE Transactions on Information Theory 44, 273 (1998) DOI

  74. [74]

    R. de Buda, “The upper error bound of a new near-optimal code”, IEEE Transactions on Information Theory 21, 441 (1975) DOI

  75. [75]

    R. de Buda and W. Kassem, About lattices and the random coding theorem, in Abstracts of Papers, IEEE Inter. Symp. Info. Theory 1981, IEEE Press, NY 1981, p. 145

  76. [76]

    W. Kassem, “Optimal Lattice Codes for the Gaussian Channel”, PhD thesis, McMaster University, 1981

  77. [77]

    S. Kumar and H. D. Pfister, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2015) arXiv:1505.05123

  78. [78]

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu, and R. Urbanke, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2016) arXiv:1601.04689

  79. [79]

    K. Ivanov and R. L. Urbanke, “Capacity-achieving codes: a review on double transitivity”, (2020) arXiv:2010.15453

  80. [80]

    R. R. Varshamov, “Some features of linear codes that correct asymmetric errors”, Soviet Physics Doklady 9 (1965)

  81. [81]

    S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for Reliable Quantum Information Storage in 2D Systems”, Physical Review Letters 104, (2010) arXiv:0909.5200 DOI

  82. [82]

    N. Baspin, “On combinatorial structures in linear codes”, (2023) arXiv:2309.16411

  83. [83]

    G. D. Forney, “On the Hamming distance properties of group codes”, IEEE Transactions on Information Theory 38, 1797 (1992) DOI

  84. [84]

    E. Biglieri and M. Elia, “On the construction of group block codes”, Annales Des Télécommunications 50, 817 (1995) DOI

  85. [85]

    J. C. Interlando, R. Palazzo, and M. Elia, “Group block codes over nonabelian groups are asymptotically bad”, IEEE Transactions on Information Theory 42, 1277 (1996) DOI

  86. [86]

    J. L. Massey, “Linear codes with complementary duals”, Discrete Mathematics 106–107, 337 (1992) DOI

  87. [87]

    I. Kerenidis and R. de Wolf, “Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument”, (2002) arXiv:quant-ph/0208062

  88. [88]

    A. Ben-Aroya, O. Regev, and R. de Wolf, “A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs”, 2008 49th Annual IEEE Symposium on Foundations of Computer Science 477 (2008) arXiv:0705.3806 DOI

  89. [89]

    O. Goldreich, H. Karloff, L. J. Schulman, and L. Trevisan, “Lower bounds for linear locally decodable codes and private information retrieval”, Proceedings 17th IEEE Annual Conference on Computational Complexity 175 DOI

  90. [90]

    J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes”, Proceedings of the thirty-second annual ACM symposium on Theory of computing 80 (2000) DOI

  91. [91]

    V. R. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes”, IEEE Transactions on Information Theory 61, 5787 (2015) DOI

  92. [92]

    A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes”, IEEE Transactions on Information Theory 64, 3481 (2018) arXiv:1702.02685 DOI

  93. [93]

    J. Garcia-Frias and Wei Zhong, “Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix”, IEEE Communications Letters 7, 266 (2003) DOI

  94. [94]

    R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI

  95. [95]

    V. Guruswami, “Iterative Decoding of Low-Density Parity Check Codes (A Survey)”, (2006) arXiv:cs/0610022

  96. [96]

    S. Kudekar, T. Richardson, and R. Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation”, (2012) arXiv:1201.2999

  97. [97]

    J. Mosheiff, N. Resch, N. Ron-Zewi, S. Silas, and M. Wootters, “Low-Density Parity-Check Codes Achieve List-Decoding Capacity”, SIAM Journal on Computing 53, FOCS20 (2021) arXiv:1909.06430 DOI

  98. [98]

    D. J. C. MacKay and R. M. Neal, “Good codes based on very sparse matrices”, Lecture Notes in Computer Science 100 (1995) DOI

  99. [99]

    K. Kasai, “MacKay-Neal Codes Achieve Capacity under MAP Decoding”, (2026) arXiv:2610.10277

  100. [100]

    H. Landau, “How does a porcupine separate its quills?”, IEEE Transactions on Information Theory 17, 157 (1971) DOI

  101. [101]

    R. E. Blahut, Modem Theory (Cambridge University Press, 2009) DOI

  102. [102]

    E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”, IEEE Transactions on Information Theory 55, 3051 (2009) arXiv:0807.3917 DOI

  103. [103]

    N. Hussami, S. B. Korada, and R. Urbanke, “Performance of polar codes for channel and source coding”, 2009 IEEE International Symposium on Information Theory 1488 (2009) DOI

  104. [104]

    M. Mondelli, S. H. Hassani, and R. L. Urbanke, “Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors”, IEEE Transactions on Information Theory 62, 6698 (2016) DOI

  105. [105]

    S. B. Korada, A. Montanari, E. Telatar, and R. Urbanke, “An empirical scaling law for polar codes”, 2010 IEEE International Symposium on Information Theory 884 (2010) DOI

  106. [106]

    A. Barg and G. D. Forney, “Random codes: minimum distances and error exponents”, IEEE Transactions on Information Theory 48, 2568 (2002) DOI

  107. [107]

    A. Barg and A. Mazumdar, “Codes in permutations and error correction for rank modulation”, 2010 IEEE International Symposium on Information Theory 854 (2010) DOI

  108. [108]

    G. Reeves and H. D. Pfister, “Reed–Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for all Rates Below Capacity”, IEEE Transactions on Information Theory 70, 920 (2024) arXiv:2110.14631 DOI

  109. [109]

    E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors”, (2014) arXiv:1411.4590

  110. [110]

    E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels”, (2023) arXiv:2304.02509

  111. [111]

    R. Gallager, “Low-density parity check codes”, PhD thesis, MIT, 1963 URL

  112. [112]

    T. Richardson and R. Urbanke, “The renaissance of gallager’s low-density parity-check codes”, IEEE Communications Magazine 41, 126 (2003) DOI

  113. [113]

    L. Bazzi, M. Mahdian, and D. A. Spielman, “The Minimum Distance of Turbo-Like Codes”, IEEE Transactions on Information Theory 55, 6 (2009) DOI

  114. [114]

    V. Guruswami and W. Machmouchi, “Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction”, 2008 IEEE International Symposium on Information Theory 1968 (2008) DOI

  115. [115]

    D. Elimelech, A. Aydin, and A. Barg, “Asymptotically good bosonic Fock state codes”, Quantum 10, 2240 (2026) arXiv:2603.15190 DOI

  116. [116]

    G. J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas”, Bell Labs Technical Journal 1, 41 (2002) DOI

  117. [117]

    E. Telatar, “Capacity of Multi‐antenna Gaussian Channels”, European Transactions on Telecommunications 10, 585 (1999) DOI

  118. [118]

    G. J. Foschini and M. J. Gans, “On Limits of Wireless Communications in a Fading Environment when Using Multiple Antennas”, Wireless Personal Communications 6, 311 (1998) DOI

  119. [119]

    A. Goldsmith, S. A. Jafar, N. Jindal, and S. Vishwanath, “Capacity limits of MIMO channels”, IEEE Journal on Selected Areas in Communications 21, 684 (2003) DOI

  120. [120]

    B. M. Hochwald and T. L. Marzetta, “Unitary space-time modulation for multiple-antenna communications in Rayleigh flat fading”, IEEE Transactions on Information Theory 46, 543 (2000) DOI

  121. [121]

    T. L. Marzetta and B. M. Hochwald, “Capacity of a mobile multiple-antenna communication link in Rayleigh flat fading”, IEEE Transactions on Information Theory 45, 139 (1999) DOI

  122. [122]

    Lizhong Zheng and D. N. C. Tse, “Communication on the Grassmann manifold: a geometric approach to the noncoherent multiple-antenna channel”, IEEE Transactions on Information Theory 48, 359 (2002) DOI

  123. [123]

    A. Jimenez Felstrom and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix”, IEEE Transactions on Information Theory 45, 2181 (1999) DOI

  124. [124]

    S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC”, IEEE Transactions on Information Theory 57, 803 (2011) DOI

  125. [125]

    M. Lentmaier, A. Sridharan, K. Sh. Zigangirov, and D. J. Costello, “Terminated LDPC convolutional codes with thresholds close to capacity”, Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. 1372 (2005) arXiv:cs/0508030 DOI

  126. [126]

    S. Kumar, A. J. Young, N. Macris, and H. D. Pfister, “Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels”, IEEE Transactions on Information Theory 60, 7389 (2014) arXiv:1309.7543 DOI

  127. [127]

    J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI

  128. [128]

    D. Slepian, “Bounds on Communication”, Bell System Technical Journal 42, 681 (1963) DOI

  129. [129]

    G. A. Kabatiansky, V. I. Levenshtein, “On Bounds for Packings on a Sphere and in Space”, Problemy Peredachi Informatsii 14(1), 3–25 (1978); Problems of Information Transmission 14(1), 1–17 (1978)

  130. [130]

    M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI

  131. [131]

    B. Chor, A. Fiat, M. Naor, and B. Pinkas, “Tracing traitors”, IEEE Transactions on Information Theory 46, 893 (2000) DOI

  132. [132]

    Y. Ihara, “Some remarks on the number of rational points of algebraic curves over finite fields”, Journal of the Faculty of Science, University of Tokyo, Section IA Mathematics 28, 721-724 (1981)

  133. [133]

    C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1”, Proceedings of ICC ’93 - IEEE International Conference on Communications 2, 1064 DOI

  134. [134]

    V. Guruswami and S. Li, “A Deterministic Construction of a Large Distance Code From the Wozencraft Ensemble”, IEEE Transactions on Information Theory 71, 930 (2025) arXiv:2305.02484 DOI

  135. [135]

    P. Gaborit and G. Zemor, “Asymptotic Improvement of the Gilbert–Varshamov Bound for Linear Codes”, IEEE Transactions on Information Theory 54, 3865 (2008) arXiv:0708.4164 DOI

  136. [136]

    F. G. Jeronimo, “Fast decoding of explicit almost optimal ε-balanced q-ary codes and fast approximation of expanding k-CSPs”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

  137. [137]

    A. Rao, “Lecture 6: Expander Codes: Tanner Codes”, Coding Theory lecture notes, 14 Oct. 2019, University of Washington

  138. [138]

    G. Zemor, “On expander codes”, IEEE Transactions on Information Theory 47, 835 (2001) DOI

  139. [139]

    M. Aaltonen, “A new upper bound on nonbinary block codes”, Discrete Mathematics 83, 139 (1990) DOI