Here is a list of \(q\)-ary linear codes over the Galois field \(GF(q)\).
| Code | Description |
|---|---|
| Accumulate-repeat-accumulate (ARA) code | A generalization of the RA code in which the outer repetition-code encoding step is augmented with an acumulator acting on a fraction of the incoming bits. In addition, the code may be punctured after the final acumulating step. |
| Algebraic LDPC code | LDPC code whose parity check matrix is constructed explicitly (i.e., non-randomly) from a particular graph [1,2] or an algebraic structure such as a combinatorial design [3–5], balanced incomplete block design [6], a partial geometry [7], a generalized polygon [8,9], or a Latin square [10–12]. The extra structure and/or symmetry [13] of these codes can often be used to gain a better understanding of their properties. |
| Alternant code | Given a length-\(n\) GRS code \(C\) over \(GF(q^m)\), an alternant code is the \(GF(q)\)-subfield subcode of the dual of \(C\); see [14; Ch. 12]. Its parity-check matrix is an alternant matrix. |
| Array-based LDPC (AB-LDPC) code | QC-LDPC code constructed deterministically from a disk array code known as a B-code. Its parity-check matrix admits a compact representation [15] and is related to RS codes. |
| Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code | Locally testable \([n,k,d]\) code with \(n = k^{1+\epsilon}\) and query complexity of order \(O(1/\epsilon)\) for any \(\epsilon > 0\). |
| Ben-Sasson-Sudan code | Locally testable \([n,k/2,d]_{2^m}\) code with \(k\) a power of two, \(n = k \log^{c} k\), and query complexity \(\log^{c}k\) for some universal constant \(c\). |
| Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code | Locally testable \([n,k,d]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity, where \(\tilde{O}(f)=O(f\cdot (\log f)^c)\) for some fixed constant \(c\). |
| Berlekamp code | A linear \(p\)-ary code (for prime \(p\)) that has Lee distance 5 and whose construction resembles that of RS codes. It is obtained by first constructing an RS-like parity-check matrix out of a certain field extension of \(GF(p)\) and then taking the subfield subcode of the corresponding code; see [16; Ch. 10.6]. |
| Binary BCH code | Cyclic binary code of odd length \(n\) whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\) (see Cyclic-to-polynomial correspondence). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=2^r-1\) for some \(r\geq 2\). |
| Binary duadic code | Member of a pair of cyclic linear binary codes that satisfy certain relations, depending on whether the pair is even-like or odd-like duadic. Duadic codes exist for lengths \(n\) that are products of powers of primes, with each prime being \(\pm 1\) modulo \(8\) [17]. |
| Binary linear LTC | A binary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). |
| Binary quadratic-residue (QR) code | Member of a quadruple of cyclic binary codes of prime length \(n=8m\pm 1\) for \(m\geq 1\) constructed using quadratic residues and nonresidues of \(n\). |
| Block LDPC (B-LDPC) code | Member of a particular class of irregular QC-LDPC codes with efficient encoders. |
| Bose–Chaudhuri–Hocquenghem (BCH) code | Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively prime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). More general BCH codes can be defined for zeroes are powers of the form \(\{b,b+s,b+2s,\cdots,b+(\delta-2)s\}\) where gcd\((s,n)=1\). |
| Cartier code | A generalization of the Goppa codes to codes defined from curves of nonzero genus. Each code is a subcode of a certain residue AG code and is constructed using the Cartier operator. |
| Chien-Choy generalized BCH (GBCH) code | An \([n,k\geq n-rm, d\geq r+1]_q\) alternant code defined using two polynomials \(P(x),G(x)\) that are relatively prime to \(x^n-1\), with \(\deg P \leq n-1\) and \(r = \deg G \leq n-1\). |
| Classical fractal liquid code | Member of a family of \([L^D,O(L^{D-1}),O(L^{D-\epsilon})]_p\) linear codes on \(D\)-dimensional square lattices of side length \(L\) and for some prime \(p\) and \(\epsilon > 0\) that is based on \(p\)-ary generalizations of the Sierpinski triangle. |
| Classical topological code | Classical code defined on a two-dimensional lattice and derived from a geometrically local stabilizer code, such as the surface code or color code. |
| Complete-intersection RM-type code | Evaluation code of polynomials evaluated on points lying on a complete intersection. |
| Cross-interleaved RS (CIRS) code | An IRS code that is constructed using two shortened RS codes and two forms of interleaving. The code can also be visualized as a 2D array code [18]. |
| Cycle LDPC code | An LDPC code whose parity-check matrix forms the incidence matrix of a graph, i.e., has weight-two columns. |
| Cycle code | A code whose parity-check matrix forms the incidence matrix of a graph. This code's properties are derived from the size two chain complex associated with the graph. |
| Cyclic linear \(q\)-ary code | A \(q\)-ary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=q^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
| Cyclic linear binary code | A binary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=2^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
| Cyclic redundancy check (CRC) code | A generalization of the single parity-check code in which the generalization of the parity bit is the remainder of the data string (mapped into a polynomial via the Cyclic-to-polynomial correspondence) divided by some generator polynomial. A notable family of codes is referred to as CRC-(\(m-1\)), where \(m\) is the length of the generator polynomial. |
| Deligne-Lusztig code | Evaluation code of polynomials evaluated on points lying on a Deligne-Lusztig curve. |
| Denniston code | Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{GF(2^a)}\) codes for \(i < a\) constructed using Denniston arcs. |
| Difference-set cyclic (DSC) code | Cyclic LDPC code constructed deterministically from a difference set. Certain DCS codes satisfy more redundant constraints than Gallager codes and thus can outperform them [19]. |
| Dinur code | Member of infinite family of locally testable \([n,n/\text{polylog}(n),d]\) codes with vanishing rate. Code construction relies on a construction utilizing tensor-product codes [20]. |
| Divisible code | A linear \(q\)-ary block code is \(\Delta\)-divisible if the Hamming weight of each of its codewords is divisible by divisor \(\Delta\). A \(2\)-divisible (\(4\)-divisible, \(8\)-divisible) code is called even (doubly even, triply even) [21,22]. A code is called singly even if all codewords are even and at least one has weight equal to 2 modulo 4. More generally, a code is \(m\)-even if it is \(2^{m}\)-divisible. |
| Dual linear code | For any \([n,k]_q\) linear code \(C\), the dual code is the set of \(q\)-ary strings that are orthogonal to the codewords of \(C\) under a particular inner product. |
| Elliptic code | Evaluation AG code of rational functions evaluated on points lying on an elliptic curve, i.e., a curve of genus one. |
| Evaluation AG code | Evaluation code over \(GF(q)\) on a set of points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) in \(GF(q)\) lying on an algebraic curve \(\cal X\) whose corresponding vector space \(L\) of functions \(f\) consists of certain polynomials or rational functions. |
| Evaluation code | Code whose codewords are evaluations of functions at certain fixed points. Code properties can be inferred from the structure of the functions and the underlying geometric object containing the points, often using results from algebraic geometry. |
| Expander code | LDPC code whose parity-check matrix is derived from the adjacency matrix of bipartite expander graph [23] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [24,25]. Expander codes admit efficient encoding and decoding algorithms and yield an explicit (i.e., non-random) asymptotically good LDPC code family. |
| Extended GRS code | A GRS code with an additional parity-check coordinate with corresponding evaluation point of zero. In other words, an \([n+1,k,n-k+2]_q\) GRS code whose polynomials are evaluated at the points \((\alpha_1,\cdots,\alpha_n,0)\). The case when \(n=q-1\), multipliers \(v_i=1\), and \(\alpha_i\) are \(i-1\)st powers of a primitive \(n\)th root of unity is an extended narrow-sense RS code. |
| Extended IRA (eIRA) code | A generalization of the IRA code in which the outer LDGM code is replaced by a random sparse matrix containing no weight-two columns. |
| Fibonacci code | The code is defined on an \(L\times L/2\) lattice with one bit on each site, where \(L=2^N\) for an integer \(N\geq 2\). The codewords are defined to satisfy the condition that, for each lattice site \((x,y)\), the bits on \((x,y)\), \((x+1,y)\), \((x-1,y)\) and \((x,y+1)\) (where the lattice is taken to be periodic in both directions) contain an even numbers of \(1\)'s. The codewords can be generated using a one-dimensional cellular automaton of length \(L\) (periodic). The \(2^L\) possible initial states correspond to the \(2^L\) codewords. For each generation, the state of each cell is the xor sum of that cell and its two neighbors in the previous generation. After \(L/2-1\) generations, the entire history generated by the automaton corresponds to a codeword, where the initial state is the first row of the lattice, the first generation is the second row, etc. |
| Finite-geometry LDPC (FG-LDPC) code | LDPC code whose parity-check matrix is the incidence matrix of points and hyperplanes in either a Euclidean or a projective geometry. Such codes are called Euclidean-geometry LDPC (EG-LDPC) and projective-geometry LDPC (PG-LDPC), respectively. Such constructions have been generalized to incidence matrices of hyperplanes of different dimensions [26]. |
| Five-qubit perfect code | Five-qubit cyclic stabilizer code that is the smallest qubit stabilizer code to correct a single-qubit error. |
| Flag-variety code | Evaluation code of polynomials evaluated on points lying on a flag variety. |
| Folded RS (FRS) code | A linear \([n/m,k]_{q^m}\) code that is a modification of an \([n,k]_q\) RS code such that evaluations are grouped to yield a code with smaller length. In this case, the evaluation points are all powers of a generating field element \(\gamma\), \(\alpha_i=\gamma^i\). Each codeword \(\mu\) of an \(m\)-folded RS code is a string of \(n/m\) symbols, with each symbol being a string of values of a polynomial \(f_\mu\) at consecutive powers of \(\gamma\), \begin{align} \begin{split} \mu\to&\Big(\left(f_{\mu}(\alpha^{0}),\cdots,f_{\mu}(\alpha^{m-1})\right),\left(f_{\mu}(\alpha^{m}),\cdots,f_{\mu}(\alpha^{2m-1})\right)\cdots\\&\cdots,\left(f_{\mu}(\alpha^{n-m}),\cdots,f_{\mu}(\alpha^{n-1})\right)\Big)~. \end{split} \tag*{(1)}\end{align} |
| Fountain code | Code based on the idea of generating an endless stream of custom encoded packets for the receiver. The code is designed so that the receiver can recover the original transmission of size \(Kl\) bits after receiving at least \(K\) packets each of \(l\) bits. |
| Gallager (GL) code | The first LDPC code. The rows of the parity check matrix of this regular code are divided into equal subsets, and columns in the first subset are randomly permuted to yield the corresponding rows in subsequent subsets. |
| Gauss' law code | An \([m+Dm,Dm,3]\) linear binary code for \(m\geq 3^D\), defined by the Gauss' law constraint of a \(D\)-dimensional fermionic \(\mathbb{Z}_2\) gauge theory [27; Thm. 1]. The code can be re-phrased as a distance-one stabilizer code whose stabilizers consist of gauge-group elements. It can be concatenated to form a stabilizer code for fault-tolerant quantum simulation of the underlying gauge theory [27,28]. |
| Generalized Gallager code | A LDPC code that generalizes the Gallager codes using the Tanner construction. While Gallager code parity-check matrices consists of repetition code submatrices that are randomly permuted, generalized Gallager code matrices substitute general binary linear codes. |
| Generalized RM (GRM) code | Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at the points of \(GF(q)\). |
| Generalized RS (GRS) code | An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. |
| Generalized Srivastava code | An \([n,k \geq n-mst,d \geq st+1 ]_q\) alternant code defined for \(n+s\) distinct elements \(\alpha_1,\alpha_2,\cdots,\alpha_n,w_1,w_2,\cdots,w_s\) and \(n\) nonzero elements \(z_1,z_2,\cdots,z_n\) of \(GF(q^m)\). |
| Glynn code | The unique trace-Hermitian self-dual \([10,5,6]_9\) code, constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve. |
| Gold code | Member of the family of \([2^r-1, 2r ]\) cyclic binary linear codes characterized by the generator polynomial of degree \(r\) of two maximum-period sequences of period \(2^r-1\) with absolute cross-correlation \( \leq 2^{(r+2)/2}\). Gold codewords are generated using \(m\)-sequences \(x\) and \(y\), which are codewords of simplex codes with check polynomials of degree \(r\) [29]. |
| Goldreich-Sudan code | Locally testable \([n,k,d]\) code with \(n = k^{1+O(1/u)}\) and distance of order \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\). |
| Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \). |
| Graph-adjacency code | Binary linear code whose generator matrix is that of the row space of the adjacency matrix of a strongly regular graph. Given an adjacency matrix \(A\), the generator matrix is either \(G=A\) or \(G=(I|A)\), where \(I\) is the identity matrix. |
| Grassmannian code | Evaluation code of polynomials evaluated on points lying on a Grassmannian \({\mathbb{G}}(\ell,m)\) [30]. |
| Gray code | The first Gray code [31], now called the binary reflected Gray code, is a trivial \([n,n,1]\) code that orders length-\(n\) binary strings such that nearest-neighbor strings differ by only one digit via what is known as the Gray map. |
| Griesmer code | A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. |
| Group-algebra code | An \( [n,k]_q \) code whose automorphism group includes a finite group \( G \) of size \(n \), which acts on the code via its regular representation. This makes the code a \(G\)-submodule of the module \(GF(q)^n\) [33][32; Lemma 2.3]. A group-algebra code for an Abelian group is called an Abelian group-algebra code. |
| Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code. The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). |
| Hansen toric code | Evaluation code of a linear space of polynomials evaluated on points lying on an affine or projective toric variety. If the space is taken to be all polynomials up to some degree, the code is called a toric RM-type code of that degree. |
| Hermitian code | Evaluation AG code of rational functions evaluated on points lying on a Hermitian curve in either affine or projective space. Hermitian codes improve over RS codes in length: that RS codes have length at most \(q+1\) while Hermitian codes have length \(q^3 + 1\). |
| Hermitian-hypersurface code | Evaluation code of polynomials evaluated on points lying on a Hermitian hypersurface. |
| Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [22], and conformal field theory [34]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [35]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
| Higman-Sims graph-adjacency code | A graph-based code whose generator matrix is constructed using the adjacency matrix of the Higman-Sims graph. This family includes a \([100,22,32]\) code whose dual is an optimal \([100,78,8]\) code [36; Table VI]. |
| Hill projective-cap code | Member of a projective code family that contains of \(q\)-ary sharp configurations and that is constructed using projective caps. |
| Hirschfeld code | A projective geometry code that is an example of an MDS code that is not an RS code; see [37; Exam. 7.6] for the description. |
| Hoffman-Singleton cycle code | A \([50,21,12]\) cycle code whose parity-check matrix is the incidence matrix of the Hoffman-Singleton graph [38]. Its dual is a \([50,29,8]\) code [36; Table II]. |
| Hoffman-Singleton graph-adjacency code | A graph-based code whose generator matrix is that of the row space of the adjacency matrix of the Hoffman-Singleton graph [38]. This \([50,22,7]\) code is dual to a \([50,28,8]\) code [36; Table III]. |
| Hsu-Anastasopoulos LDPC (HA-LDPC) code | A regular LDPC code obtained from a concatenation of a certain random regular LDPC code and a certain random LDGM code. Using rate-one LDGM codes eliminates high-weight codewords while admitting an amount of low-weight codewords that asymptotically vanishes, allowing code families to achieve the GV bound with high probability. |
| Hyperbolic evaluation code | An evaluation code over polynomials in two variables. Generator matrices are determined in Ref. [39] following initial formulations of the codes as generalized concatenations of RS codes [40,41]; see [42; Exam. 4.26]. |
| Hyperoval code | A projective code constructed using hyperovals in projective space. |
| Incidence-matrix projective code | Code whose generator matrix is the incidence matrix of points and hyperplanes in a projective space. Has been generalized to incidence matrices of other structures [43,44][45; Sec. 14.4]. Columns of a code's parity-check matrix can similarly correspond to an incidence matrix. |
| Interleaved RS (IRS) code | A modification of RS codes where multiple polynomials are used to define each codeword. Each codeword \(\mu\) of a \(t\)-interleaved RS code is a string of values of the corresponding set \(\{f_\mu^{(1)},f_\mu^{(2)},\cdots,f_\mu^{(t)}\}\) of \(t\) polynomials at the points \(\alpha_i\). The vector codewords can be arranged in an array whose rows are ordinary RS codes for each polynomial \(f^{j}\), yielding the encoding \begin{align} \mu\to\left( \begin{array}{cccc} f_{\mu}^{(1)}\left(\alpha_{1}\right) & f_{\mu}^{(1)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(1)}\left(\alpha_{n}\right)\\ f_{\mu}^{(2)}\left(\alpha_{1}\right) & f_{\mu}^{(2)}\left(\alpha_{2}\right) & & f_{\mu}^{(2)}\left(\alpha_{n}\right)\\ \vdots & & \ddots & \vdots\\ f_{\mu}^{(t)}\left(\alpha_{1}\right) & f_{\mu}^{(t)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(t)}\left(\alpha_{n}\right) \end{array}\right)~. \tag*{(2)}\end{align} |
| Irregular LDPC code | An LDPC code whose parity-check matrix has a variable number of entries in each row or column. |
| Irregular repeat-accumulate (IRA) code | A generalization of the RA code in which the outer 1-in-3 repetition encoding step is replaced by an LDGM code. A simple version is when different bits in the RA block are repeated a different number of times. |
| Justesen code | Binary linear code resulting from generalized concatenation of an outer RS code with multiple inner codes sampled from the Wozencraft ensemble, i.e., \(N\) distinct binary inner codes of dimension \(m\) and length \(2m\). The first asymptotically good codes. |
| Karlin double circulant code | Member of the family of \([2m+2,m+1]\) double circulant codes such that \(m\) is prime of the form \(8k+3\) for some \(k\), and \(2m+2\) is a multiple of eight. See [14; Ch. 16] for their generator matrix. |
| Kasami code | Member of the family of \([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) cyclic binary linear codes. |
| Klein-quartic code | Evaluation AG code over \(GF(8)\) of rational functions evaluated on points lying on the Klein quartic, which is defined by the equation \(x^3 y + y^3 z + z^3 x = 0\) ([42], Exam. 2.75). |
| Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code | Member of a family of locally testable binary linear codes with constant rate, constant relative distance, and subpolynomial query complexity \(u = (\log n)^{O(\log \log n)}\)). Later work by Gopi, Kopparty, Oliveira, Ron-Zewi, and Saraf [46] showed that related concatenated codes achieve the GV bound. |
| Lazebnik-Ustimenko (LU) code | LDPC code whose Tanner graph comes from a particular family of \(q\)-regular graphs [47] of known girth and relatively large stopping sets. |
| Left-right Cayley complex code | Binary code constructed on a left-right Cayley complex using a pair of base codes \(C_A,C_B\) and an expander graph [23] such that codewords for a fixed graph vertex are codewords of the tensor code \(C_A \otimes C_B\). A family of such codes is one of the first \(c^3\)-LTCs. |
| Linear \(q\)-ary code | An \((n,K,d)_q\) linear code is denoted as \([n,k,d]_q\), where \(k=\log_q K\) need not be an integer. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(\alpha x+ \beta y\) is also a codeword for any \(q\)-ary digits \(\alpha,\beta\). This extra structure yields much information about their properties, making them a large and well-studied subset of codes. |
| Linear binary code | An \((n,2^k,d)\) linear code is denoted as \([n,k]\) or \([n,k,d]\), where \(d\) is the code's distance. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. A code that is not linear is called nonlinear. |
| Linear code with complementary dual (LCD) | A linear code \(C\) admits a complementary dual if \(C\) and its dual code \(C^{\perp}\) do not share any codewords. |
| Long code | Locally testable \([2^{2^k},k,d]\) code. The encoder maps a \(k\)-bit string into a codeword that consists of the values of all Boolean functions on the \(k\)-bit string. The code is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [48]. |
| Low-density generator-matrix (LDGM) code | Binary linear code with a sparse generator matrix. Alternatively, a member of an infinite family of \([n,k,d]\) codes for which the number of nonzero entries in each row and column of the generator matrix are both bounded by a constant as \(n\to\infty\). The dual of an LDGM code has a sparse parity-check matrix and is called an LDPC code. |
| Low-density parity-check (LDPC) code | A binary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\). |
| Luby transform (LT) code | Erasure codes based on fountain codes. They improve on random linear fountain codes by having a much more efficient encoding and decoding algorithm. |
| MacKay-Neal LDPC (MN-LDPC) code | Codes whose parity-check matrix is constructed non-deterministically via the MacKay-Neal prescription. The parity-check matrix of an \((l,r,g\))-MN-LDPC code is of the form \((H_1~H_2)\), where \(H_1\) is a random binary matrix of column weight \(l\) and row weight \(r\), and \(H_2\) is a random binary matrix of column and row weight \(g\) [49]. |
| Margulis LDPC code | Member of a class of LDPC codes deterministically constructed using an explicit class of regular graphs with no short cycles. Related explicit LDPC constructions [50] utilize Ramanujan graphs [24,25]. |
| Maximum distance separable (MDS) code | A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality. |
| Meir code | Locally testable \([n,k,d]_q\) code with query complexity \(\text{poly}(\log k)\) and rejection ratio \(R/n = 1/\text{poly}(\log k)\). Code construction is probabilistic and combinatorial. |
| Melas code | Cyclic \([2^m -1, 2^m - 1 - 2m, 5]\) linear code with generator polynomial is \(g(x) = p(x)p(x)^{\star}\), where \(p(x)\) is a primitive polynomial of degree \(m\) that is the minimal polynomial over \(GF(2)\) of an element \(\alpha\) of order \(2^m -1\) in \(GF(2^m)\), \(m\) is odd and greater that five, and '\(\star\)' denotes reciprocation [51]. |
| Multi-edge LDPC code | Irregular LDPC code whose construction generalizes those of the original examples of irregular LDPC as well as RA codes. |
| Multiplicity code | A generalization of an \(m\)-variate polynomial evaluation code based on evaluating polynomials and \(s\) of their derivatives at all points in \(GF(q)^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [52]. Univariate (\(m=1\)) [52,53] and multivariante (\(m>1\)) [54] codes have been proposed. |
| Narrow-sense RS code | An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(GF(q)\). |
| Newman-Moore code | Member of a family of \([L^2,O(L),O(L^{\frac{\log 3}{\log 2}})]\) binary linear codes on \(L\times L\) square lattices that form the ground-state subspace of a class of exactly solvable spin-glass models with three-body interactions. The codewords resemble the Sierpinski triangle on a square lattice, which can be generated by a cellular automaton [55]. |
| Norm-trace code | Evaluation AG code of rational functions evaluated on points lying on a Miura-Kamiya curve in either affine or projective space. The family is named as such because the equations defining the curves can be expressed in terms of the field norm and field trace. |
| One-hot code | A length-\(n\) binary code whose codewords are those with Hamming weight one. The reverse of this code, where all codewords have Hamming weight \(n-1\) is called a one-cold code. |
| Ovoid code | Member of a \([q^2+1,4,q^2-q]_q\) projective code family that is universally optimal and that is constructed using ovoids in projective space. See [56; pg. 107][57; pg. 192] for further details. |
| Parity-check tensor-product code | A matrix-based code constructed out of two linear binary or \(q\)-ary codes with parity-check matrices \(H_A,H_B\) such its parity-check matrix is \(H_A \otimes H_B\). Its dual has parity-check matrix \(G_A\otimes G_B\), where \(G_{A,B}\) are the generator matrices of the two underlying codes [58]. |
| Parvaresh-Vardy (PV) code | An IRS code with additional algebraic relations (a.k.a. correlations) between the codeword polynomials \(\{f^{(j)}\}_{j=1}^{t}\). These relations yielded a list decoder that achieves list-decoding capacity. |
| Petersen cycle code | A \([15,6,5]\) cycle code whose parity-check matrix is the incidence matrix of the Petersen graph. The Petersen graph can be thought of as a dodecahedron with antipodes identified [59; Appx. A.2.1]. |
| Plane-curve code | Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine or projective plane curve. |
| Plaquette Ising code | Classical code defined on a two-dimensional square lattice whose parity checks are applied on the four vertices of each square. |
| Pless symmetry code | A member of a family of self-dual ternary \([2q+2,q+1]_3\) codes for any power of an odd prime satisfying \(q \equiv 2\) modulo 3. |
| Polar code | In its basic version, a binary linear polar code encodes \(K\) message bits into \(N=2^n\) bits. The linear transformation that defines the code is given by the matrix \(G^{(n)}=B_N G^{\otimes n}\), where \(B_N\) is a certain \(N\times N\) permutation matrix, and \(G^{\otimes n}\) is the \(n\)th Kronecker power of the \(2\times 2\) kernel matrix \(G=\left[\begin{smallmatrix}1 & 0\\ 1 & 1 \end{smallmatrix}\right]\). To encode \(K\) message bits, one forms an \(N\)-vector \(u\) in which \(K\) coordinates represent the message bits. The remaining \(N-K\) coordinates are set to some fixed values and are said to be frozen. The codeword \(x \in \{0,1\}^N\) is obtained as \(x=u G^{\otimes n}\). |
| Polynomial evaluation code | Evaluation code of polynomials (or, more generally, rational functions) at points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic variety \(\cal X\) of dimension greater than one (i.e., not an algebraic curve). |
| Primitive narrow-sense BCH code | BCH codes for \(b=1\) and for \(n=q^r-1\) for some \(r\geq 2\). |
| Projective RM (PRM) code | Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) with \(n=m+1\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates. |
| Projective geometry code | Linear \(q\)-ary \([n,k,d]\) code such that columns of its generator matrix \(G\) does not contain any repeated columns or the zero column. That way, each column corresponds to a distinct point in the projective space \(PG(k-1,q)\) arising from a \(k\)-dimensional vector space over \(GF(q)\). If the columns are linearly independent, then the codewords are collectively called an information set. Columns of a code's parity-check matrix can similarly correspond to points in projective space. This formulation yields connections to projective geometry, which can be applied to determine code properties. |
| Projective two-weight code | A projective code whose codewords all have one of two possible nonzero Hamming weights. |
| Protograph LDPC code | Binary version of a \(q\)-ary protograph LDPC code. Its parity check matrix can be put into the form of a block matrix consisting of either a sum of permutation sub-matrices or the zero sub-matrix. |
| Pyramid code | An LRC whose generator matrix is that of an RS code in standard form, but some of whose columns are split into multiple columns; see [60; Sec. 31.3.1.1] for an example. |
| Quadratic-residue (QR) code | Member of a quadruple of cyclic \(q\)-ary codes of prime length \(n\) where \(q\) is prime and a quadratic-residue modulo \(n\). The codes are constructed using quadratic residues and nonresidues of \(n\). Extensions to prime-power \(q\) are also known [61,62]. |
| Quadric code | Evaluation code of polynomials evaluated on points lying on a quadric hypersurface. |
| Quantum convolutional code | One-dimensional translationally invariant qubit stabilizer code whose whose stabilizer group can be partitioned into constant-size subsets of constant support and of constant overlap between neighboring sets. Initially formulated as a quantum analogue of convolutional codes, which were designed to protect a continuous and never-ending stream of information. Precise formulations sometimes begin with a finite-dimensional lattice, with the intent to take the thermodynamic limit; logical dimension can be infinite as well. |
| Quantum irregular convolutional code (QIRCC) | Quantum convolutional code whose stabilizer group consists of different constant-size subsets. |
| Quantum turbo code | A quantum version of the turbo code, obtained from an interleaved serial quantum concatenation [63; Def. 30] of quantum convolutional codes. |
| Quasi group-algebra code | A \(q\)-ary linear code based on a finite group \( G \) of order \(n/\ell\) for some index \(\ell\). The code is a right submodule of the direct sum of \(\ell\) copies of the group algebra \(\mathbb{F}_q G\). A quasi group-algebra code for an Abelian group is called an Abelian quasi group-algebra code. |
| Quasi-cyclic LDPC (QC-LDPC) code | LDPC code that can be put into quasi-cyclic form. Its parity check matrix can be put into the form of a block matrix consisting of either circulant permutation sub-matrices or the zero sub-matrix. Such codes are often constructed by lifting certain protographs into such block matrices [64]. Their simple structure makes them useful for several wireless communication standards. |
| Raptor (RAPid TORnado) code | Raptor codes are concatenated erasure codes with two layers: an outer pre-code and a Luby-Transform (LT) inner code. The pre-code is a linear binary erasure code, which is applied first to the input to create some redundant data. The LT code is then applied to the intermediate symbols from the pre-code to generate final output symbols to be transmitted. |
| Reed-Muller (RM) code | Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). |
| Regular LDPC code | An LDPC code whose parity-check matrix has a fixed number of entries for each row or column. |
| Regular binary Tanner code | A binary Tanner code defined on a regular bipartite graph, with the inner code being the same for all vertices. |
| Repeat-accumulate (RA) code | An LDPC code whose parity-check matrix has weight-two columns arranged in a step-like pattern for its last columns [65]. |
| Repeat-accumulate-accumulate (RAA) code | Generalization of the RA code in which two accumulators and permutations are used. |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. Its automorphism group is \(S_n\). |
| Residue AG code | Linear \(q\)-ary code defined using a set of points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) in \(GF(q)\) lying on an algebraic curve \(\cal X\) and a linear space \(\Omega\) of certain rational differential forms \(\omega\). |
| Roth-Lempel code | Member of a \(q\)-ary linear code family that includes many examples of MDS codes that are not GRS codes. |
| Ruled-surface code | Evaluation code of polynomials evaluated on points lying on a ruled surface. |
| Schubert code | Evaluation code of polynomials evaluated on points lying on a Schubert variety. |
| Segre-variety RM-type code | Evaluation code of polynomials evaluated on points lying on a Segre variety. |
| Self-dual linear code | An \([n,n/2]_q\) code that is equal to its dual, \(C^\perp = C\), where the dual is defined with respect to an inner product, most commonly either Euclidean or Hermitian. Self-dual codes exist only for even lengths and have dimension \(k=n/2\). A code that is equivalent to its dual is called iso-dual. |
| Single parity-check (SPC) code | An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings. Its automorphism group is \(S_n\). |
| Spatially coupled LDPC (SC-LDPC) code | LDPC code whose parity-check matrix is constructed by "spatially" coupling several copies of a regular LDPC parity-check matrix in chain-like fashion (or, more generally, in grid-like fashion) to yield a band matrix. A finite-length chain is then capped by imposing either open boundary conditions (yielding non-tail-biting SC-LDPC codes) or open boundary conditions (yielding tail-biting SC-LDPC codes); sometimes extra terminating vertices are added to the ends of the chain. Matrices corresponding to translationally invariant chains are called time-variant, and otherwise are called time-invariant. These codes can be constructed, e.g., using the lifting procedure or using edge-cutting vectors [66]. |
| Srivastava code | A special case of a generalized Srivastava code for \(z_j = \alpha_j^{\mu}\) for some \(\mu\) and \(t=1\). |
| Suzuki-curve code | Evaluation AG code of rational functions evaluated on points lying on a Suzuki curve. |
| Ta-Shma zigzag code | Member of a family of \(\epsilon\)-balanced codes that nearly achieves the asymptotic GV bound. The codes have relative distance \(\frac{1}{2}-\frac{\epsilon}{2}\) and rate of order \(\Omega (\epsilon^{2+\beta})\) for \(\beta\to 0\) as \(n\to\infty\) [67]. |
| Tamo-Barg code | A family of \(q\)-ary polynomial evaluation codes that are optimal LRCs and for which \(q\) is comparable to \(n\). |
| Tamo-Barg-Vladut code | Polynomial evaluation code on algebraic curves, such as Hermitian or Garcia-Stichtenoth curves, that is constructed to be an LRC. Codes can be constructed to be be able to recover locally after one or more erasures as well as to tackle the availability problem. |
| Tanner code | A linear \(q\)-ary code defined on a bipartite graph similar to a Tanner graph. This generalized Tanner graph consists of variable nodes and constraint nodes, with the generalization being that the constraint nodes of degree \(r\) now represent a linear codes of length \(r\). |
| Tanner-Sridhara-Fuja (TSF) code | Array QC-LDPC code constructed from a cyclically shifted identity matrix; see [68; Exam. 21.6.5]. |
| Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [22] and sporadic simple groups [14]. Adding a parity bit to the code results in the self-dual \([12,6,6]_3\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters [69]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode. |
| Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [22]. |
| Tornado code | Linear binary code that is a precursor to fountain codes and whose encoding and decoding operations involve only XOR gates [70; Sec. 30.2]. |
| Tsfasman-Vladut-Zink (TVZ) code | Member of a family of residue AG or, more generally, evaluation AG codes where \(\cal X\) is either Drinfeld modular curve, a classic modular curve, or a Garcia-Stichtenoth curve. |
| Two-weight code | A linear \(q\)-ary code whose codewords all have one of two possible nonzero Hamming weights. |
| Wozencraft ensemble code | A code that is part of the Wozencraft ensemble, a set of codes most of whose members achieve the GV bound. |
| Zetterberg code | Family of binary cyclic \([2^{2s}+1,2^{2s}-4s+1]\) codes with distance \(d>5\) generated by the minimal polynomial \(g_s(x)\) of \(\alpha\) over \(GF(2)\), where \(\alpha\) is a primitive \(n\)th root of unity in the field \(GF(2^{4s})\). They are quasi-perfect codes and are one of the best known families of double-error correcting binary linear codes |
| \((5,1,2)\)-convolutional code | Family of quantum convolutional codes that are 1D lattice generalizations of the five-qubit perfect code, with the former''s lattice-translation symmetry being the extension of the latter''s cyclic permutation symmetry. |
| \([23, 12, 7]\) Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [22] and sporadic simple groups [14]. Up to equivalence, it is unique for its parameters [69]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [71]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [72,73]. |
| \([24, 12, 8]\) Extended Golay code | A self-dual \([24, 12, 8]\) code that is obtained from the Golay code by adding a parity check. Up to equivalence, it is unique for its parameters [69]. |
| \([2^m,m+1,2^{m-1}]\) First-order RM code | A member of the family of first-order RM codes. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). They form a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping. |
| \([2^m-1,m,2^{m-1}]\) simplex code | A member of the code family that is dual to the \([2^m,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping. |
| \([2^r,2^r-r-1,4]\) Extended Hamming code | Member of an infinite family of binary linear codes with parameters \([2^r,2^r-r-1, 4]\) for \(r \geq 2\) that are extensions of the Hamming codes by a parity-check bit. |
| \([2^r-1,2^r-r-1,3]\) Hamming code | Member of an infinite family of perfect linear codes with parameters \([2^r-1,2^r-r-1, 3]\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity-check matrix \(H\) has all possible nonzero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code. |
| \([48,24,12]\) self-dual code | An extended quadratic-residue code that is known to be the only self-dual doubly even code at its parameters [74]. |
| \([56,6,36]_3\) Hill-cap code | Projective two-weight ternary code based on the Games graph [76][75; Table 19.1] and Hill's 56-cap [77]. Its automorphism group contains \(PSL_3(4)\) [78]. |
| \([7,3,4]\) simplex code | Second-smallest member of the simplex code family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(2,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((8,9)\) simplex spherical code under the antipodal mapping. |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family. |
| \([78,6,56]_4\) Hill-cap code | Projective two-weight quaternary code based on a cap that corresponds to a strongly regular graph [76; Table 7.1]. |
| \([8,4,4]\) extended Hamming code | Extension of the \([7,4,3]\) Hamming code by a parity-check bit. The smallest doubly even self-dual code. |
| \(q\)-ary Hamming code | Member of an infinite family of perfect linear \(q\)-ary codes with parameters \([(q^r-1)/(q-1),(q^r-1)/(q-1)-r, 3]_q\) for \(r \geq 2\). |
| \(q\)-ary LDGM code | \(q\)-ary linear code with a sparse generator matrix. Alternatively, a member of an infinite family of \([n,k,d]_q\) codes for which the number of nonzero entries in each row and column of the generator matrix are both bounded by a constant as \(n\to\infty\). |
| \(q\)-ary LDPC code | A \(q\)-ary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]_q\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\). |
| \(q\)-ary duadic code | Member of a pair of cyclic linear binary codes that satisfy certain relations, depending on whether the pair is even-like or odd-like duadic. Duadic codes exist only when \(q\) is a square modulo \(n\) [17]. |
| \(q\)-ary linear LCC | A linear code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). |
| \(q\)-ary linear LTC | A \(q\)-ary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(q)^{r\times n}\) have weight at most \(u\) and if \begin{align} \frac{1}{r}|H x| \geq \frac{R}{n} D(x,C) \tag*{(3)}\end{align} holds for any \(q\)-ary string \(x\), where \(D(x,C)\) is the \(q\)-ary Hamming distance between \(x\) and the closest codeword to \(x\) [79; Def. 11]. A code satisfying the above constraint without the weight-\(u\) restriction is called an \(R\)-testable code [80]. |
| \(q\)-ary parity-check code | An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check or zero-sum check digit such that the sum over all coordinates of each codeword is zero. |
| \(q\)-ary protograph LDPC code | A \(q\)-ary LDPC code whose parity-check matrix is constructed using the lifting procedure applied to the incidence matrix of a sparse graph called, in this context, a protograph. An ability to assign non-binary edge weight called edge scaling can also be used in code construction. |
| \(q\)-ary repetition code | An \([n,1,n]_q\) code encoding consisting of codewords \((j,j,\cdots,j)\) for \(j \in GF(q)\). The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. |
| \(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. |
References
- [1]
- G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica 2, 71 (1982) DOI
- [2]
- C. A. Kelley, D. Sridhara, and J. Rosenthal, “Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights”, IEEE Transactions on Information Theory 53, 1460 (2007) DOI
- [3]
- S. J. Johnson and S. R. Weller, “Regular low-density parity-check codes from combinatorial designs”, Proceedings 2001 IEEE Information Theory Workshop (Cat. No.01EX494) DOI
- [4]
- S. J. Johnson and S. R. Weller, “Construction of low-density parity-check codes from Kirkman triple systems”, GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270) DOI
- [5]
- S. J. Johnson and S. R. Weller, “Resolvable 2-designs for regular low-density parity-check codes”, IEEE Transactions on Communications 51, 1413 (2003) DOI
- [6]
- B. Vasic and O. Milenkovic, “Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding”, IEEE Transactions on Information Theory 50, 1156 (2004) DOI
- [7]
- S. J. Johnson and S. R. Weller, “Codes for iterative decoding from partial geometries”, Proceedings IEEE International Symposium on Information Theory, DOI
- [8]
- P. O. Vontobel and R. M. Tanner, “Construction of codes based on finite generalized quadrangles for iterative decoding”, Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252) DOI
- [9]
- Z. Liu and D. A. Pados, “LDPC Codes From Generalized Polygons”, IEEE Transactions on Information Theory 51, 3890 (2005) DOI
- [10]
- O. Milenkovic and S. Laendner, “Analysis of the cycle-structure of LDPC codes based on Latin squares”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) 777 (2004) DOI
- [11]
- S. Laendner and O. Milenkovic, “LDPC Codes Based on Latin Squares: Cycle Structure, Stopping Set, and Trapping Set Analysis”, IEEE Transactions on Communications 55, 303 (2007) DOI
- [12]
- L. Zhang, Q. Huang, S. Lin, K. Abdel-Ghaffar, and I. F. Blake, “Quasi-Cyclic LDPC Codes: An Algebraic Construction, Rank Analysis, and Codes on Latin Squares”, IEEE Transactions on Communications 58, 3126 (2010) DOI
- [13]
- Tanner, R. Michael, Deepak Sridhara, and Tom Fuja. "A class of group-structured LDPC codes." Proc. ISTA. 2001.
- [14]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [15]
- T. Mittelholzer, “Efficient encoding and minimum distance bounds of Reed-Solomon-type array codes”, Proceedings IEEE International Symposium on Information Theory, DOI
- [16]
- R. Roth, Introduction to Coding Theory (Cambridge University Press, 2006) DOI
- [17]
- V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993) DOI
- [18]
- M. Blaum, P. G. Farrell, H. C. A. van Tilborg, 1998. Array codes. Handbook of coding theory, 2 (Part 2), pp. 1855-1909.
- [19]
- D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, Codes, Systems, and Graphical Models 113 (2001) DOI
- [20]
- E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
- [21]
- S. Kurz, “Divisible Codes”, (2023) arXiv:2112.11763
- [22]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [23]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [24]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [25]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [26]
- Heng Tang, Jun Xu, S. Lin, and K. A. S. Abdel-Ghaffar, “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
- [27]
- L. Spagnoli, A. Roggero, and N. Wiebe, “Fault-tolerant simulation of Lattice Gauge Theories with gauge covariant codes”, (2024) arXiv:2405.19293
- [28]
- A. Rajput, A. Roggero, and N. Wiebe, “Quantum Error Correction with Gauge Symmetries”, (2022) arXiv:2112.05186
- [29]
- R. Gold, “Optimal binary sequences for spread spectrum multiplexing (Corresp.)”, IEEE Transactions on Information Theory 13, 619 (1967) DOI
- [30]
- D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI
- [31]
- Gray, Frank. "Pulse code communication." United States Patent Number 2632058 (1953).
- [32]
- A. Günther and G. Nebe, “Automorphisms of doubly even self-dual binary codes”, Bulletin of the London Mathematical Society 41, 769 (2009) arXiv:0810.3787 DOI
- [33]
- Günther, Annika. Automorphism groups of self-dual codes. Diss. Aachen, Techn. Hochsch., Diss., 2009, 2009.
- [34]
- J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI
- [35]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [36]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [37]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [38]
- A. J. Hoffman and R. R. Singleton, “On Moore Graphs with Diameters 2 and 3”, IBM Journal of Research and Development 4, 497 (1960) DOI
- [39]
- O. Geil and T. Høholdt, “On Hyperbolic Codes”, Lecture Notes in Computer Science 159 (2001) DOI
- [40]
- K. Saints and C. Heegard, “On hyperbolic cascaded Reed-Solomon codes”, Lecture Notes in Computer Science 291 (1993) DOI
- [41]
- Gui-Liang Feng and T. R. N. Rao, “Improved geometric Goppa codes. I. Basic theory”, IEEE Transactions on Information Theory 41, 1678 (1995) DOI
- [42]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [43]
- B. Bagchi and S. P. Inamdar, “Projective Geometric Codes”, Journal of Combinatorial Theory, Series A 99, 128 (2002) DOI
- [44]
- M. Lavrauw, L. Storme, and G. Van de Voorde (2010). Linear codes from projective spaces. In A. Bruen & D. Wehlau (Eds.), Contemporary Mathematics (Vol. 523, pp. 185–202). Providence, RI, USA: American Mathematical Society (AMS).
- [45]
- L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [46]
- S. Gopi, S. Kopparty, R. Oliveira, N. Ron-Zewi, and S. Saraf, “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018) DOI
- [47]
- F. Lazebnik and V. A. Ustimenko, “Explicit construction of graphs with an arbitrary large girth and of large size”, Discrete Applied Mathematics 60, 275 (1995) DOI
- [48]
- P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
- [49]
- K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI
- [50]
- J. Rosenthal and P. O. Vontobel, “Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis”, Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252) DOI
- [51]
- 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
- [52]
- M. Yu. Rosenbloom, M. A. Tsfasman, “Codes for the m-Metric”, Probl. Peredachi Inf., 33:1 (1997), 55–63; Problems Inform. Transmission, 33:1 (1997), 45–52
- [53]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [54]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
- [55]
- 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
- [56]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [57]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [58]
- D. Ostrev, D. Orsucci, F. Lázaro, and B. Matuz, “Classical product code constructions for quantum Calderbank-Shor-Steane codes”, Quantum 8, 1420 (2024) arXiv:2209.13474 DOI
- [59]
- J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, “Magic state distillation with low space overhead and optimal asymptotic input count”, Quantum 1, 31 (2017) arXiv:1703.07847 DOI
- [60]
- V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, "Codes for Distributed Storage." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [61]
- J. van Lint and F. MacWilliams, “Generalized quadratic residue codes”, IEEE Transactions on Information Theory 24, 730 (1978) DOI
- [62]
- J. H. Lint, “Generalized quadratic-residue codes”, Algebraic Coding Theory and Applications 285 (1979) DOI
- [63]
- D. Poulin, J.-P. Tillich, and H. Ollivier, “Quantum serial turbo-codes”, (2009) arXiv:0712.2888
- [64]
- I. E. Bocharova, F. Hug, R. Johannesson, B. D. Kudryashov, and R. V. Satyukov, “Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth”, IEEE Transactions on Information Theory 58, 2265 (2012) arXiv:1108.0840 DOI
- [65]
- Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
- [66]
- H. Esfahanizadeh, A. Hareedy, and L. Dolecek, “Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting”, IEEE Transactions on Communications 67, 3 (2019) DOI
- [67]
- 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
- [68]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [69]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [70]
- I. F. Blake, "Coding for Erasures and Fountain Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [71]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
- [72]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [73]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [74]
- S. K. Houghten, C. W. H. Lam, L. H. Thiel, and J. A. Parker, “The extended quadratic residue code is the only (48,24,12) self-dual doubly-even code”, IEEE Transactions on Information Theory 49, 53 (2003) DOI
- [75]
- A. E. Brouwer, "Two-weight Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [76]
- R. A. Games, “The packing problem for projective geometries over GF(3) with dimension greater than five”, Journal of Combinatorial Theory, Series A 35, 126 (1983) DOI
- [77]
- Hill, R. (1973). On the largest size of cap in s53. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, 54(3), 378-384.
- [78]
- N. Pace and A. Sonnino, “On linear codes admitting large automorphism groups”, Designs, Codes and Cryptography 83, 115 (2016) DOI
- [79]
- A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI
- [80]
- M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681