Here is a list of classical codes that have notable decoders.

[Jump to code graph excerpt]

Name Decoder(s)
Alternant code Variation of the Berlekamp-Welch algorithm [1].Euclidean algorithm; see [2; Ch. 12] for more details.Guruswami-Sudan list decoder [3,4].
Analog RS code Syndrome repairing (SR) decoder [5].
B-code Efficient decoding algorithm against erasures [6].
Balanced code Efficient decoder [7–9].
Binary BCH code Peterson decoder with runtime of order \(O(n^3)\) [10,11] (see exposition in Ref. [12]).Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [13,14] and modification by Burton [15]; see also [16,17].Sugiyama et al. modification of the extended Euclidean algorithm [18,19].Guruswami-Sudan list decoder [3,4].
Binary code For few-bit codes (\(n\) is small), decoding can be based on a lookup table. For infinite code families, the size of such a table scales exponentially with \(n\), so approximate decoding algorithms scaling polynomially with \(n\) have to be used. The decoder determining the most likely error given a noise channel is called the maximum-likelihood decoder.Given a received string \(x\) and an error bound \(e\), a list decoder returns a list of all codewords that are at most \(e\) from \(x\) in Hamming distance. The number of codewords in a neighborhood of \(x\) has to be polynomial in \(n\) in order for this decoder to run in time polynomial in \(n\).
Binary quadratic-residue (QR) code Algebraic decoder [20].
Block code Decoding an error-correcting code is equivalent to finding the ground state of a statistical mechanical model [21].
Bose–Chaudhuri–Hocquenghem (BCH) code Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [13,14,22] and modification by Burton [15]; see also [16,17].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [10,23] (see exposition in Ref. [12]).Sugiyama et al. modification of the extended Euclidean algorithm [18,19].
Concatenated code Generalized minimum-distance decoder [24].
Convolutional code Decoders based on the Viterbi algorithm (trellis decoding) were developed first, which result in the most-likely codeword for the encoded bits [25].BCJR decoder, also a trellis-based decoder [26].
Coxeter code Majority-logic decoder generalizing the Reed decoder of RM codes, correcting up to \(d/2-1\) errors [27; Sec. 5].
Cyclic linear \(q\)-ary code Meggitt decoder [28].Information set decoding (ISD) [29], a probabilistic decoding strategy that essentially tries to guess an information set of \(k\) correct positions in the received word, where \(k\) is the code dimension. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming those \(k\) positions are error-free. When the Hamming weight of the error vector is low enough, that codeword is assumed to be the intended transmission.Permutation decoding [30].
Cyclic linear binary code Meggitt decoder [28].Information set decoding (ISD) [29], a probabilistic decoding strategy that essentially tries to guess an information set of \(k\) correct positions in the received word, where \(k\) is the code dimension. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming those \(k\) positions are error-free. When the Hamming weight of the error vector is low enough, that codeword is assumed to be the intended transmission.Permutation decoding [30].
Cyclic redundancy check (CRC) code GRAND [31].
Delsarte-Goethals (DG) code Since the equivalent \(\mathbb{Z_4}\) codes are extended cyclic codes, efficient encoding and decoding is possible [32].
Determinant code For exact repair, the interior points of the storage-bandwidth trade-off curve can be shown to be the convex hull of \(k\) corner points described by \((\alpha_m,\beta_m)= (\binom{k}{m},\binom{k-1}{m-1})\) for \(m\in\{1,2,\cdots,k\}\).
EVENODD code Efficient decoding algorithm against two erasures [33].
Error-correcting output code (ECOC) Standard Hamming-distance decoding [34].Inverse Hamming decoding [35].Euclidean-distance decoding or attenuated Euclidean decoding [36].Loss-based decoding [37].Probabilistic-based decoding [38].
Evaluation AG code Generalization of plane-curve decoder [39]. Another decoder [40] was later shown to be equivalent in Ref. [41]. Application of several algorithms in parallel can be used to decode up to half the minimum distance [42,43]. Computational procedure implementing these decoders is based on an extension of the Berlekamp-Massey algorithm by Sakata [44–46].Decoder based on majority voting of unknown syndromes [47] decodes up to half of the minimum distance [48].List decoders generalizing Sudan’s RS decoder by Shokrollahi-Wasserman [49] and Guruswami-Sudan [4].
Expander code Decoding can be done in \(O(n)\) runtime using a greedy flip decoder [50] (see also [51]). The algorithm consists of flipping a bit of the received word if it will result in a greater number of satisfied parity checks. This is repeated until a codeword is reached. It corrects \((1-2\epsilon)\gamma n\) errors for \(\epsilon < 1/4\) [50].‘Find erasures and Decode’ a.k.a. Viderman’s algorithm correcting \((1-3\epsilon)\gamma n/(1-2\epsilon)\) errors for \(\epsilon < 1/3\) in order \(O(n)\) time [52]. Its erasure-decoding subroutine corrects up to \((1-\xi)\gamma n/(2\epsilon)\) erasures in linear time for any \(\xi > 0\) [53; Thm. 4.1].Linear-time decoder that guesses the expansion of the corrupted set and either runs Viderman’s find-erasures step or flips all bits with many unsatisfied parity checks [53; Thm. 5.4]. It corrects up to \((3\gamma/(16\epsilon)-\eta)n\) errors for any \(\eta > 0\) and \(\epsilon < 1/4\).Linear-time decoder for \(\epsilon \leq 1/8\) that guesses the size and expansion of the corrupted set and uses them to set the threshold of Viderman’s find-erasures step [53; Thm. 6.6]. It corrects up to \(((\sqrt{2}-1)\gamma/(2\epsilon)-\eta)n\) errors for \(\epsilon < (3-2\sqrt{2})/2\) and up to \(((1-2\epsilon)\gamma/(4\epsilon)-\eta)n\) errors otherwise, for any \(\eta > 0\).
Fibonacci code An efficient algorithm based on minimum-weight perfect matching [54], which can correct high-weight errors that span rows and columns of the 2D lattice, with failure rate decaying super-exponentially with \(L\).
Finite-dimensional error-correcting code (ECC) Capacity-achieving Guessing Random Additive Noise Decoding (GRAND) [55] (see also [56]).
Folded RS (FRS) code Guruswami and Rudra [57,58] achieved list-decoding up to \(1-\frac{k}{n}-\epsilon\) fraction of errors using the Parvaresh-Vardy algorithm [59]; see Ref. [60] for a randomized construction.List-decoding works up to the Johnson bound using the Guruswami-Sudan algorithm [61].Folded RS codes, concatenated with suitable inner codes, can be efficiently list-decoded up to the Blokh-Zyablov bound [57,62].
Fountain code Invert the fragment generator matrix resulting from the continuous encoding process. If exactly \(K\) packets are received, then the probability of decoding correctly is \(0.289\). Extra packets increase this probability exponentially. The decoding runtime is dominated by the matrix inversion step, which takes order \(O(n^3)\) time.
Gabidulin code Fast decoder based on a transform-domain approach [63].Subcodes of Gabidulin codes whose evaluation points span a subfield can be list decoded up to the Singleton bound, with the subcode chosen by a Monte Carlo construction [64] or explicitly [65].
Generalized RS (GRS) code The decoding process of GRS codes reduces to the solution of a polynomial congruence equation, usually referred to as the key equation. Decoding schemes are based on applications of the Euclid algorithm to solve the key equation.Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [13,14,22].Guruswami-Sudan list decoder [3,4] and modification by Koetter-Vardy for soft-decision decoding [66].Hard-decision decoder for errors within the Singleton bound [67].
Goppa code Algebraic decoding algorithms [68]. If \( deg G(x) = 2t \) , then there exists a \(t\)-correcting algebraic decoding algorithm for \( \Gamma(L,G) \).Sugiyama et al. modification of the extended Euclidean algorithm [18,19].Binary Goppa codes can be decoded using an RS-based decoder [69].List decoder for binary Goppa codes [70].
Hergert code Since the equivalent \(\mathbb{Z}_4\) codes are extended cyclic codes, efficient encoding and decoding is possible [32,71].
Hermitian code Unique decoding using syndromes and error locator ideals for polynomial evaluations. Note that Hermitian codes are linear codes so we can compute the syndrome of a received vector. Moreover, akin to the error-locator ideals found in decoding RS codes, for the multivariate case we must define an error locator ideal \(\Lambda \) such that the variety of this ideal over \(\mathbb{F}^{2}_q\) is exactly the set of errors. The Sakata algorithm uses these two ingredients to get a unique decoding procedure [44].
Higman-Sims graph-adjacency code The rows of the adjacency matrix can be used as orthogonal parity checks enabling majority decoding of \(C_{HS}^\perp\) up to two errors [72; Prop. 1.4].
Hoffman-Singleton graph-adjacency code The rows of the adjacency matrix serve as orthogonal parity checks enabling majority decoding of the \([50,28,8]\) dual code up to three errors (its full error-correcting capacity) [72].
Interleaved RS (IRS) code Decoder that corrects up to \(1-\frac{2k+n}{3n}\) fraction of random errors [73].Decoder that corrects up to \(1-(\frac{k}{n})^{2/3}\) fraction of random errors [74].
Irregular convolutional code (IRCC) Extrinsic information transfer (EXIT) charts [75].
Irregular repeat-accumulate (IRA) code Linear-time decoder [76].
Justesen code Generalized minimum distance decoding [77].
Kerdock code Soft decision decoding involves extending the Fast Hadamard Transform decoding algorithm for the first-order RM code to Kerdock code [32].Complexity of soft decision decoding algorithm: \(4^m\) multiplications and \(m4^m\) additions [32].
Lattice Sphere decoder [78,79].
Linear STC Sphere decoder [80–82].
Linear \(q\)-ary code Maximum likelihood (ML) decoding. This algorithm decodes a received word to the most likely sent codeword based on the received word. ML decoding of reduced complexity is possible for virtually all \(q\)-ary linear codes [83].Optimal symbol-by-symbol decoding rule [84].Information set decoding (ISD) [85], a probabilistic decoding strategy that essentially tries to guess \(k\) correct positions in the received word, where \(k\) is the size of the code. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming the \(k\) positions are error free. When the Hamming weight of the error vector is low enough, that codeword is assumed to be the intended transmission.Generalized minimum-distance decoder [24].Soft-decision maximum-likelihood trellis-based decoder [86].Extensions of algebraic-geometry decoders to linear codes [87,88].
Linear binary code Decoding an arbitrary linear binary code is \(NP\)-complete [89,90].Slepian’s standard-array decoding [91].Recursive maximum likelihood decoding [92].Deep learning [93] and a transformer graph neural net (GNN) for soft decoding [94].Chase decoding, which uses channel measurement information [95].
Linear code with complementary dual (LCD) The decoding problem reduces to finding the nearest codeword in \(C\) given a word in \(C^{\perp}\) [96].
Linearized RS code Berlekamp-Welch-type decoder [97] and its sum-rank version [98].
Locally decodable code (LDC) LDCs admit decoders whose runtime scales polylogarithmically with \(n\).A 2-query LDC with recovery probability \(1/2+\epsilon\) can be decoded with one quantum query to the received word at recovery probability at least \(1/2+4\epsilon/7\) [99; Thm. 1].An LDC whose decoder outputs the XOR of its \(2r\) queried bits can be decoded with \(r\) quantum queries at the same recovery probability [99; Thm. 5].
Low-density parity-check (LDPC) code Gallager introduced a hard-decision iterative decoder that flips any digit contained in more than a fixed number of unsatisfied parity checks [100; Ch. 4].Gallager also introduced an iterative probabilistic decoding procedure on the computation tree; this is a precursor to modern message-passing, belief-propagation (BP), and sum-product decoding [101–104][100; Ch. 4] (see also [105,106]).Soft-decision Sum-Product Algorithm (SPA) [103,104] and its simplification the Min-Sum Algorithm (MSA) [107].Linear programming [108–110].Iterative decoder using stochastic computation [111].Iterative LDPC decoders can get stuck at stopping sets of their Tanner graphs [112], with decoder performance improving with the size of the smallest stopping set; see [113; Sec. 21.3.1] for more details. The smallest stopping set size can reach the minimum distance of the code [114].Ensembles of random LDPC codes under iterative decoders are subject to the concentration theorem [104,115]; see [113; Thm. 21.7.1] for the case of the BEC.Reinforcement learning [116].Quantum-enhanced BP decoding [117].
Low-rank parity-check (LRPC) code Efficient probabilistic decoder [118].Mixed decoder [119].
Luby transform (LT) code Sum-Product Algorithm (SPA), often called a peeling decoder [120,121], similar to belief propagation [122].
MacKay-Neal LDPC (MN-LDPC) code Free-energy minimization and a BP decoder [123].
Matrix-product code Decoder up to half of the minimum distance for NSC codes [124].
Multiplicity code Multivariate multiplicity codes can be decoded up to half of the minimum distance in polynomial time [125,126].Univariate [127] and multivariate [125] multiplicity codes can be list-decoded up to the Johnson bound. Certain univariate code families achieve the list-decoding capacity for sufficiently large field characteristic [125,128].
Newman-Moore code Efficient decoder [129].
Orthogonal Spacetime Block Code (OSTBC) Maximum-likelihood decoding can be achieved with only linear processing [130].
Parvaresh-Vardy (PV) code PV codes can be list-decoded up to \(1-(t k/n)^{1/(t+1)}\) fraction of errors. This result improves over the Guruswami-Sudan algorithm for ordinary RS codes, which list-decodes up to \(1-\sqrt{k/n}\) fraction of errors.
Permutation spherical code Efficient maximum-likelihood decoder determining the Voronoi region of an error word.
Plane-curve evaluation code Generalization of the Peterson algorithm for BCH codes [39,131,132].
Polar code Successive cancellation (SC) decoder [133].Successive cancellation list (SCL) decoder [134] and a modification utilizing sequence repetition (SR-List) [135].Soft cancellation (SCAN) decoder [136,137].Belief propagation (BP) decoder [138].Noisy quantum gate-based decoder [139].
Quaternary RM (QRM) code QRM codes whose Gray images are Preparata codes can be decoded using a syndrome-calculation-based algorithm to correct all error patterns of Lee weight at most 2 and detect all (or, for some constructions, a subset of) error patterns of Lee weight 3 or 4 [32].
Random code Ball-collision decoding [140].Information set decoding (ISD) [141] and Finiasz and Sendrier (FS-ISD) decoding [142].
Rank-metric code Polynomial-reconstruction Berlekamp-Welch based decoder [143].Berlekamp-Massey based decoder [144].
Raptor (RAPid TORnado) code Raptor codes can be decoded using inactivation decoding [145], a combination of belief-propagation and Gaussian elimination decoding.
Reed-Muller (RM) code Reed decoder with \(r+1\)-step majority decoding corrects \(\frac{1}{2}(2^{m-r}-1)\) errors [146] (see also [2; Ch. 13]).Sequential code-reduction decoding [147].Matrix factorization can be used to decode an RM\((n,n-3)\) code [148]; see [149].
Reed-Solomon (RS) code Decoding general RS codes is \(NP\)-hard [150].Although using iFFT has its counterpart iNNT for finite fields, the decoding is usually standard polynomial interpolation in \(k=O(n\log^2 n)\). However, in erasure decoding, encoded values are only erased in \(r\) points, which is a specific case of polynomial interpolation and can be done in \(O(n\log n)\) by computing product of the received polynomial and an erasure locator polynomial and using long division to find an original polynomial. The long division step can be omitted to increase speed further by only dividing the derivative of the product polynomial, and derivative of erasure locator polynomial evaluated at erasure locations.Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [13,14].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [10,23] (see exposition in Ref. [12]).Berlekamp-Welch decoder with runtime of order \(O(n^3)\) [151] (see exposition in Ref. [152]), assuming that \(t \geq (n+k)/2\).Sugiyama et al. modification of the extended Euclidean algorithm [18,19,153].Gao decoder using extended Euclidean algorithm [154].Fast-Fourier-transform decoder with runtime of order \(O(n polylogn)\) [155].List decoders try to find a low-degree bivariate polynomial \(Q(x,y)\) such that evaluation of \(Q\) at \((\alpha_i,y_i)\) is zero. By choosing proper degrees, it can be shown such polynomial exists by drawing an analogy between evaluation of \(Q(\alpha_i,y_i)\) and solving a homogeneous linear equation (interpolation). Once this is done, one lists roots of \(y\) that agree at \(\geq t\) points. The Sudan list-decoding algorithm corrects up to \(1-\sqrt{2R}\) fraction of errors asymptotically in \(n\) [156]. A modified key equation allows correction of more than \(\left\lfloor (n-k)/2 \right\rfloor\) errors [157]. The Guruswami-Sudan algorithm improved the Sudan algorithm to the Johnson radius \(1-\sqrt{R}\) [4], which lies below the list-decoding capacity \(1-R\). See Ref. [158] for limits to list decoding RS codes. RS codes of any constant rate over prime fields of polynomial size can be list decoded up to capacity in deterministic polynomial time for every evaluation set [159,160]. The Koetter-Vardy modification of the Guruswami-Sudan algorithm is used for soft-decision decoding [66] (see also Ref. [161]). Subcodes of RS codes whose evaluation points lie in a subfield can be list decoded up to the capacity \(1-R\) [64]. Explicit such subcodes, built from permuted products of two RS codes, can be efficiently list decoded up to capacity with constant list size [162]. List decoding of RS codes is known as noisy polynomial interpolation in cryptography [163].The ubiquity of RS codes has yielded off-the-shelf VLSI integrated-circuit decoding hardware [164] (see also [165; Chs. 5 and 10]).
Regenerating code (RGC) If the recovered symbols are exactly equal to the erased symbols, the repair is called an exact repair.If the recovered symbols are not exactly equal to the erased symbols but still preserve the code properties, the repair is called a functional repair.
Regular LDPC code The BP decoding threshold for regular codes is strictly below the Shannon capacity for any fixed \(j,k\) [166; Sec. 3.11].
Regular binary Tanner code Parallel decoding algorithm corrects a fraction \(\delta_0^2/48\) of errors for Tanner codes [50]. A modification of said algorithm improves the fraction to \(\delta_0^2/4\) with no extra cost to complexity [167].Soft-decision linear-time decoder correcting errors almost up to half of the Blokh-Zyablov bound [168].
Repetition code Calculate the Hamming weight \(d_H\) of an error word. If \(d_H\leq \frac{n-1}{2}\), decode the code as 0. If \(d_H\geq \frac{n+1}{2}\), decode the code as 1.Local automaton decoder for the repetition code on a 2D lattice based on Toom’s rule [169–172].Local automaton decoder for the repetition code on a 1D lattice by Gacs that is translation-invariant, that does not require synchronization of local clocks, and that has a constant encoding rate [173–176].Local automaton decoder for the repetition code on a 1D lattice by Tsirelson [177].Local automaton decoder obtained from reinforcement learning [178].
Sphere packing Each signal point is assigned its own Voronoi cell, and a received point is mapped back to the center of the Voronoi cell in which it is located upon reception.
Subspace code List decoding up to the Singleton bound [64].
Ta-Shma zigzag code Unique and list decoders [179].
Tamo-Barg code Polynomial evaluation over \(r\) points [180].
Tanner code Min-sum and sum-product iterative decoders for binary Tanner codes [181,182]; see also [19,183]. These decoders can be improved using a probabilistic message-passing schedule [184].Any code can be put into normal form without significantly altering the underlying graph or the decoding complexity [185]. For an algebraic viewpoint on decoding, see [186].Iterative decoding is optimal for Tanner graphs that are free of cycles [182]. However, codes that admit cycle-free representations have bounds on their distances [187,188]; see [113,189].
Telegraph code Mutilation-table lookup lists the candidate codewords for a received non-codeword, e.g., five for ZNBAB, and the meaning of the decoded text is used to select one [190; Sec. 3].Terminal indices list codewords alphabetized by their last two letters, for use when the beginning of a codeword is corrupted [190; Sec. 3].
Tensor-product code The simple decoding algorithm (first decode all columns with \(C_A\), then all rows with \(C_B\)) corrects up to \((d_A d_B-1)/4 \) errors.Algorithms such as generalized minimum-distance decoding [24] or the min-sum algorithm can decode all errors of weight up to \((d_A d_B-1)/2\). Error location may be coupled with Viterbi decoding for every faulty sub-block [191].
Tornado code Linear-time peeling decoder [192]. This decoder either terminates when it has removed a given erasure pattern or when it is stuck in a stopping set.
Torus-layer spherical code (TLSC) Efficiently decodable [193].
Turbo code Turbo decoder [194], an instance of BP decoding [195].Maximum A Posteriori (MAP) decoder [196] and a soft output derivative [197]. The use of soft outputs can improve code performance [198].List decoding [199].VLSI integrated-circuit decoding hardware [200].Autoencoder [201].
Varshamov-Tenengolts (VT) code Decoder based on checksums \(\sum_{i=1}^n i~x_i^{\prime}\) of corrupted codewords \(x_i^{\prime}\) [202,203].
Zetterberg code Kallquist first described an algebraic decoding theorem [204]. A faster version was later provided in Ref. [205] and further modified in Ref. [206].
\([12,6,6]_3\) Extended ternary Golay code Decoder using the tetracode [207].
\([23, 12, 7]\) Golay code The Golay code has a trellis representation and can thus be decoded using trellis decoding [208,209].Bounded-distance decoder requiring at most 121 real operations [210].
\([24, 12, 8]\) Extended Golay code Majority decoding [211].Decoder using the hexacode [207].The extended Golay code has a trellis representation and can thus be decoded using trellis decoding [208,209].
\([2^m -1, 2^m - 1 - 2m, 5]\) Melas code Algebraic decoder [212].
\([2^m,m+1,2^{m-1}]\) First-order RM code First-order RM codes admit specialized decoders, such as the Fast Hadamard Transform decoder [213].Maximum-likelihood decoding is practical via the Green Machine decoder [2; Ch. 14].
\([2^m,m,2^{m-1}]\) Hadamard code Local decoder making one quantum query to the received word [99].
\([2^m-1,m,2^{m-1}]\) simplex code Serial orthogonal decoder [214,215]Quantum decoder [216].
\([2^r-1, 2r ]\) Gold code General decoding is done by building a sparse parity check matrix, followed by applying an iterative message passing algorithm. [217].
\([6,3,4]_4\) Hexacode Bounded-distance decoder requiring at most 34 real operations [210].
\([n,n-1,2]\) Single parity-check (SPC) code If the receiver finds that the parity information of a codeword disagrees with the parity bit, then the receiver will discard the information and request a resend.Wagner’s rule yields a procedure that is linear in \(n\) [218] (see [219; Sec. 29.7.2] for a description).
\(q\)-ary LDPC code Gallager generalized his iterative probabilistic decoding procedure to arbitrary alphabet sizes, with symbol-update rules expressed in terms of modulo-\(q\) check sums [100; Secs. 5.3–5.4].
\(q\)-ary code For small \(n\), decoding can be based on a lookup table. For infinite code families, the size of such a table scales exponentially with \(n\), so approximate decoding algorithms scaling polynomially with \(n\) have to be used. The decoder determining the most likely error given a noise channel is called the maximum-likelihood decoder.Given a received string \(x\) and an error bound \(e\), a list decoder returns a list of all codewords that are at most \(e\) from \(x\). The number of codewords in a neighborhood of \(x\) has to be polynomial in \(n\) in order for this decoder to run in time polynomial in \(n\).
\(q\)-ary repetition code The receiver can use majority vote to recover the information.
\(q\)-ary simplex code Permutation decoder for simplex [220] and MacDonald [221] codes.
List (property_set_in_domain): All codes in Classical Domain with Decoding.

