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

Name | Decoder(s) |
---|---|

Alternant code | Variation of the Berlekamp-Welch algorithm [1].Guruswami-Sudan list decoder [2,3]. |

B-code | Efficient decoding algorithm against erasures [4]. |

Balanced code | Efficient decoder [5–7]. |

Binary BCH code | Peterson decoder with runtime of order \(O(n^3)\) [8,9] (see exposition in Ref. [10]).Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [11,12] and modification by Burton [13]; see also [14,15].Sugiyama et al. modification of the extended Euclidean algorithm [16,17].Guruswami-Sudan list decoder [2,3]. |

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\). |

Bose–Chaudhuri–Hocquenghem (BCH) code | Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [11,12,18] and modification by Burton [13]; see also [14,15].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [8,19] (see exposition in Ref. [10]).Sugiyama et al. modification of the extended Euclidean algorithm [16,17].Guruswami-Sudan list decoder [2,3] and modification by Koetter-Vardy for soft-decision decoding [20]. |

Classical Goppa code | Algebraic decoding algorithms [21]. If \( \text{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 [16,17].Guruswami-Sudan list decoder [2,3].Binary Goppa codes can be decoded using a RS-based decoder [22]. |

Cyclic linear \(q\)-ary code | Meggitt decoder [23].Information set decoding (ISD) [24], 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.Permutation decoding [25]. |

Cyclic linear binary code | Meggitt decoder [23].Information set decoding (ISD) [24], 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.Permutation decoding [25]. |

Delsarte-Goethals (DG) code | Since the equivalent \(\mathbb{Z_4}\) codes are extended cyclic codes, efficient encoding and decoding is possible [26]. |

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\}\). |

Evaluation AG code | Generalization of plane-curve decoder [27,28]. Another decoder [29] was later showed to be equivalent in Ref. [30]. Application of several algorthims in parallel can be used to decode up to half the minimum distance [31,32]. Computational procedure implementing these decoders is based on an extension of the Berlekamp-Massey algorithm by Sakata [33–35].Decoder based on majority voting of unknown syndromes [36] decodes up to half of the minimum distance [37].List decoders generalizing Sudan's RS decoder by Shokrollahi-Wasserman [38] and Guruswami-Sudan [3]. |

Expander code | Decoding can be done in \(O(n)\) runtime using a greedy flip decoder [39] (see also [40]). 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.'Find erasures and Decode' a.k.a. Viderman's alogrithm correcting \(\Omega(n)\) in order \(O(n)\) time [41]. |

Fibonacci code | An efficient algorithm base on minimum-weight perfect matching [42], which can correct high-weight errors that span rows and columns of the 2D lattice, with failure rate decaying super-exponentially with \(L\). |

Folded RS (FRS) code | Guruswami and Rudra [43,44] achieved list-decoding up to \(1-\frac{k}{n}-\epsilon\) fraction of errors using the Parvaresh-Vardy algorithm [45]; see Ref. [46] for a randomized construction.List-decoding works up to the Johnson bound using the Guruswami-Sudan algorithm [47].Folded RS codes, concatenated with suitable inner codes, can be efficiently list-decoded up to the Blokh-Zyablov bound [43,48]. |

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 [49].Algebraic list decoder that decodes up to the Singleton bound [50]. |

Galois-field \(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\). |

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)\) [11,12,18].Guruswami-Sudan list decoder [2,3] and modification by Koetter-Vardy for soft-decision decoding [20].Hard-decision decoder for errors within the Singleton bound [51]. |

Golay code | Majority decoding for the extended Golay code [52].Decoder for the extended Golay code using the hexacode [53].Both Golay codes have a trellis representation and can thus be decoded using trellis decoding [54,55].Bounded-distance decoder requiring at most 121 real operations [56]. |

Gold code | General decoding is done by building a sparse parity check matrix, followed by applying an iterative message passing alogirithm. [57]. |

Hergert code | Since the equivalent \(\mathbb{Z_4}\) codes are extended cyclic codes, efficient encoding-decoding is possible. [26,58]. |

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 Reed-Solomon 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 [33]. |

Hexacode | Bounded-distance decoder requiring at most 34 real operations [56]. |

Interleaved RS (IRS) code | Decoder that corrects up to \(1-\frac{2k+n}{3n}\) fraction of random errors [59].Decoder that corrects up to \(1-(\frac{k}{n})^{2/3}\) fraction of random errors [60]. |

Irregular repeat-accumulate (IRA) code | Linear-time decoder [61]. |

Justesen code | Generalized minimum distance decoding [62]. |

Kerdock code | Soft decision decoding involves extending the Fast Hadamard Transform decoding algorithm for the first-order RM code to Kerdock code [26].Complexity of soft decision decoding algorithm: \(4^m\) multiplications and \(m4^m\) additions [26,63]. |

Linear STC | Sphere decoder [64–66]. |

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 [67].Optimal symbol-by-symbol decoding rule [68].Information set decoding (ISD) [69], 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 [70].Soft-decision maximum-likelihood trellis-based decoder [71].Random linear codes over large fields are list-recoverable and list-decodable up to near-optimal rates [72].Extensions of algebraic-geometry decoders to linear codes [73,74]. |

Linear binary code | Decoding an arbitary linear binary code is \(NP\)-complete [75].Slepian's standard-array decoding [76].Recursive maximum likelihood decoding [77].Transformer neural net for soft decoding [78].Chase decoding, which uses channel measurement information [79]. |

Low-density parity-check (LDPC) code | Message-passing algorithm called belief propagation (BP) [80–82] (see also [83–85]).Soft-decision Sum-Product Algorithm (SPA) [80,83,86] and its simplification the Min-Sum Algorithm (MSA) [87].Linear programming [88–90].Iterative LDPC decoders can get stuck at stopping sets of their Tanner graphs [91], with decoder performance improving with the size of the smallest stopping set; see [92; Sec. 21.3.1] for more details. The smallest stopping set size can reach the minimum distance of the code [93].Ensembles of random LDPC codes under iterative decoders are subject to the concentration theorem [83,94]; see [92; Thm. 21.7.1] for the case of the BEC.Reinforcement learning [95]. |

Low-rank parity-check (LRPC) code | Efficient probabilistic decoder [96].Mixed decoder [97]. |

Luby transform (LT) code | Sum-Product Algorithm (SPA), often called a peeling decoder [98,99], similar to belief propagation [100]. |

MacKay-Neal LDPC (MN-LDPC) code | Free-energy minimization and a BP decoder [101]. |

Matrix-product code | Decoder up to half of the minimum distance for NSC codes [102]. |

Melas code | Algebraic decoder [103]. |

Multiplicity code | Multivariate multiplicity codes can be decoded up to half of the minimum distance in polynomial time [104,105].Univariate [106] and multivariate [104] 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 [104,107]. |

Newman-Moore code | Efficient decoder [108]. |

Orthogonal Spacetime Block Code (OSTBC) | Maximum-likelihood decoding can be achieved with only linear processing [109]. |

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 code | Generalization of the Peterson algorithm for BCH codes [110]. |

Polar code | Successive cancellation (SC) decoder [111].Successive cancellation list (SCL) decoder [112] and a modification utilizing sequence repetition (SR-List) [113].Soft cancellation (SCAN) decoder [114,115].Belief propagation (BP) decoder [116].Noisy quantum gate-vased decoder [117]. |

Preparata code | Preparata Codes can be decoded using a syndrome calculation based algorithm to correct all error patterns of Lee weight atmost 2 and detect all/ some error patterns of Lee weight 3/ 4 [26,63]. |

Rank-metric code | Polynomial-reconstruction Berlekamp-Welch based decoder [118].Berlekamp-Massey based decoder [119]. |

Raptor (RAPid TORnado) code | Raptor codes can be decoded using inactivation decoding [120], a combination of belief-propogation 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 [121] (see also Ch. 13 of Ref. [122]).Sequential code-reduction decoding [123].Matrix factorization is equivalent to decoding an RM\((n,n-3)\) code [124]; see [125]. |

