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], or a generalized polygon [8,9]. The extra structure and/or symmetry [10] 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\).
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 [11] 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.
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\) [12].
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\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(2)^{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*{(1)}\end{align} holds for any bitstring \(x\), where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\) [13; Def. 11].
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 coprime, 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\).
Cartier code Subcode of a certain residue AG code that is constructed using the Cartier operator.
Classical 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} \).
Complete-intersection RM-type code Evaluation code of polynomials evaluated on points lying on a complete intersection.
Cycle LDPC code A \(q\)-ary LDPC code whose parity-check matrix has weight-two columns. Non-binary cycle LDPC codes for \(q\geq 32\) exihibit good performance [14–16].
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.
Deligne-Lusztig code Evaluation code of polynomials evaluated on points lying on a Deligne-Lusztig variety.
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 [17].
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 [18].
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) code is called even (doubly-even) [19,20]. A code is called singly-even if all codewords are even and at least one has weight equal to 2 modulo 4.
Dual linear code For any \([n,k]_q\) linear code \(C\), the dual (or orthogonal) code, \begin{align} C^\perp = \{ y\in GF(q)^{n} ~|~ x\cdot y=0 \forall x\in C\}, \tag*{(2)}\end{align} where the ordinary, standard, or Euclidean inner product is \(x\cdot y = \sum_{i=1}^n x_i y_i\) for coordinates \(x_i,y_i\).
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 Also called a function 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. Codewords are evaluations of all functions at the specified points, \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \quad\quad\forall f\in L~. \tag*{(3)}\end{align} The code is denoted as \(C_L({\cal X},{\cal P},D)\), where the divisor \(D\) (of degree less than \(n\)) determines which rational functions to use by prescribing features associated with their zeroes and poles. The original motivation for evaluation codes, which are generalizations of RS codes that expand both the types of functions used as well as the available evaluation points, was to increase code length while maintaining good distance and size.
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 [21] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [22,23]. 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 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.
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 [24].
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*{(4)}\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.
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.
Gallager (GL) code The first LDPC code construction. 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. For example, the parity-check matrix \begin{align} \begin{pmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{pmatrix} \tag*{(5)}\end{align} contains two subsets, each consisting of two rows, and the last two rows are obtained from the first two by exchanging the second and third columns.
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 a set of distinct points \(\{\alpha_1,\cdots,\alpha_n\}\) in \(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. Each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), multiplied by a corresponding nonzero factor \(v_i \in GF(q)\), \begin{align} \mu\to\left( v_{1}f_{\mu}\left(\alpha_{1}\right),v_{2}f_{\mu}\left(\alpha_{2}\right),\cdots,v_{n}f_{\mu}\left(\alpha_{n}\right)\right)~. \tag*{(6)}\end{align}
Golay code A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [20] and sporadic simple groups [25]. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters.
Gold code Member of the family of \([2^r-1, 2r ]\) cyclic binary linear code 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\) [26].
Goldreich-Sudan code Locally testable \([[n,k,d]]\) code with \(n = k^{1+O(1/u)}\) and distance \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\).
Graph homology code This code's properties are derived from the size two chain complex associated with a particular graph. Given a connected simplicial (no self loops or muliedges) graph \(G = (V, E)\), which is not a tree, with incidence matrix \(\Gamma\) we can construct a code by choosing a parity check matrix which consists of all the linearly independent rows of \(\Gamma\). This is a \([n,k,d]\) code with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.
Grassmannian code Evaluation code of polynomials evaluated on points lying on a Grassmannian \({\mathbb{G}}(\ell,m)\).
Griesmer code A \([n,k,d]_q\) code is a Griesmer code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Griesmer bound \begin{align} n\geq\sum_{j=0}^{k-1}\left\lceil \frac{d}{q^{j}}\right\rceil ~, \tag*{(7)}\end{align} where \(\left\lceil x\right\rceil \) is the ceiling function, becomes an equality.
Group-algebra code Also known as a group code. An \( [n,k]_q \) code based on a finite group \( G \) of size \(n \). A group-algebra code for an abelian group is called an abelian group-algebra code.
Hadamard code Also known as a Walsh code or Walsh-Hadamard code. An \([2^m,m,2^{m-1}]\) balanced binary code dual to an extended Hamming Code.
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 non-zero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code.
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 \(H(x,y) = x^{q+1} + y^{q+1} - 1\) over \(\mathbb{F}_q = GF(q)\) in either affine or projective space. Hermitian codes directly improve over RS codes in the sense that RS codes have length at most \(q\) 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 with generator matrix \begin{align} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & \omega\\ 0 & 1 & 0 & 1 & \omega & 1\\ 0 & 0 & 1 & \omega & 1 & 1 \end{pmatrix}~, \tag*{(8)}\end{align} where \(GF(4) = \{0,1,\omega, \bar{\omega}\}\). Has connections to projective geometry, lattices [20], and conformal field theory [27].
Hill projective-cap code Member of a projective code family that contains of \(q\)-ary sharp configurations and that is constructed using projective caps.
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.
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 of a projective spaces. Has been generalized to incidence matrices of other structures [28,29][30; 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*{(9)}\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 a Reed-Solomon (RS) outer 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.
Klein-quartic code Evaluation AG code over \(GF(8)\) of rational functions evaluated on points lying in the Klein quartic, which is defined by the equation \(x^3 y + y^3 z + z^3 x = 0\) ([31], Ex. 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 [32] showed that related concatenated codes achieve the Gilbert-Varshamov bound.
Lazebnik-Ustimenko (LU) code LDPC code whose Tanner graph comes from a particular family of \(q\)-regular graphs [33] 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 [21] 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.
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 [34].
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\) [35].
Margulis LDPC code Member of a class of LDPC codes deterministically constructed using a class of regular graphs with no short cycles. Related explicit LDPC constructions [36] utilize Ramanujan graphs [22,23].
Maximum distance separable (MDS) code A \([n,k,d]_q\) binary or \(q\)-ary linear code is an MDS code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Singleton bound \begin{align} d \leq n-k+1 \tag*{(10)}\end{align} becomes an equality. A code is called almost MDS (AMDS) when \(d=n-k\). A bound for general \(q\)-ary codes can also be formulated; see [37; Thm. 1.9.10]. A code is near MDS (NMDS) if the code and its dual are mode AMDS.
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 [38].
Multi-edge LDPC code Irregular LDPC code whose construction generalizes those of the original examples of irregular LDPC as well as RA codes.
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 [39].
One-hot code Also known as an \(1\)-in-\(n\) 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 [40; pg. 107][41; pg. 192] for further details.
Parvaresh-Vardy (PV) code Also called a correlated RS 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.
Plane-curve code Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine plane curve.
Pless symmetry code Also called a Pless double circulant code. A member of a family of self-dual ternary \([2p+2,p+1]_3\) codes for any prime \(p \equiv -1\) modulo 6. See [42; Sec. 10.5][20; pg. 87] for explicit constructions.
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 at points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic variety \(\cal X\). Codewords \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \tag*{(11)}\end{align} are evaluations of a linear space \(L\) of polynomials \(f\). If the space is taken to be all polynomials up to some degree, the code is called a Reed-Muller-type code or RM-type code of that degree.
Projective RM (PRM) code Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates. PRM codes PRM\(_q(r,m)\) for \(r<q\) are injective evaluation codes with parameters [43] \begin{align} \left[ q^m+q^{m-1}\cdots +1, {m+r \choose r},(q+1-r)q^{m-1} \right]~. \tag*{(12)}\end{align}
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 LDPC code whose parity-check matrix is constructed using the lifting procedure (defined below) applied to the incident matrix of a sparse graph called, in this context, a protograph. 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.
Quadric code Evaluation code of polynomials evaluated on points lying on a quadric hypersurface.
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 [44]. 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 or more coordinates from each codeword.
Reed-Solomon (RS) code An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). Let \(\{\alpha_1,\cdots,\alpha_n\}\) be \(n\) distinct points in \(GF(q)\). An RS code encodes a message \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(\alpha_1),\cdots,f_\mu(\alpha_n)\}\) using a message-dependent polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \tag*{(13)}\end{align} In other words, each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), \begin{align} \mu\to\left( f_{\mu}\left(\alpha_{1}\right),f_{\mu}\left(\alpha_{2}\right),\cdots,f_{\mu}\left(\alpha_{n}\right)\right) \,. \tag*{(14)}\end{align}
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 [45].
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.
Residue AG code Also called a differential 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\). Codewords are evaluations of residues of the differential forms in the specified points, \begin{align} \left(\text{Res}_{P_{1}}(\omega),\text{Res}_{P_{2}}(\omega),\cdots,\text{Res}_{P_{n}}(\omega)\right)\quad\quad\forall\omega\in\Omega~. \tag*{(15)}\end{align} The code is denoted as \(C_{\Omega}({\cal X},{\cal P},D)\), where the divisor \(D\) determines which rational rational differential forms to use.
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.
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\).
Serge-variety RM-type code Evaluation code of polynomials evaluated on points lying on a Serge variety.
Simplex code Also known as a maximum length feedback shift register code. An \([n,k,q^{k-1}]_q\) projective code with \(n=\frac{q^k-1}{q-1}\), denoted as \(S(q,k)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(k-1,q)\), with each column being a chosen representative of the corresponding element. Its dual code is the \([n,n-k,3]_q\) \(q\)-ary Hamming code. The name of the code comes from the property that, for \(q=2\), the codewords form a \((2^k-1)\)-simplex of constant edge length if the codewords are interpreted as points in \(\mathbb{R}^n\).
Single parity-check (SPC) code Also known as a sum-zero, zero-sum, or even-weight code. An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check 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.
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 [46].
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 Gilbert-Varshamov 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\) [47].
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 [48; 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 [20] and sporadic simple groups [25]. Adding a parity bit to the code results in the \([12, 6, 6]\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters.
Tetracode The \([4,2,3]_3\) self-dual MDS code with generator matrix \begin{align} \begin{pmatrix}1 & 0 & 1 & 1\\ 0 & 1 & 1 & 2 \end{pmatrix}~, \tag*{(16)}\end{align} where \(GF(3) = \{0,1,2\}\). Has connections to lattices [20].
Tornado code Stub.
Tsfasman-Vladut-Zink (TVZ) code Member of a family of residue AG codes where \(\cal X\) is either a reduction of a Shimura curve or an elliptic curve of varying genus.
Two-weight code A linear \(q\)-ary code whose codewords all have one of two possible nonzero Hamming weights.
Weight-two code A length-\(n\) binary code whose codewords all have Hamming weight two. Such codes provide slightly extra redundancy for storage of small-scale information such as ZIP codes or decimal digits.
Wozencraft ensemble code Stub.
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
\([7,4,3]\) Hamming code Second-smallest member of the Hamming code family with generator matrix \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)~. \tag*{(17)}\end{align} Up to equivalence, this is the only nontrivial length-seven perfect binary code containing the zero vector.
\([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\) [12].
\(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*{(18)}\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\) [13; Def. 11].
\(q\)-ary parity-check code Also known as a sum-zero or zero-sum 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 \(q\)-ary LDPC code whose parity-check matrix is constructed using the lifting procedure as well as using edge scaling, i.e., the ability to assign non-binary edge weights.
\(q\)-ary 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\).
\(q\)-ary repetition code \([n,1,n]_q\) binary linear 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.

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]
Tanner, R. Michael, Deepak Sridhara, and Tom Fuja. "A class of group-structured LDPC codes." Proc. ISTA. 2001.
[11]
T. Mittelholzer, “Efficient encoding and minimum distance bounds of Reed-Solomon-type array codes”, Proceedings IEEE International Symposium on Information Theory, DOI
[12]
V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993) DOI
[13]
A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI
[14]
X.-Yu. Hu and E. Eleftheriou, “Binary representation of cycle Tanner-graph GF(2/sup b/) codes”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) (2004) DOI
[15]
R.-H. Peng and R.-R. Chen, “Design of Nonbinary Quasi-Cyclic LDPC Cycle Codes”, 2007 IEEE Information Theory Workshop (2007) DOI
[16]
C. Poulliat, M. Fossorier, and D. Declercq, “Design of regular (2,d/sub c/)-LDPC codes over GF(q) using their binary images”, IEEE Transactions on Communications 56, 1626 (2008) DOI
[17]
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
[18]
E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
[19]
S. Kurz, “Divisible Codes”, (2022) arXiv:2112.11763
[20]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[21]
S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
[22]
A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
[23]
G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
[24]
Heng Tang et al., “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
[25]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[26]
R. Gold, “Optimal binary sequences for spread spectrum multiplexing (Corresp.)”, IEEE Transactions on Information Theory 13, 619 (1967) DOI
[27]
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
[28]
B. Bagchi and S. P. Inamdar, “Projective Geometric Codes”, Journal of Combinatorial Theory, Series A 99, 128 (2002) DOI
[29]
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).
[30]
L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[31]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[32]
S. Gopi et al., “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018) DOI
[33]
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
[34]
P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
[35]
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
[36]
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
[37]
W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[38]
A. Alahmadi et al., “On the lifted Melas code”, Cryptography and Communications 8, 7 (2015) DOI
[39]
D. R. Chowdhury et al., “Design of CAECC - cellular automata based error correcting code”, IEEE Transactions on Computers 43, 759 (1994) DOI
[40]
R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
[41]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[42]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[43]
G. Lachaud, “Number of points of plane sections and linear codes defined on algebraic varieties”, Arithmetic, Geometry, and Coding Theory DOI
[44]
I. E. Bocharova et al., “Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth”, IEEE Transactions on Information Theory 58, 2265 (2012) arXiv:1108.0840 DOI
[45]
Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
[46]
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
[47]
F. G. Jeronimo et al., “Unique Decoding of Explicit \(ε\)-balanced Codes Near the Gilbert-Varshamov Bound”, (2020) arXiv:2011.05500
[48]
C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI