Welcome to the Galois-field Kingdom.

Galois-field \(q\)-ary code Encodes \(K\) states (codewords) in \(n\) \(q\)-ary coordinates over the field \(GF(q)=\mathbb{F}_q\) and has distance \(d\). Usually denoted as \((n,K,d)_q\). The distance is the minimum number of coordinates where two strings in the code differ. Protection: Detects errors on up to \(d-1\) coordinates, corrects erasure errors on up to \(d-1\) coordinates, and corrects general errors on up to \(\left\lfloor (d-1)/2 \right\rfloor\) coordinates. Parents: Error-correcting code (ECC). Parent of: Additive \(q\)-ary code, Algebraic-geometry (AG) code, Matrix-product code.
Additive \(q\)-ary code A \(q\)-ary code whose codewords are closed under addition, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. Parents: Galois-field \(q\)-ary code. Parent of: Dual additive code, Linear \(q\)-ary code. Cousin of: Galois-qudit stabilizer code.
Algebraic-geometry (AG) code[1][2][3] Binary or \(q\)-ary code constructed from an algebraic curve of some genus over a finite field via the evaluation construction, the residue construction, or more general constructions that yield nonlinear codes. Linear AG codes from the first two constructions are also called geometric Goppa codes. Parents: Galois-field \(q\)-ary code. Parent of: Evaluation AG code, Nonlinear AG code, Residue AG code. Cousins: Maximum distance separable (MDS) code. Cousin of: Evaluation code.
Matrix-product code[4] Code constructed using a concatenation procedure that yields a code consisting of all products of codewords in \(M\) length-\(n\) \(q\)-ary codes and an \(M\times N\) \(q\)-ary matrix with \(N\geq M\). A prominent subclass is the case with \(A\) is non-singular by columns (NSC). Parents: Galois-field \(q\)-ary code. Parent of: Generalized RM (GRM) code. Cousin of: True Galois-qudit stabilizer code.
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\). Protection: Distance \(d\) of a linear code is the number of nonzero entries in the (nonzero) codeword with the smallest such number. Corrects any error set such that the difference of any pair of distinct elements of the set is a codeword. Parents: Additive \(q\)-ary code, Linear code. Parent of: Cyclic linear \(q\)-ary code, Evaluation AG code, Folded RS (FRS) code, Gabidulin code, Generalized RM (GRM) code, Interleaved RS (IRS) code, Projective geometry code, Wozencraft ensemble code, \(q\)-ary Hamming code. Cousin of: Entanglement-assisted (EA) QECC, Entanglement-assisted (EA) stabilizer code, Evaluation code, Galois-qudit CSS code, Modular-qudit CSS code, True Galois-qudit stabilizer code.
Dual additive code For any \(q\)-ary additive code \(C\), the dual additive (or orthogonal additive) code is \begin{align} C^\perp = \{ y\in GF(q)^{n} ~|~ x \star y=0 \forall x\in C\}, \end{align} where the trace inner product is \(x\star y = \sum_{i=1}^n \text{tr}(x_i y_i)\) for coordinates \(x_i,y_i\), and the trace maps elements of the field \(GF(q)\) with \(q=p^m\) to elements of \(GF(p)\) as \begin{align} \text{tr}(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~. \end{align} Parents: Additive \(q\)-ary code. Cousins: Dual linear code. Cousin of: Galois-qudit stabilizer code, Octacode, Stabilizer code over \(GF(4)\), Stabilizer code over \(GF(q^2)\).
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. Protection: Shift bound [5] gives a lower bound on the distance of cyclic \(q\)-ary codes. Parents: Cyclic code, Linear \(q\)-ary code, Group code. Parent of: Bose–Chaudhuri–Hocquenghem (BCH) code, Dodecacode, \(q\)-ary duadic code, \(q\)-ary parity-check code. Cousin of: Galois-qudit CSS code, Generalized RM (GRM) code, Quantum maximum-distance-separable (MDS) code, Reed-Solomon (RS) code, \(q\)-ary Hamming code.
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~. \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. Protection: Riemann-Roch theorem yields code length \(n\), dimension \(k\), and a lower bound on distance in terms of features of \(L\) and genus of the curve \(\cal X\) ([6], Thm. 15.3.12). The order or Feng-Rao bound, a generalization of the shift bound for cyclic codes, gives a lower bound on the distance of evaluation AG codes [7][8][9]. Connection to semigroups yields another bound [10][11]. Parents: Linear \(q\)-ary code, Algebraic-geometry (AG) code, Evaluation code. Parent of: Elliptic code, Generalized RS (GRS) code, Hermitian code, Hexacode, Klein-quartic code, Plane-curve code, Residue AG code. Cousin of: Polynomial evaluation code.
Folded RS (FRS) code[12] 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} \end{align} Parents: Linear \(q\)-ary code. Parent of: Reed-Solomon (RS) code. Cousin of: Parvaresh-Vardy (PV) code.
Gabidulin code[13][14] Also called a vector rank-metric code. A linear code over \(GF(q^N)\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(GF(q^N)\) can be written as an \(N\)-dimensional vector with coefficients in \(GF(q)\), and the rank of a set of elements is rank of the matrix formed by their coefficients. Protection: Set of vectors \(\{x_1, x_2, \ldots, x_M\}\) determines a rank code with distance \(d=\min d(x_i, x_j)\). The code with distance \(d\) corrects all errors with rank of the error not greater than \(\lfloor (d-1)/2\rfloor\). Parents: Linear \(q\)-ary code, Rank-metric code. Cousins: Maximum-rank distance (MRD) code.
Generalized RM (GRM) code[15][16][17] 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)\). Protection: Code parameters for specific \(m,r\) are given in Ref. [18], pg. 46. Parents: Linear \(q\)-ary code, Polynomial evaluation code, Matrix-product code. Parent of: Projective RM (PRM) code. Cousins: Reed-Muller (RM) code, Cyclic linear \(q\)-ary code, Extended GRS code. Cousin of: \(q\)-ary Hamming code.
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{split} 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{split}\right)~. \end{align} Parents: Linear \(q\)-ary code. Parent of: Parvaresh-Vardy (PV) code, Reed-Solomon (RS) code.
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. Protection: Distance \(d\) is \(n\) minus the maximum number of points that are contained in a hyperplane. For \(n \geq 3\), a code is projective if and only if the distance of its dual code is at least three. Parents: Linear \(q\)-ary code. Parent of: Denniston code, Hexacode, Incidence-matrix projective code, Simplex code. Cousins: Evaluation code, Extended GRS code, Griesmer code, Anticode. Cousin of: Hamming code, Maximum distance separable (MDS) code, Projective RM (PRM) code, Ternary Golay Code, \(q\)-ary Hamming code.
\(q\)-ary Hamming code[20] 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\). Protection: Can detect 1-bit and 2-bit errors, and can correct 1-dit errors. Parents: Linear \(q\)-ary code, Perfect code. Cousins: Projective geometry code, Cyclic linear \(q\)-ary code, Binary BCH code, Generalized RM (GRM) code. Cousin of: Hamming code, Simplex 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~. \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. Protection: Riemann-Roch theorem yields code length \(n\), dimension \(k\), and a lower bound on distance in terms of features of \(L\) and genus of the curve \(\cal X\) ([6], Corr. 15.3.13). Distance bounds can also be derived from how an algebraic curve \(\cal X\) is embedded in the ambient projective space [21]. Parents: Algebraic-geometry (AG) code, Evaluation AG code. Parent of: Cartier code, Tsfasman-Vladut-Zink (TVZ) code.
Nonlinear AG code[22][23][24][25][26] Nonlinear \(q\)-ary code constructed by evaluating functions on an algebraic curve. Parents: Algebraic-geometry (AG) code.
Bose–Chaudhuri–Hocquenghem (BCH) code[27] 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\). Protection: By the BCH bound, BCH code with designed distance \(\delta\) has true minimum distance \(d\geq\delta\). BCH codes with different designed distances may coincide, and the largest possible designed distance for a given code is the Bose distance; the true distance may still be larger than that. Parents: Generalized RS (GRS) code, Cyclic linear \(q\)-ary code. Cousins: Classical Goppa code. Cousin of: Binary BCH code, Galois-qudit BCH code, Qubit BCH code, Reed-Solomon (RS) code.
Dodecacode[28][29] Self-dual \([12,6,6]_{GF(4)}\) code whose codewords are cyclic permutations of \((\omega 10100100101)\), where \(GF(4)=\{0,1,\omega,\bar{\omega}\}\). Parents: Cyclic linear \(q\)-ary code. Cousins: Dual linear code.
\(q\)-ary duadic code[30][31][32][33] 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\) [31]. Parents: Cyclic linear \(q\)-ary code. Parent of: \(q\)-ary quadratic-residue (QR) code. Cousin of: Binary duadic code.
\(q\)-ary parity-check code Also known as a sum-zero code. An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check digit such that the sum over all coordinates of each codeword is zero. Parents: Reed-Solomon (RS) code, Cyclic linear \(q\)-ary code, Maximum distance separable (MDS) code. Cousins: Low-density generator-matrix (LDGM) code. Cousin of: Parity-check code.
Hexacode[34] The \([6,3,4]_{GF(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}~, \end{align} where \(GF(4) = \{0,1,\omega, \bar{\omega}\}\). Has connections to projective geometry, lattices [34] and conformal field theory [35]. Parents: Evaluation AG code, Projective geometry code, \(q\)-ary quadratic-residue (QR) code, Denniston code, Maximum distance separable (MDS) code. Cousins: Five-qubit perfect code, Dual linear code, Golay code.
Ternary Golay Code[20] A \([11,6,5]_{GF(3)}\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [34] and sporadic simple groups [36]. 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. Parents: Perfect code, \(q\)-ary quadratic-residue (QR) code. Cousins: Golay code, Dual linear code, Projective geometry code, Divisible code. Cousin of: Tetracode.
Elliptic code Evaluation AG code of rational functions evaluated on points lying on an elliptic curve, i.e., a curve of genus one. Parents: Evaluation AG code. Cousins: Maximum distance separable (MDS) code.
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)~. \end{align} Protection: The code can detect \(n-k\) errors, and can correct errors \( \left\lfloor (n-k)/2\right\rfloor \) errors. Parents: Evaluation AG code, Polynomial evaluation code. Parent of: Alternant code, Bose–Chaudhuri–Hocquenghem (BCH) code, Classical Goppa code, Extended GRS code, Hermitian code, Reed-Solomon (RS) code. Cousins: Maximum distance separable (MDS) code, Distributed-storage code. Cousin of: Binary BCH code, Galois-qudit GRS code.
Hermitian code[37][38] 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\). Protection: Distance determined by properties of the Hermitian curve, the underlying field, and the functions used [39]; see Ref. [11], Sec. 5.3, for an example. For evaluations of polynomials up to degree \(D\), the Hermitian code protects against at least \(n - (q+1)D\) errors whenever \(D < q + 1 \). If \(D \geq q+1 \), the Hermitian code protects against at least \(n-k - \frac{q(q-1)}{2} + 1\) errors. Parents: Generalized RS (GRS) code, Evaluation AG code. Cousin of: Hermitian-hypersurface code.
Klein-quartic code[40] 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\) ([11], Ex. 2.75). Protection: Dimension \(k=8\) and distance \(d \geq 13\). Concatenation with the \([4,3,2]\) single parity check code, conversion to a binary code by expressing \(GF(8)\) elements as vectors over \(GF(2)\), and puncturing yields a \([91,24,25]\) binary code that held the world record for codes of length 91 [41]. Parents: Evaluation AG code.
Plane-curve code[42] Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine plane curve. Protection: Bezout's theorem yields parameters \([n,k,d]\), which depend on the polynomial used to define the plane curve as well as the maximum degree of the polynomials used for evaluation ([11], pg. 883). Distance bounds can be derived from how the plane curve is embedded in the ambient projective space ([21], Thm. 4.1). Parents: Evaluation AG code.
Reed-Solomon (RS) code[43][44] 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}. \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) \,. \end{align} Protection: Since each polynomial \(f_{\mu}\) is of degree less than \(k\), it can be determined from its values at \(k\) points. This means that RS codes can correct erasures on up to \(n-k\) registers. The resulting distance, \(d=n-k+1\), saturates the Singleton bound. Parents: Generalized RS (GRS) code, Interleaved RS (IRS) code, Folded RS (FRS) code. Parent of: \(q\)-ary parity-check code. Cousins: Maximum distance separable (MDS) code, Bose–Chaudhuri–Hocquenghem (BCH) code, Cyclic linear \(q\)-ary code. Cousin of: Approximate secret-sharing code, Convolutional code, Galois-qudit RS code, Justesen code, Maximum-rank distance (MRD) code, Quantum Reed-Solomon code, Rank-modulation code.
Cartier code[45] Subcode of a certain residue AG code that is constructed using the Cartier operator. Parents: Residue AG code. Parent of: Classical Goppa code.
Tsfasman-Vladut-Zink (TVZ) code[46] 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. Parents: Residue AG code.
Projective RM (PRM) code[47][48] 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 [49] \begin{align} \left[ q^m+q^{m-1}\cdots +1, {m+r \choose r},(q+1-r)q^{m-1} \right]~. \end{align} Parents: Generalized RM (GRM) code. Cousins: Projective geometry code, Griesmer code.
Parvaresh-Vardy (PV) code[50] 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. Parents: Interleaved RS (IRS) code. Cousins: Folded RS (FRS) code.
Denniston code[51] 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. Parents: Projective geometry code, Griesmer code. Parent of: Hexacode.
Incidence-matrix projective code[52][53][54] 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 ([55][56]; [6], Sec. 14.4). Parents: Projective geometry code.
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\). Parents: Projective geometry code, Griesmer code, Constant-weight code. Parent of: Tetracode. Cousins: Extended GRS code, Repetition code, \(q\)-ary Hamming code, Reed-Muller (RM) code.
Tetracode[34] The \([4,2,3]_{GF(3)}\) self-dual MDS code with generator matrix \begin{align} \begin{pmatrix}1 & 0 & 1 & 1\\ 0 & 1 & 1 & 2 \end{pmatrix}~, \end{align} where \(GF(3) = \{0,1,2\}\). Has connections to lattices [34]. Parents: Simplex code, Hamming code, Maximum distance separable (MDS) code. Cousins: Dual linear code, Ternary Golay Code.
\(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\). Parents: \(q\)-ary duadic code. Parent of: Hexacode, Ternary Golay Code. Cousin of: Binary quadratic-residue (QR) code.
Alternant code[57] 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\). Parents: Generalized RS (GRS) code.
Classical Goppa code[58][59][60] 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} \). Protection: The length \( n = |L| \) , dimension \( k \geq n-mr \) where \( r = \text{deg} G(x) \), and the minimum distance \( d \geq r +1 \). Parents: Generalized RS (GRS) code, Cartier code. Cousin of: Binary quantum Goppa code, Bose–Chaudhuri–Hocquenghem (BCH) code.
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. Parents: Generalized RS (GRS) code. Cousins: Maximum distance separable (MDS) code. Cousin of: Generalized RM (GRM) code, Projective geometry code, Simplex code.