Reed-Solomon (RS) code | Decoding general RS codes is \(NP\)-hard [126].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)\) [11,12].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [8,19] (see exposition in Ref. [10]).Berlekamp-Welch decoder with runtime of order \(O(n^3)\) [127] (see exposition in Ref. [128]), assuming that \(t \geq (n+k)/2\).Gao decoder using extended Euclidean algorithm [129].Fast-Fourier-transform decoder with runtime of order \(O(n \text{polylog}n)\) [130].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 homogenous linear equation (interpolation). Once this is done, one lists roots of \(y\) that agree at \(\geq t\) points. The breakthrough Sudan list-decoding algorithm corrects up to \(1-\sqrt{2R}\) fraction of errors [131]. Roth and Ruckenstein proposed a modified key equation that allows for correction of more than \(\left\lfloor (n-k)/2 \right\rfloor\) errors [132]. The Guruswami-Sudan algorithm improved the Sudan algorithm to \(1-\sqrt{R}\) [3], meaning that RS codes achieve list-decoding capacity; see Ref. [133] for bounds. It was later shown that generic Reed-Solomon codes achieve list-decoding capacity [134]. A modification of the Guruswami-Sudan algorithm by Koetter and Vardy is used for soft-decision decoding [20] (see also Ref. [135]). Subcodes of RS codes whose evaluation points lie in a subfield can be decoded up to the \(1-R\) [50].The ubiquity of RS codes has yielded off-the-shelf VLSI intergrated-circuit decoding hardware [136] (see also Ref. [137], Ch. 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 binary Tanner code | Parallel decoding algorithm corrects a fraction \(\delta_0^2/48\) of errors for Tanner codes [39]. A modification of said algorithm improves the fraction to \(\delta_0^2/4\) with no extra cost to complexity [138]. |

Repetition code | Calculate the Hamming weight \(d_H\) of the code. 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.Automaton-like decoders for the repetition code on a 2D lattice, otherwise known as the classical 2D Ising model, were developed by Toom [139,140]. An automaton by Gacs yields a decoder for a 1D lattice [141]. |

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\) [142] (see [143; Sec. 29.7.2] for a description). |

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 that it is located upon reception. |

Ta-Shma zigzag code | Unique and list decoders [144]. |

Tamo-Barg code | Polynomial evaluation over \(r\) points [145]. |

Tanner code | Min-sum and sum-product iterative decoders for binary Tanner codes [146,147]; see also [17,148]. These decoders can be improved using a probabilistic message-passing schedule [149].Any code can be put into normal form without significantly altering the underlying graph or the decoding complexity [150]. For an algebraic viewpoint on decoding, see [151].Iterative decoding is optimal for Tanner graphs that are free of cycles [147]. However, codes that admit cycle-free representations have bounds on their distances [152,153]; see [92,154]. |

Tensor-product code | The simple decoding algorithm (first decode all columns with \(C_1\), then all rows with \(C_2\)) corrects up to \((d_A d_B-1)/4 \) errors.Algorithms such as generalized minimum-distance decoding [70] 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 [155]. |

Ternary Golay code | Decoder for the extended ternary Golay code using the tetracode [53]. |

Tornado code | Linear-time peeling decoder [156]. 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 [157]. |

Varshamov-Tenengolts (VT) code | Decoder based on checksums \(\sum_{i=1}^n i~x_i^{\prime}\) of corrupted codewords \(x_i^{\prime}\) [158,159]. |

Zetterberg code | Kallquist first described an algebraic decoding theorem [160]. A faster version was later provided in Ref. [161] and further modified in Ref. [162]. |