References

  1. [1]

    H. Helgert, “Decoding of alternant codes (Corresp.)”, IEEE Transactions on Information Theory 23, 513 (1977) DOI

  2. [2]

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

  3. [3]

    V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI

  4. [4]

    V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) 28 DOI

  5. [5]

    F. N. Hu, W. Henkel, and M. J. Zhao, “Analog Codes for Gross Error Correction in Signal Transmission”, Advanced Materials Research 341–342, 514 (2011) DOI

  6. [6]

    M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction”, IEEE Transactions on Information Theory 39, 66 (1993) DOI

  7. [7]

    D. Knuth, “Efficient balanced codes”, IEEE Transactions on Information Theory 32, 51 (1986) DOI

  8. [8]

    S. Al-Bassam and B. Bose, “On balanced codes”, IEEE Transactions on Information Theory 36, 406 (1990) DOI

  9. [9]

    K. A. Schouhamer Immink and J. H. Weber, “Very Efficient Balanced Codes”, IEEE Journal on Selected Areas in Communications 28, 188 (2010) DOI

  10. [10]

    W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI

  11. [11]

    S. Arimoto, “Encoding and decoding of p-ary group codes and the correction system”, Information Processing in Japan (in Japanese) 2, 320-325 (1961)

  12. [12]

    R. E. Blahut, Theory and Practice of Error-Control Codes (Addison-Wesley, 1983)

  13. [13]

    J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI

  14. [14]

    E. R. Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968)

  15. [15]

    H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI

  16. [16]

    W. W. Peterson and E. J. Weldon, Error-Correcting Codes (MIT Press, 1972)

  17. [17]

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

  18. [18]

    Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, “A method for solving key equation for decoding goppa codes”, Information and Control 27, 87 (1975) DOI

  19. [19]

    R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI

  20. [20]

    Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S. H. Chen, “Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm”, Journal of information science and engineering 23(1), 127-145 (2007)

  21. [21]

    N. Sourlas, “Spin-glass models as error-correcting codes”, Nature 339, 693 (1989) DOI

  22. [22]

    E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI

  23. [23]

    D. Gorenstein and N. Zierler, “A Class of Error-Correcting Codes in \(p^m \) Symbols”, Journal of the Society for Industrial and Applied Mathematics 9, 207 (1961) DOI

  24. [24]

    G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI

  25. [25]

    A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”, IEEE Transactions on Information Theory 13, 260 (1967) DOI

  26. [26]

    L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)”, IEEE Transactions on Information Theory 20, 284 (1974) DOI

  27. [27]

    A. Barg, Q. R. Gashi, and T. Xu, “Minimum distance and decoding of Coxeter codes”, (2026) arXiv:2607.10774

  28. [28]

    J. Meggitt, “Error correcting codes and their implementation for data transmission systems”, IEEE Transactions on Information Theory 7, 234 (1961) DOI

  29. [29]

    E. Prange, “The use of information sets in decoding cyclic codes”, IEEE Transactions on Information Theory 8, 5 (1962) DOI

  30. [30]

    J. Macwilliams, “Permutation Decoding of Systematic Codes”, Bell System Technical Journal 43, 485 (1964) DOI

  31. [31]

    W. An, M. Medard, and K. R. Duffy, “CRC Codes as Error Correction Codes”, ICC 2021 - IEEE International Conference on Communications 1 (2021) arXiv:2104.13663 DOI

  32. [32]

    A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208

  33. [33]

    M. Blaum, J. Brady, J. Bruck, and Jai Menon, “EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures”, IEEE Transactions on Computers 44, 192 (1995) DOI

  34. [34]

    N. J. Nilsson, Learning Machines (McGraw-Hill, 1965)

  35. [35]

    T. Windeatt and R. Ghaderi, “Coding and decoding strategies for multi-class learning problems”, Information Fusion 4, 11 (2003) DOI

  36. [36]

    O. Pujol, S. Escalera, and P. Radeva, “An incremental node embedding technique for error correcting output codes”, Pattern Recognition 41, 713 (2008) DOI

  37. [37]

    E. L. Allwein, R. E. Schapire, and Y. Singer, “Reducing multiclass to binary: A unifying approach for margin classifiers”, Journal of machine learning research 1, 113-141 (2000)

  38. [38]

    A. Passerini, M. Pontil, and P. Frasconi, “New Results on Error Correcting Output Codes of Kernel Machines”, IEEE Transactions on Neural Networks 15, 45 (2004) DOI

  39. [39]

    J. Justesen, K. J. Larsen, H. E. Jensen, A. Havemose, and T. Hoholdt, “Construction and decoding of a class of algebraic geometry codes”, IEEE Transactions on Information Theory 35, 811 (1989) DOI

  40. [40]

    S. C. Porter, B.-Z. Shen, and R. Pellikaan, “Decoding geometric Goppa codes using an extra place”, IEEE Transactions on Information Theory 38, 1663 (1992) DOI

  41. [41]

    D. Ehrhard, “Decoding Algebraic-Geometric Codes by solving a key equation”, Lecture Notes in Mathematics 18 (1992) DOI

  42. [42]

    R. Pellikaan, “On a decoding algorithm for codes on maximal curves”, IEEE Transactions on Information Theory 35, 1228 (1989) DOI

  43. [43]

    S. Vladut, “On the decoding of algebraic-geometric codes over F/sub q/ for q&amp;lt;or=16”, IEEE Transactions on Information Theory 36, 1461 (1990) DOI

  44. [44]

    S. Sakata, “Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array”, Journal of Symbolic Computation 5, 321 (1988) DOI

  45. [45]

    S. Sakata, “Extension of the Berlekamp-Massey algorithm to N dimensions”, Information and Computation 84, 207 (1990) DOI

  46. [46]

    S. Sakata, “Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm”, IEEE Transactions on Information Theory 37, 1200 (1991) DOI

  47. [47]

    G.-L. Feng and T. R. N. Rao, “Decoding algebraic-geometric codes up to the designed minimum distance”, IEEE Transactions on Information Theory 39, 37 (1993) DOI

  48. [48]

    D. Ehrhard, “Achieving the designed error capacity in decoding algebraic-geometric codes”, IEEE Transactions on Information Theory 39, 743 (1993) DOI

  49. [49]

    M. A. Shokrollahi and H. Wasserman, “List decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 45, 432 (1999) DOI

  50. [50]

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

  51. [51]

    J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright, “LP Decoding Corrects a Constant Fraction of Errors”, IEEE Transactions on Information Theory 53, 82 (2007) DOI

  52. [52]

    M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI

  53. [53]

    X. Chen, K. Cheng, X. Li, and M. Ouyang, “Improved Decoding of Expander Codes”, (2022) arXiv:2111.07629

  54. [54]

    G. M. Nixon and B. J. Brown, “Correcting Spanning Errors With a Fractal Code”, IEEE Transactions on Information Theory 67, 4504 (2021) arXiv:2002.11738 DOI

  55. [55]

    K. R. Duffy, J. Li, and M. Medard, “Capacity-Achieving Guessing Random Additive Noise Decoding”, IEEE Transactions on Information Theory 65, 4023 (2019) arXiv:1802.07010 DOI

  56. [56]

    K. R. Duffy, J. Li, and M. Medard, “Guessing noise, not code-words”, 2018 IEEE International Symposium on Information Theory (ISIT) 671 (2018) DOI

  57. [57]

    V. Guruswami and A. Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy”, (2007) arXiv:cs/0511072

  58. [58]

    A. Rudra, “List Decoding and Property Testing of Error Correcting Codes”, PhD thesis, University of Washington, 2007

  59. [59]

    F. Parvaresh and A. Vardy, “Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 285 DOI

  60. [60]

    V. Guruswami, “Linear-Algebraic List Decoding of Folded Reed-Solomon Codes”, 2011 IEEE 26th Annual Conference on Computational Complexity 77 (2011) arXiv:1106.0436 DOI

  61. [61]

    S. Bhandari, P. Harsha, M. Kumar, and M. Sudan, “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, LIPIcs, Volume 207, APPROX/RANDOM 2021 207, 56:1 (2021) arXiv:2103.07930 DOI

  62. [62]

    V. Guruswami and A. Rudra, “Better Binary List Decodable Codes Via Multilevel Concatenation”, IEEE Transactions on Information Theory 55, 19 (2009) DOI

  63. [63]

    D. Silva and F. R. Kschischang, “Fast encoding and decoding of Gabidulin codes”, 2009 IEEE International Symposium on Information Theory 2858 (2009) arXiv:0901.2483 DOI

  64. [64]

    V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing 843 (2013) DOI

  65. [65]

    V. Guruswami and C. Wang, “Explicit rank-metric codes list-decodable with optimal redundancy”, (2013) arXiv:1311.7084

  66. [66]

    R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI

  67. [67]

    A. Berman, A. Dor, Y. Shany, I. Shapir, and A. Doubchak, “Efficient Hard Decision Decoding of Generalized Reed-Solomon Codes in Presence of Erasures and Errors within the Singleton Bound”, U.S. Patent US11855658B1 (2023)

  68. [68]

    N. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory 21, 203 (1975) DOI

  69. [69]

    D. J. Bernstein, “Understanding binary-Goppa decoding”, Cryptology ePrint Archive (2022)

  70. [70]

    P. Beelen, T. Hoholdt, J. S. R. Nielsen, and Y. Wu, “On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes”, IEEE Transactions on Information Theory 59, 3269 (2013) DOI

  71. [71]

    T. Helleseth and P. V. Kumar, “The algebraic decoding of the Z/sub 4/-linear Goethals code”, IEEE Transactions on Information Theory 41, 2040 (1995) DOI

  72. [72]

    V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI

  73. [73]

    D. Bleichenbacher, A. Kiayias, and M. Yung, “Decoding interleaved Reed–Solomon codes over noisy channels”, Theoretical Computer Science 379, 348 (2007) DOI

  74. [74]

    D. Coppersmith and M. Sudan, “Reconstructing curves in three (and higher) dimensional space from noisy data”, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing 136 (2003) DOI

  75. [75]

    M. Tuchler, “Design of Serially Concatenated Systems Depending on the Block Length”, IEEE Transactions on Communications 52, 209 (2004) DOI

  76. [76]

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

  77. [77]

    J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972) DOI

  78. [78]

    U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Mathematics of Computation 44, 463 (1985) DOI

  79. [79]

    C. P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”, Mathematical Programming 66, 181 (1994) DOI

  80. [80]

    O. Damen, A. Chkeif, and J.-C. Belfiore, “Lattice code decoder for space-time codes”, IEEE Communications Letters 4, 161 (2000) DOI

  81. [81]

    B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I. Expected complexity”, IEEE Transactions on Signal Processing 53, 2806 (2005) DOI

  82. [82]

    E. Viterbo and J. Bouros, “A universal lattice code decoder for fading channels”, IEEE Transactions on Information Theory 45, 1639 (1999) DOI

  83. [83]

    I. Dumer, “Maximum likelihood decoding with reduced complexity”, Proceedings of IEEE International Symposium on Information Theory 396 DOI

  84. [84]

    C. Hartmann and L. Rudolph, “An optimum symbol-by-symbol decoding rule for linear codes”, IEEE Transactions on Information Theory 22, 514 (1976) DOI

  85. [85]

    C. Peters, “Information-Set Decoding for Linear Codes over F q”, Lecture Notes in Computer Science 81 (2010) DOI

  86. [86]

    J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis”, IEEE Transactions on Information Theory 24, 76 (1978) DOI

  87. [87]

    R. Kötter. A unified description of an error locating procedure for linear codes. In D. Yorgov, editor, Proc. 3rd International Workshop on Algebraic and Combinatorial Coding Theory, pages 113–117, Voneshta Voda, Bulgaria, June 1992. Hermes

  88. [88]

    R. Pellikaan, “On decoding by error location and dependent sets of error positions”, Discrete Mathematics 106–107, 369 (1992) DOI

  89. [89]

    E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (Corresp.)”, IEEE Transactions on Information Theory 24, 384 (1978) DOI

  90. [90]

    G. S. Evseev, “Complexity of decoding for linear codes”, Problems of Information Transmission 19(1), 1-6 (1983)

  91. [91]

    D. Slepian, “Some Further Theory of Group Codes”, Bell System Technical Journal 39, 1219 (1960) DOI

  92. [92]

    Y. S. Han, H.-T. Pai, P.-N. Chen, and T.-Y. Wu, “Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes”, (2014) arXiv:1408.1310

  93. [93]

    E. Nachmani, Y. Beery, and D. Burshtein, “Learning to Decode Linear Codes Using Deep Learning”, (2016) arXiv:1607.04793

  94. [94]

    Y. Choukroun and L. Wolf, “Error Correction Code Transformer”, (2022) arXiv:2203.14966

  95. [95]

    D. Chase, “Class of algorithms for decoding block codes with channel measurement information”, IEEE Transactions on Information Theory 18, 170 (1972) DOI

  96. [96]

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

  97. [97]

    S. Liu, F. Manganiello, and F. R. Kschischang, “Construction and decoding of generalized skew-evaluation codes”, 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT) 9 (2015) DOI

  98. [98]

    U. Martinez-Penas and F. R. Kschischang, “Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes”, IEEE Transactions on Information Theory 65, 4785 (2019) arXiv:1805.03789 DOI

  99. [99]

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

  100. [100]

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

  101. [101]

    J. Pearl, “Reverend Bayes on inference engines: A distributed hierarchical approach”, in Probabilistic and Causal Inference: The Works of Judea Pearl (pp. 129–138) (2022)

  102. [102]

    “Probabilistic Reasoning in Intelligent Systems”, (1988) DOI

  103. [103]

    F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm”, IEEE Transactions on Information Theory 47, 498 (2001) DOI

  104. [104]

    T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding”, IEEE Transactions on Information Theory 47, 599 (2001) DOI

  105. [105]

    S. Lin and D. J. Costello, Error Control Coding, 2nd ed. (Prentice-Hall, 2004)

  106. [106]

    K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, and S. Goto, “A parallel LSI architecture for LDPC decoder improving message-passing schedule”, 2006 IEEE International Symposium on Circuits and Systems 4 DOI

  107. [107]

    J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Y. Hu, “Reduced-Complexity Decoding of LDPC Codes”, IEEE Transactions on Communications 53, 1288 (2005) DOI

  108. [108]

    J. Feldman, “Decoding Error-Correcting Codes via Linear Programming”, PhD thesis, Massachusetts Institute of Technology, 2003

  109. [109]

    J. Feldman, M. J. Wainwright, and D. R. Karger, “Using Linear Programming to Decode Binary Linear Codes”, IEEE Transactions on Information Theory 51, 954 (2005) DOI

  110. [110]

    J. Feldman, “LP Decoding”, Encyclopedia of Algorithms 1177 (2016) DOI

  111. [111]

    V. C. Gaudet and A. C. Rapley, “Iterative decoding using stochastic computation”, Electronics Letters 39, 299 (2003) DOI

  112. [112]

    Changyan Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check codes on the binary erasure channel”, IEEE Transactions on Information Theory 48, 1570 (2002) DOI

  113. [113]

    C. A. Kelley, “Codes over Graphs”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 527-552 DOI

  114. [114]

    M. Schwartz and A. Vardy, “On the stopping distance and the stopping redundancy of codes”, IEEE Transactions on Information Theory 52, 922 (2006) DOI

  115. [115]

    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

  116. [116]

    S. Habib, A. Beemer, and J. Kliewer, “RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codes”, (2023) arXiv:2112.13934

  117. [117]

    S. M. Perez-Garcia and A. Montanaro, “Quantum-enhanced belief propagation for LDPC decoding”, (2024) arXiv:2412.08596

  118. [118]

    P. Gaborit, G. Murat, O. Ruatta, and G. Zemor, “Low rank parity check codes and their application to cryptography”, in Proceedings of the Workshop on Coding and Cryptography WCC (2013)

  119. [119]

    P. Gaborit, O. Ruatta, J. Schrek, and G. Zémor, “RankSign: An Efficient Signature Algorithm Based on the Rank Metric”, Lecture Notes in Computer Science 88 (2014) DOI

  120. [120]

    T. Richardson and R. Urbanke, Modern Coding Theory (Cambridge University Press, 2008) DOI

  121. [121]

    D. J. C. MacKay, Information Theory, Inference and Learning Algorithms (Cambridge University Press, 2002)

  122. [122]

    J. Pearl, “Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach”, Probabilistic and Causal Inference 129 (2022) DOI

  123. [123]

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

  124. [124]

    F. Hernando, K. Lally, and D. Ruano, “Construction and decoding of matrix-product codes from nested codes”, Applicable Algebra in Engineering, Communication and Computing 20, 497 (2009) DOI

  125. [125]

    S. Kopparty, Theory of Computing 11, 149 (2015) DOI

  126. [126]

    S. Bhandari, P. Harsha, M. Kumar, and M. Sudan, “Decoding multivariate multiplicity codes on product sets”, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 1489 (2021) arXiv:2012.01530 DOI

  127. [127]

    R. R. Nielsen, “List decoding of linear block codes”, PhD thesis, Technical University of Denmark, 2001

  128. [128]

    V. Guruswami and C. Wang, “Optimal rate list decoding via derivative codes”, (2011) arXiv:1106.3951

  129. [129]

    D. R. Chowdhury, S. Basu, I. S. Gupta, and P. P. Chaudhuri, “Design of CAECC - cellular automata based error correcting code”, IEEE Transactions on Computers 43, 759 (1994) DOI

  130. [130]

    V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block coding for wireless communications: performance results”, IEEE Journal on Selected Areas in Communications 17, 451 (1999) DOI

  131. [131]

    A. N. Skorobogatov and S. G. Vladut, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 36, 1051 (1990) DOI

  132. [132]

    V. Yu. Krachkovsky, (1988) “Decoding of codes on algebraic curves”, Proceedings of the IX All-Union Conference on the Theory of Coding and Information Transmission, Moscow-Odessa: USSR Academy of Sciences, 1988 Part 2, pp. 143–146

  133. [133]

    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

  134. [134]

    I. Tal and A. Vardy, “List Decoding of Polar Codes”, IEEE Transactions on Information Theory 61, 2213 (2015) DOI

  135. [135]

    Y. Ren, A. T. Kristensen, Y. Shen, A. Balatsoukas-Stimming, C. Zhang, and A. Burg, “A Sequence Repetition Node-Based Successive Cancellation List Decoder for 5G Polar Codes: Algorithm and Implementation”, IEEE Transactions on Signal Processing 70, 5592 (2022) arXiv:2205.08857 DOI

  136. [136]

    U. U. Fayyaz and J. R. Barry, “Low-Complexity Soft-Output Decoding of Polar Codes”, IEEE Journal on Selected Areas in Communications 32, 958 (2014) DOI

  137. [137]

    U. U. Fayyaz and J. R. Barry, “Polar codes for partial response channels”, 2013 IEEE International Conference on Communications (ICC) 4337 (2013) DOI

  138. [138]

    E. Arkan, “A performance comparison of polar codes and Reed-Muller codes”, IEEE Communications Letters 12, 447 (2008) DOI

  139. [139]

    S. Kasi, J. Kaewell, S. Hamidi-Rad, and K. Jamieson, “Decoding Polar Codes via Noisy Quantum Gates: Quantum Circuits and Insights”, (2022) arXiv:2210.10854

  140. [140]

    D. J. Bernstein, T. Lange, and C. Peters, “Smaller Decoding Exponents: Ball-Collision Decoding”, Lecture Notes in Computer Science 743 (2011) DOI

  141. [141]

    A. Becker, A. Joux, A. May, and A. Meurer, “Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding”, Lecture Notes in Computer Science 520 (2012) DOI

  142. [142]

    M. Finiasz and N. Sendrier, “Security Bounds for the Design of Code-Based Cryptosystems”, Lecture Notes in Computer Science 88 (2009) DOI

  143. [143]

    P. Loidreau, “A Welch–Berlekamp Like Algorithm for Decoding Gabidulin Codes”, Lecture Notes in Computer Science 36 (2006) DOI

  144. [144]

    G. Richter and S. Plass, “Fast decoding of rank-codes with rank errors and column erasures”, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings. 398 DOI

  145. [145]

    F. Lazaro, G. Liva, and G. Bauch, “Inactivation Decoding of LT and Raptor Codes: Analysis and Code Design”, IEEE Transactions on Communications 1 (2017) arXiv:1706.05814 DOI

  146. [146]

    D. E. Muller, “Application of Boolean algebra to switching circuit design and to error detection”, Transactions of the I.R.E. Professional Group on Electronic Computers EC-3, 6 (1954) DOI

  147. [147]

    L. Rudolph and C. Hartmann, “Decoding by sequential code reduction”, IEEE Transactions on Information Theory 19, 549 (1973) DOI

  148. [148]

    G. Seroussi and A. Lempel, “Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields”, SIAM Journal on Computing 9, 758 (1980) DOI

  149. [149]

    E. T. Campbell and M. Howard, “Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost”, Physical Review A 95, (2017) arXiv:1606.01904 DOI

  150. [150]

    V. Guruswami and A. Vardy, “Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard”, (2004) arXiv:cs/0405005

  151. [151]

    E. R. Berlekamp and L. Welch, “Error Correction of Algebraic Block Codes”, U.S. Patent 4,633,470 (1986)

  152. [152]

    P. Gemmell and M. Sudan, “Highly resilient correctors for polynomials”, Information Processing Letters 43, 169 (1992) DOI

  153. [153]

    D. V. Sarwate and Z. Yan, “Modified Euclidean Algorithms for Decoding Reed-Solomon Codes”, (2009) arXiv:0906.3778

  154. [154]

    S. Gao, “A New Algorithm for Decoding Reed-Solomon Codes”, Communications, Information and Network Security 55 (2003) DOI

  155. [155]

    I. Reed, R. Scholtz, Treiu-Kien Truong, and L. Welch, “The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions”, IEEE Transactions on Information Theory 24, 100 (1978) DOI

  156. [156]

    M. Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13, 180 (1997) DOI

  157. [157]

    R. M. Roth and G. Ruckenstein, “Efficient decoding of Reed-Solomon codes beyond half the minimum distance”, IEEE Transactions on Information Theory 46, 246 (2000) DOI

  158. [158]

    V. Guruswami and A. Rudra, “Limits to List Decoding Reed–Solomon Codes”, IEEE Transactions on Information Theory 52, 3642 (2006) DOI

  159. [159]

    J. Brakensiek, Y. Chen, A. Putterman, Z. Zhang, and K. Z. Zheng, “Algorithmic List Decoding of Reed-Solomon Codes up to Capacity”, (2026) arXiv:2609.08005

  160. [160]

    F. G. Jeronimo, “Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes”, (2026) arXiv:2609.05870

  161. [161]

    A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI

  162. [162]

    A. Berman, Y. Shany, and I. Tamo, “Explicit Subcodes of Reed-Solomon Codes that Efficiently Achieve List Decoding Capacity”, (2024) arXiv:2401.15034

  163. [163]

    M. Naor and B. Pinkas, “Oblivious transfer and polynomial evaluation”, Proceedings of the thirty-first annual ACM symposium on Theory of Computing 245 (1999) DOI

  164. [164]

    D. V. Sarwate and N. R. Shanbhag, “High-speed architectures for Reed-Solomon decoders”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 9, 641 (2001) DOI

  165. [165]

    S. B. Wicker and V. K. Bhargava, “Reed-Solomon Codes and Their Applications”, (1999) DOI

  166. [166]

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

  167. [167]

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

  168. [168]

    A. Barg and G. Zemor, “Concatenated Codes: Serial and Parallel”, IEEE Transactions on Information Theory 51, 1625 (2005) DOI

  169. [169]

    A. L. Toom, “Nonergodic Multidimensional System of Automata”, Problemy Peredachi Informatsii 10(3), 70–79 (1974); Problems of Information Transmission 10(3), 239–246 (1974)

  170. [170]

    A. L. Toom, “Stable and attractive trajectories in multicomponent systems”, Multicomponent random systems 6, 549-575 (1980)

  171. [171]

    L. F. Gray, “Toom’s Stability Theorem in Continuous Time”, Perplexing Problems in Probability 331 (1999) DOI

  172. [172]

    G. Grinstein, “Can complex structures be generically stable in a noisy world?”, IBM Journal of Research and Development 48, 5 (2004) DOI

  173. [173]

    P. Gács, “Reliable computation with cellular automata”, Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC ’83 32 (1983) DOI

  174. [174]

    P. Gács, “Reliable computation with cellular automata”, Journal of Computer and System Sciences 32, 15 (1986) DOI

  175. [175]

    P. Gács, “Self-Correcting Two-Dimensional Arrays”, Advances in Computing Research 5, 223-326 (1989)

  176. [176]

    P. Gács, “Reliable Cellular Automata with Self-Organization”, Journal of Statistical Physics 103, 45 (2001) arXiv:math/0003117 DOI

  177. [177]

    B. S. Cirel’son, “Reliable storage of information in a system of unreliable components with local interactions”, Lecture Notes in Mathematics 15 (1978) DOI

  178. [178]

    M. Park, N. Maskara, M. Kalinowski, and M. D. Lukin, “Enhancing quantum memory lifetime with measurement-free local error correction and reinforcement learning”, Physical Review A 111, (2025) arXiv:2408.09524 DOI

  179. [179]

    F. G. Jeronimo, D. Quintana, S. Srivastava, and M. Tulsiani, “Unique Decoding of Explicit \(ε\)-balanced Codes Near the Gilbert-Varshamov Bound”, (2020) arXiv:2011.05500

  180. [180]

    I. Tamo and A. Barg, “A Family of Optimal Locally Recoverable Codes”, IEEE Transactions on Information Theory 60, 4661 (2014) arXiv:1311.3284 DOI

  181. [181]

    N. Wiberg, H. Loeliger, and R. Kotter, “Codes and iterative decoding on general graphs”, European Transactions on Telecommunications 6, 513 (1995) DOI

  182. [182]

    N. Wiberg, “Codes and decoding on general graphs”, PhD thesis, Linköping University, 1996

  183. [183]

    B. J. Frey, Graphical models for machine learning and digital communication (MIT Press, 1998)

  184. [184]

    Yongyi Mao and A. H. Banihashemi, “Decoding low-density parity-check codes with probabilistic schedule”, 2001 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (IEEE Cat. No.01CH37233) 1, 119 DOI

  185. [185]

    G. D. Forney, “Codes on graphs: normal realizations”, 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060) 9 DOI

  186. [186]

    E. Soljanin and E. Offer, “LDPC codes: a group algebra formulation”, Electronic Notes in Discrete Mathematics 6, 148 (2001) DOI

  187. [187]

    T. Etzion, A. Trachtenberg, and A. Vardy, “Which codes have cycle-free Tanner graphs?”, IEEE Transactions on Information Theory 45, 2173 (1999) DOI

  188. [188]

    R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981) DOI

  189. [189]

    D. K. Kythe and P. K. Kythe, “Algebraic and Stochastic Coding Theory”, (2017) DOI

  190. [190]

    S. M. Bellovin, “Compression, correction, confidentiality, and comprehension: a modern look at telegraph codebooks”, Cryptologia 50, 374 (2025) DOI

  191. [191]

    P. Chaichanavong and P. H. Siegel, “Tensor-product parity code for magnetic recording”, IEEE Transactions on Magnetics 42, 350 (2006) DOI

  192. [192]

    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

  193. [193]

    C. Torezzan, S. I. R. Costa, and V. A. Vaishampayan, “Spherical codes on torus layers”, 2009 IEEE International Symposium on Information Theory 2033 (2009) DOI

  194. [194]

    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

  195. [195]

    R. J. McEliece, D. J. C. MacKay, and Jung-Fu Cheng, “Turbo decoding as an instance of Pearl’s “belief propagation” algorithm”, IEEE Journal on Selected Areas in Communications 16, 140 (1998) DOI

  196. [196]

    H. R. Sadjadpour, “&lt;title&gt;Maximum a posteriori decoding algorithms for turbo codes&lt;/title&gt;”, SPIE Proceedings 4045, 73 (2000) DOI

  197. [197]

    J. D. Kene and K. D. Kulat, “Soft Output Decoding Algorithm for Turbo Codes Implementation in Mobile Wi-Max Environment”, Procedia Technology 6, 666 (2012) DOI

  198. [198]

    B. Sklar, “A primer on turbo code concepts”, IEEE Communications Magazine 35, 94 (1997) DOI

  199. [199]

    K. R. Narayanan and G. L. Stuber, “List decoding of turbo codes”, IEEE Transactions on Communications 46, 754 (1998) DOI

  200. [200]

    G. Masera, G. Piccinini, M. R. Roch, and M. Zamboni, “VLSI architectures for turbo codes”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 7, 369 (1999) DOI

  201. [201]

    E. Balevi and J. G. Andrews, “Autoencoder-Based Error Correction Coding for One-Bit Quantization”, (2019) arXiv:1909.12120

  202. [202]

    V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals” (translated to English), Soviet Physics Doklady 10(8), 707-710 (1966)

  203. [203]

    V. I. Levenshtein, “Binary codes capable of correcting spurious insertions and deletions of one” (translated to English), Problems of Information Transmission 1(1), 8-17 (1965)

  204. [204]

    P. Kallquist, “Decoding of Zetterberg codes”, in Proc. Fourth Joint Swedish-Soviet Workshop on Inform. Theory, Gotland, Sweden, Aug. 27-Sept. 1, 1989, p. 305-300

  205. [205]

    S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992) DOI

  206. [206]

    M.-H. Jing, Y. Chang, C.-D. Lee, J.-H. Chen, and Z.-H. Chen, “A Result on Zetterberg Codes”, IEEE Communications Letters 14, 662 (2010) DOI

  207. [207]

    V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986) DOI

  208. [208]

    A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009) DOI

  209. [209]

    B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993) DOI

  210. [210]

    A. Vardy, “Even more efficient bounded-distance decoding of the hexacode, the Golay code, and the Leech lattice”, IEEE Transactions on Information Theory 41, 1495 (1995) DOI

  211. [211]

    J.-M. Goethals, “On the Golay perfect binary code”, Journal of Combinatorial Theory, Series A 11, 178 (1971) DOI

  212. [212]

    A. Alahmadi, H. Alhazmi, T. Helleseth, R. Hijazi, N. Muthana, and P. Solé, “On the lifted Melas code”, Cryptography and Communications 8, 7 (2015) DOI

  213. [213]

    E. C. Posner, “Combinatorial Structures in Planetary Reconnaissance”, in Error Correcting Codes, ed. H. B. Mann, Wiley, NY 1968

  214. [214]

    R. R. Green, “A serial orthogonal decoder”, JPL Space Programs Summary, vol. 37–39-IV, pp. 247–253, 1966

  215. [215]

    A. Ashikhmin and S. Litsyn, “Simple MAP decoding of first order Reed-Muller and Hamming codes”, Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674) 18 DOI

  216. [216]

    A. M. Barg and S. Zhou, “A quantum decoding algorithm for the simplex code”, in Proceedings of the 36th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, 23–25 September 1998 (UIUC 1998) 359–365

  217. [217]

    O. W. Yeung and K. M. Chugg, “An Iterative Algorithm and Low Complexity Hardware Architecture for Fast Acquisition of Long PN Codes in UWB Systems”, Journal of VLSI signal processing systems for signal, image and video technology 43, 25 (2006) DOI

  218. [218]

    R. Silverman and M. Balser, “Coding for constant-data-rate systems”, Transactions of the IRE Professional Group on Information Theory 4, 50 (1954) DOI

  219. [219]

    A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI

  220. [220]

    W. Fish, J. D. Key, and E. Mwambene, “Partial permutation decoding for simplex codes”, Advances in Mathematics of Communications 6, 505 (2012) DOI

  221. [221]

    J. D. Key and P. Seneviratne, “Partial permutation decoding for MacDonald codes”, Applicable Algebra in Engineering, Communication and Computing 27, 399 (2016) DOI

Classical Domain

  • Binary Kingdom
  • Galois-field Kingdom
  • Matrix Kingdom
  • Analog Kingdom
  • Spherical Kingdom
  • Ring Kingdom
  • Group Kingdom
  • Homogeneous-space Kingdom

Quantum Domain

  • Qubit Kingdom
  • Modular-qudit Kingdom
  • Galois-qudit Kingdom
  • Bosonic Kingdom
  • Spin Kingdom
  • Group quantum Kingdom
  • Homogeneous-space quantum Kingdom
  • Category Kingdom

Classical-quantum Domain

  • Binary c-q Kingdom
  • Analog c-q Kingdom

  • Home
  • Code graph
  • Code lists
  • Concepts glossary
  • Handbook
  • Search

  • Team
  • About

  • 🌒
≡
Error correction zoo by Victor V. Albert, Philippe Faist, and many contributors. This work is licensed under a CC-BY-SA License. See how to contribute.