References

[1]
V. D. Goppa, “Codes Associated with Divisors”, Probl. Peredachi Inf., 13:1 (1977), 33–39; Problems Inform. Transmission, 13:1 (1977), 22–27
[2]
V. D. Goppa, “Codes on algebraic curves”, Dokl. Akad. Nauk SSSR, 259:6 (1981), 1289–1290
[3]
V. D. Goppa, “Algebraico-geometric codes”, Izv. Akad. Nauk SSSR Ser. Mat., 46:4 (1982), 762–781; Izv. Math., 21:1 (1983), 75–91
[4]
T. Blackmore and G. H. Norton, “Matrix-Product Codes over ? q”, Applicable Algebra in Engineering, Communication and Computing 12, 477 (2001). DOI
[5]
J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986). DOI
[6]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[7]
G.-L. Feng and T. R. N. Rao, “Decoding algebraic-geometric codes up to the designed minimum distance”, IEEE Transactions on Information Theory 39, 37 (1993). DOI
[8]
R. Pellikaan, “The shift bound for cyclic, Reed-Muller and geometric Goppa codes”, Arithmetic, Geometry, and Coding Theory. DOI
[9]
P. Beelen, “The order bound for general algebraic geometric codes”, Finite Fields and Their Applications 13, 665 (2007). DOI
[10]
T. Johnsen, S. Manshadi, and N. Monzavi, “A determination of the parameters of a large class of Goppa codes”, IEEE Transactions on Information Theory 40, 1678 (1994). DOI
[11]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[12]
V. Y. Krachkovsky, “Reed-solomon codes for correcting phased error bursts”, IEEE Transactions on Information Theory 49, 2975 (2003). DOI
[13]
E. M. Gabidulin, Theory of Codes with Maximum Rank Distance, Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
[14]
R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction”, IEEE Transactions on Information Theory 37, 328 (1991). DOI
[15]
T. Kasami, Shu Lin, and W. Peterson, “New generalizations of the Reed-Muller codes--I: Primitive codes”, IEEE Transactions on Information Theory 14, 189 (1968). DOI
[16]
E. Weldon, “New generalizations of the Reed-Muller codes--II: Nonprimitive codes”, IEEE Transactions on Information Theory 14, 199 (1968). DOI
[17]
P. Delsarte, J. M. Goethals, and F. J. Mac Williams, “On generalized ReedMuller codes and their relatives”, Information and Control 16, 403 (1970). DOI
[18]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
[19]
J. L. Massey, Threshold Decoding. Cambridge, MA: M.I.T. Press, 1963.
[20]
M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
[21]
A. Couvreur, “The dual minimum distance of arbitrary-dimensional algebraic–geometric codes”, Journal of Algebra 350, 84 (2012). DOI; 0905.2345
[22]
Noam D. Elkies, “Excellent nonlinear codes from modular curves”. math/0104115
[23]
Chaoping Xing, “Nonlinear codes from algebraic curves improving the Tsfasman-Vladut-Zink bound”, IEEE Transactions on Information Theory 49, 1653 (2003). DOI
[24]
Noam D. Elkies, “Still better nonlinear codes from modular curves”. math/0308046
[25]
H. Niederreiter and F. Özbudak, “Constructive Asymptotic Codes with an Improvement on the Tsfasman-Vlăduţ-Zink and Xing Bounds”, Coding, Cryptography and Combinatorics 259 (2004). DOI
[26]
H. Stichtenoth and C. Xing, “Excellent Nonlinear Codes From Algebraic Function Fields”, IEEE Transactions on Information Theory 51, 4044 (2005). DOI
[27]
D. Gorenstein and N. Zierler, “A Class of Error-Correcting Codes in $p^m $ Symbols”, Journal of the Society for Industrial and Applied Mathematics 9, 207 (1961). DOI
[28]
A. R. Calderbank et al., “Quantum Error Correction via Codes over GF(4)”. quant-ph/9608006
[29]
Gerald Hoehn, “Self-dual Codes over the Kleinian Four Group”. math/0005266
[30]
V. Pless, “Q-codes”, Journal of Combinatorial Theory, Series A 43, 258 (1986). DOI
[31]
V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993). DOI
[32]
J. J. Rushanan, Topics in Integral Matrices and Abelian Group Codes, California Institute of Technology, 1986. DOI
[33]
M. Smid, “Duadic codes (Corresp.)”, IEEE Transactions on Information Theory 33, 432 (1987). DOI
[34]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999). DOI
[35]
J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020). DOI; 2003.13700
[36]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[37]
H. Stichtenoth, “�ber die Automorphismengruppe eines algebraischen Funktionenk�rpers von Primzahlcharakteristik”, Archiv der Mathematik 24, 527 (1973). DOI
[38]
H. Tiersma, “Remarks on codes from Hermitian curves (Corresp.)”, IEEE Transactions on Information Theory 33, 605 (1987). DOI
[39]
K. Yang and P. V. Kumar, “On the true minimum distance of Hermitian codes”, Lecture Notes in Mathematics 99 (1992). DOI
[40]
J. Hansen, “Codes on the Klein quartic, ideals, and decoding (Corresp.)”, IEEE Transactions on Information Theory 33, 923 (1987). DOI
[41]
A. M. Barg, G. L. Katsman, M. A. Tsfasman, “Algebraic-Geometric Codes from Curves of Small Genus”, Probl. Peredachi Inf., 23:1 (1987), 42–46; Problems Inform. Transmission, 23:1 (1987), 34–38
[42]
J. Justesen et al., “Construction and decoding of a class of algebraic geometry codes”, IEEE Transactions on Information Theory 35, 811 (1989). DOI
[43]
K. A. Bush, “Orthogonal Arrays of Index Unity”, The Annals of Mathematical Statistics 23, 426 (1952). DOI
[44]
I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields”, Journal of the Society for Industrial and Applied Mathematics 8, 300 (1960). DOI
[45]
Alain Couvreur, “Codes and the Cartier Operator”. 1206.4728
[46]
M. A. Tsfasman, S. G. Vlădutx, and T. Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound”, Mathematische Nachrichten 109, 21 (1982). DOI
[47]
G. Lachaud, “The parameters of projective Reed–Müller codes”, Discrete Mathematics 81, 217 (1990). DOI
[48]
A. B. Sorensen, “Projective Reed-Muller codes”, IEEE Transactions on Information Theory 37, 1567 (1991). DOI
[49]
G. Lachaud, “Number of points of plane sections and linear codes defined on algebraic varieties”, Arithmetic, Geometry, and Coding Theory. DOI
[50]
F. Parvaresh and A. Vardy, “Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). DOI
[51]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016). DOI
[52]
E. Prange, The use of coset equivalene in the analysis and decoding of group codes. AIR FORCE CAMBRIDGE RESEARCH LABS HANSCOM AFB MA, 1959.
[53]
L. Rudolph, “A class of majority logic decodable codes (Corresp.)”, IEEE Transactions on Information Theory 13, 305 (1967). DOI
[54]
E. Prange, "Some cyclic error-correcting codes with simple decoding algorithms." AFCRC-TN-58-156 (1985).
[55]
B. Bagchi and S. P. Inamdar, “Projective Geometric Codes”, Journal of Combinatorial Theory, Series A 99, 128 (2002). DOI
[56]
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).
[57]
H. J. Helgert, “Alternant codes”, Information and Control 26, 369 (1974). DOI
[58]
V. D. Goppa, "A new class of linear error-correcting codes", Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970.
[59]
V. D. Goppa, "Rational representation of codes and (Lg) codes", Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971.
[60]
E. Berlekamp, “Goppa codes”, IEEE Transactions on Information Theory 19, 590 (1973). DOI