\([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 [163]. |

\([2^m-1,m,2^{m-1}]\) simplex code | Serial orthogonal decoder [164,165]Quantum decoder [166]. |

\(q\)-ary simplex code | Permutation decoder [167] and MacDonald [168] codes. |

## References

- [1]
- H. Helgert, “Decoding of alternant codes (Corresp.)”, IEEE Transactions on Information Theory 23, 513 (1977) DOI
- [2]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI
- [3]
- 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) DOI
- [4]
- M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction”, IEEE Transactions on Information Theory 39, 66 (1993) DOI
- [5]
- D. Knuth, “Efficient balanced codes”, IEEE Transactions on Information Theory 32, 51 (1986) DOI
- [6]
- S. Al-Bassam and B. Bose, “On balanced codes”, IEEE Transactions on Information Theory 36, 406 (1990) DOI
- [7]
- K. A. Schouhamer Immink and J. H. Weber, “Very Efficient Balanced Codes”, IEEE Journal on Selected Areas in Communications 28, 188 (2010) DOI
- [8]
- W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [9]
- S. Arimoto, "Encoding and decoding of p-ary group codes and the correction system," Information Processing in Japan (in Japanese), vol. 2, pp. 320-325, Nov. 1961.
- [10]
- R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
- [11]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [12]
- E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
- [13]
- H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
- [14]
- W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
- [15]
- R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [16]
- Y. Sugiyama et al., “A method for solving key equation for decoding goppa codes”, Information and Control 27, 87 (1975) DOI
- [17]
- R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
- [18]
- E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
- [19]
- 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
- [20]
- R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
- [21]
- N. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory 21, 203 (1975) DOI
- [22]
- Daniel J. Bernstein, "Understanding binary-Goppa decoding." Cryptology ePrint Archive (2022).
- [23]
- J. Meggitt, “Error correcting codes and their implementation for data transmission systems”, IEEE Transactions on Information Theory 7, 234 (1961) DOI
- [24]
- E. Prange, “The use of information sets in decoding cyclic codes”, IEEE Transactions on Information Theory 8, 5 (1962) DOI
- [25]
- J. Macwilliams, “Permutation Decoding of Systematic Codes”, Bell System Technical Journal 43, 485 (1964) DOI
- [26]
- A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
- [27]
- A. N. Skorobogatov and S. G. Vladut, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 36, 1051 (1990) DOI
- [28]
- V. Yu. Krachkovskii, "Decoding of codes on algebraic curves," (in Russian), Conference Odessa, 1988.
- [29]
- 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
- [30]
- D. Ehrhard, “Decoding Algebraic-Geometric Codes by solving a key equation”, Lecture Notes in Mathematics 18 (1992) DOI
- [31]
- R. Pellikaan, “On a decoding algorithm for codes on maximal curves”, IEEE Transactions on Information Theory 35, 1228 (1989) DOI
- [32]
- S. Vladut, “On the decoding of algebraic-geometric codes over F/sub q/ for q&lt;or=16”, IEEE Transactions on Information Theory 36, 1461 (1990) DOI
- [33]
- 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
- [34]
- S. Sakata, “Extension of the Berlekamp-Massey algorithm to N dimensions”, Information and Computation 84, 207 (1990) DOI
- [35]
- S. Sakata, “Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm”, IEEE Transactions on Information Theory 37, 1200 (1991) DOI
- [36]
- 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
- [37]
- D. Ehrhard, “Achieving the designed error capacity in decoding algebraic-geometric codes”, IEEE Transactions on Information Theory 39, 743 (1993) DOI
- [38]
- M. A. Shokrollahi and H. Wasserman, “List decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 45, 432 (1999) DOI
- [39]
- M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI
- [40]
- J. Feldman et al., “LP Decoding Corrects a Constant Fraction of Errors”, IEEE Transactions on Information Theory 53, 82 (2007) DOI
- [41]
- M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI
- [42]
- 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
- [43]
- V. Guruswami and A. Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy”, (2007) arXiv:cs/0511072
- [44]
- Atri Rudra. List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington, 8 2007.
- [45]
- 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) DOI
- [46]
- V. Guruswami, “Linear-Algebraic List Decoding of Folded Reed-Solomon Codes”, 2011 IEEE 26th Annual Conference on Computational Complexity (2011) arXiv:1106.0436 DOI
- [47]
- S. Bhandari et al., “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, (2021) arXiv:2103.07930 DOI
- [48]
- V. Guruswami and A. Rudra, “Better Binary List Decodable Codes Via Multilevel Concatenation”, IEEE Transactions on Information Theory 55, 19 (2009) DOI
- [49]
- D. Silva and F. R. Kschischang, “Fast encoding and decoding of Gabidulin codes”, 2009 IEEE International Symposium on Information Theory (2009) arXiv:0901.2483 DOI
- [50]
- 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 (2013) DOI
- [51]
- Berman, A., Dor, A., Shany, Y., Shapir, I., and Doubchak, A. (2023). U.S. Patent No. 11,855,658. Washington, DC: U.S. Patent and Trademark Office.
- [52]
- J.-M. Goethals, “On the Golay perfect binary code”, Journal of Combinatorial Theory, Series A 11, 178 (1971) DOI
- [53]
- V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986) DOI
- [54]
- A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009) DOI
- [55]
- B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993) DOI
- [56]
- 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
- [57]
- 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
- [58]
- 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
- [59]
- D. Bleichenbacher, A. Kiayias, and M. Yung, “Decoding interleaved Reed–Solomon codes over noisy channels”, Theoretical Computer Science 379, 348 (2007) DOI
- [60]
- 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 (2003) DOI
- [61]
- Jin, Hui, Aamod Khandekar, and Robert McEliece. "Irregular repeat-accumulate codes." Proc. 2nd Int. Symp. Turbo codes and related topics. 2000.
- [62]
- J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972) DOI
- [63]
- A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
- [64]
- O. Damen, A. Chkeif, and J.-C. Belfiore, “Lattice code decoder for space-time codes”, IEEE Communications Letters 4, 161 (2000) DOI
- [65]
- B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I. Expected complexity”, IEEE Transactions on Signal Processing 53, 2806 (2005) DOI
- [66]
- E. Viterbo and J. Bouros, “A universal lattice code decoder for fading channels”, IEEE Transactions on Information Theory 45, 1639 (1999) DOI
- [67]
- I. Dumer, “Maximum likelihood decoding with reduced complexity”, Proceedings of IEEE International Symposium on Information Theory DOI
- [68]
- C. Hartmann and L. Rudolph, “An optimum symbol-by-symbol decoding rule for linear codes”, IEEE Transactions on Information Theory 22, 514 (1976) DOI
- [69]
- C. Peters, “Information-Set Decoding for Linear Codes over F q”, Post-Quantum Cryptography 81 (2010) DOI
- [70]
- G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI
- [71]
- J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis”, IEEE Transactions on Information Theory 24, 76 (1978) DOI
- [72]
- A. Rudra and M. Wootters, “Average-radius list-recovery of random linear codes: it really ties the room together”, (2017) arXiv:1704.02420
- [73]
- R. Kotter. 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.
- [74]
- R. Pellikaan, “On decoding by error location and dependent sets of error positions”, Discrete Mathematics 106–107, 369 (1992) DOI
- [75]
- 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
- [76]
- D. Slepian, “Some Further Theory of Group Codes”, Bell System Technical Journal 39, 1219 (1960) DOI
- [77]
- Y. S. Han et al., “Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes”, (2014) arXiv:1408.1310
- [78]
- Y. Choukroun and L. Wolf, “Error Correction Code Transformer”, (2022) arXiv:2203.14966
- [79]
- D. Chase, “Class of algorithms for decoding block codes with channel measurement information”, IEEE Transactions on Information Theory 18, 170 (1972) DOI
- [80]
- R. Gallagher, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
- [81]
- Pearl, J. (2022). Reverend Bayes on inference engines: A distributed hierarchical approach. In Probabilistic and Causal Inference: The Works of Judea Pearl (pp. 129-138).
- [82]
- Probabilistic Reasoning in Intelligent Systems (Elsevier, 1988) DOI
- [83]
- 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
- [84]
- S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
- [85]
- K. Shimizu et al., “A parallel LSI architecture for LDPC decoder improving message-passing schedule”, 2006 IEEE International Symposium on Circuits and Systems DOI
- [86]
- 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
- [87]
- J. Chen et al., “Reduced-Complexity Decoding of LDPC Codes”, IEEE Transactions on Communications 53, 1288 (2005) DOI
- [88]
- J. Feldman. Decoding Error-Correcting Codes via Linear Programming. PhD thesis, Massachusetts Institute of Technology, 2003.
- [89]
- 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
- [90]
- J. Feldman, “LP Decoding”, Encyclopedia of Algorithms 1177 (2016) DOI
- [91]
- Changyan Di et al., “Finite-length analysis of low-density parity-check codes on the binary erasure channel”, IEEE Transactions on Information Theory 48, 1570 (2002) DOI
- [92]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [93]
- M. Schwartz and A. Vardy, “On the stopping distance and the stopping redundancy of codes”, IEEE Transactions on Information Theory 52, 922 (2006) DOI
- [94]
- 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
- [95]
- S. Habib, A. Beemer, and J. Kliewer, “RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codes”, (2023) arXiv:2112.13934
- [96]
- Gaborit, P., Murat, G., Ruatta, O., & Zemor, G. (2013, April). Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC (Vol. 2013).
- [97]
- P. Gaborit et al., “RankSign: An Efficient Signature Algorithm Based on the Rank Metric”, Post-Quantum Cryptography 88 (2014) DOI
- [98]
- T. Richardson and R. Urbanke, Modern Coding Theory (Cambridge University Press, 2008) DOI
- [99]
- David J. C. MacKay. 2002. Information Theory, Inference & Learning Algorithms. Cambridge University Press, USA
- [100]
- J. Pearl, “Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach”, Probabilistic and Causal Inference 129 (2022) DOI
- [101]
- D. J. C. MacKay and R. M. Neal, “Good codes based on very sparse matrices”, Cryptography and Coding 100 (1995) DOI
- [102]
- 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
- [103]
- A. Alahmadi et al., “On the lifted Melas code”, Cryptography and Communications 8, 7 (2015) DOI
- [104]
- S. Kopparty, Theory of Computing 11, 149 (2015) DOI
- [105]
- S. Bhandari et al., “Decoding multivariate multiplicity codes on product sets”, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) arXiv:2012.01530 DOI
- [106]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [107]
- V. Guruswami and C. Wang, “Optimal rate list decoding via derivative codes”, (2011) arXiv:1106.3951
- [108]
- D. R. Chowdhury et al., “Design of CAECC - cellular automata based error correcting code”, IEEE Transactions on Computers 43, 759 (1994) DOI
- [109]
- 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
- [110]
- J. Justesen et al., “Construction and decoding of a class of algebraic geometry codes”, IEEE Transactions on Information Theory 35, 811 (1989) DOI
- [111]
- 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) DOI
- [112]
- I. Tal and A. Vardy, “List Decoding of Polar Codes”, IEEE Transactions on Information Theory 61, 2213 (2015) DOI
- [113]
- Y. Ren et al., “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
- [114]
- 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
- [115]
- U. U. Fayyaz and J. R. Barry, “Polar codes for partial response channels”, 2013 IEEE International Conference on Communications (ICC) (2013) DOI
- [116]
- E. Arkan, “A performance comparison of polar codes and Reed-Muller codes”, IEEE Communications Letters 12, 447 (2008) DOI
- [117]
- S. Kasi et al., “Decoding Polar Codes via Noisy Quantum Gates: Quantum Circuits and Insights”, (2022) arXiv:2210.10854
- [118]
- P. Loidreau, “A Welch–Berlekamp Like Algorithm for Decoding Gabidulin Codes”, Coding and Cryptography 36 (2006) DOI
- [119]
- G. Richter and S. Plass, “Fast decoding of rank-codes with rank errors and column erasures”, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings. DOI
- [120]
- 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
- [121]
- 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
- [122]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [123]
- L. Rudolph and C. Hartmann, “Decoding by sequential code reduction”, IEEE Transactions on Information Theory 19, 549 (1973) DOI
- [124]
- G. Seroussi and A. Lempel, “Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields”, SIAM Journal on Computing 9, 758 (1980) DOI
- [125]
- 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
- [126]
- V. Guruswami and A. Vardy, “Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard”, (2004) arXiv:cs/0405005
- [127]
- E. R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 1986.
- [128]
- P. Gemmell and M. Sudan, “Highly resilient correctors for polynomials”, Information Processing Letters 43, 169 (1992) DOI
- [129]
- S. Gao, “A New Algorithm for Decoding Reed-Solomon Codes”, Communications, Information and Network Security 55 (2003) DOI
- [130]
- I. Reed et al., “The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions”, IEEE Transactions on Information Theory 24, 100 (1978) DOI
- [131]
- M. Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13, 180 (1997) DOI
- [132]
- 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
- [133]
- V. Guruswami and A. Rudra, “Limits to List Decoding Reed–Solomon Codes”, IEEE Transactions on Information Theory 52, 3642 (2006) DOI
- [134]
- J. Brakensiek, S. Gopi, and V. Makam, “Generic Reed-Solomon codes achieve list-decoding capacity”, (2023) arXiv:2206.05256
- [135]
- A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [136]
- 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
- [137]
- S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE, 1999) DOI
- [138]
- G. Zemor, “On expander codes”, IEEE Transactions on Information Theory 47, 835 (2001) DOI
- [139]
- A. L. Toom, “Nonergodic Multidimensional System of Automata”, Probl. Peredachi Inf., 10:3 (1974), 70–79; Problems Inform. Transmission, 10:3 (1974), 239–246
- [140]
- L. F. Gray, “Toom’s Stability Theorem in Continuous Time”, Perplexing Problems in Probability 331 (1999) DOI
- [141]
- P. Gács, Journal of Statistical Physics 103, 45 (2001) DOI
- [142]
- R. Silverman and M. Balser, “Coding for constant-data-rate systems”, Transactions of the IRE Professional Group on Information Theory 4, 50 (1954) DOI
- [143]
- A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI
- [144]
- F. G. Jeronimo et al., “Unique Decoding of Explicit \(ε\)-balanced Codes Near the Gilbert-Varshamov Bound”, (2020) arXiv:2011.05500
- [145]
- I. Tamo and A. Barg, “A Family of Optimal Locally Recoverable Codes”, IEEE Transactions on Information Theory 60, 4661 (2014) arXiv:1311.3284 DOI
- [146]
- N. Wiberg, H. Loeliger, and R. Kotter, “Codes and iterative decoding on general graphs”, European Transactions on Telecommunications 6, 513 (1995) DOI
- [147]
- Niclas Wiberg, Codes and decoding on general graphs. 1996. PhD thesis, Linköping University, Linköping, Sweden
- [148]
- Brendan J. Frey. Graphical models for machine learning and digital communication. MIT press, 1998.
- [149]
- 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) DOI
- [150]
- G. D. Forney, “Codes on graphs: normal realizations”, 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060) DOI
- [151]
- E. Soljanin and E. Offer, “LDPC codes: a group algebra formulation”, Electronic Notes in Discrete Mathematics 6, 148 (2001) DOI
- [152]
- T. Etzion, A. Trachtenberg, and A. Vardy, “Which codes have cycle-free Tanner graphs?”, IEEE Transactions on Information Theory 45, 2173 (1999) DOI
- [153]
- R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981) DOI
- [154]
- D. K. Kythe and P. K. Kythe, “Algebraic and Stochastic Coding Theory”, (2017) DOI
- [155]
- P. Chaichanavong and P. H. Siegel, “Tensor-product parity code for magnetic recording”, IEEE Transactions on Magnetics 42, 350 (2006) DOI
- [156]
- M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
- [157]
- C. Torezzan, S. I. R. Costa, and V. A. Vaishampayan, “Spherical codes on torus layers”, 2009 IEEE International Symposium on Information Theory (2009) DOI
- [158]
- V. I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals (translated to English), Soviet Physics Dokl., 10(8), 707-710 (1966).
- [159]
- V. I. Levenshtein, Binary codes capable of correcting spurious insertions and deletions of one (translated to English), Prob. Inf. Transmission, 1(1), 8-17 (1965).
- [160]
- 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
- [161]
- S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992) DOI
- [162]
- M.-H. Jing et al., “A Result on Zetterberg Codes”, IEEE Communications Letters 14, 662 (2010) DOI
- [163]
- E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
- [164]
- R. R. Green, "A serial orthogonal decoder," JPL Space Programs Summary, vol. 37–39-IV, pp. 247–253, 1966.
- [165]
- 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) DOI
- [166]
- A. 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
- [167]
- W. Fish et al., “Partial permutation decoding for simplex codes”, Advances in Mathematics of Communications 6, 505 (2012) DOI
- [168]
- J. D. Key and P. Seneviratne, “Partial permutation decoding for MacDonald codes”, Applicable Algebra in Engineering, Communication and Computing 27, 399 (2016) DOI