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: Algebraic-geometry (AG) code.
Reed-Solomon (RS) code[2][3] An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). Let \(\{\alpha_1,\cdots,\alpha_n\}\) be \(n\) distinct nonzero elements of \(GF(q)\) with \(q>n\). An RS code encodes \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(\alpha_1),\cdots,f_\mu(\alpha_n)\}\), with polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \end{align} In other words, each codeword \(\mu\) is a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\). 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 Reed-Solomon (GRS) code, Maximum distance separable (MDS) code. Parent of: Extended RS code, Folded RS code. Cousins: Hamming code, Bose–Chaudhuri–Hocquenghem (BCH) code, Cyclic code. Cousin of: Approximate secret-sharing code, Convolutional code, Galois-qudit polynomial code (QPyC), Justesen code, Maximum-rank distance (MRD) code, Prime-qudit polynomial code (QPyC), Rank-modulation code.
Residue AG code Also called a differential code. Stub. Parents: Algebraic-geometry (AG) code. Parent of: Goppa code. Cousins: Evaluation AG code.
Goppa code[5][6][7] Let \( G(z) \) 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]\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(z) =0 \) modulo \(G(z)\), where \( R_a(z) = \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(z) \), and the minimum distance \( d \geq r +1 \). Parents: Generalized Reed-Solomon (GRS) code, Residue AG code. Cousin of: Binary quantum Goppa code.
Extended RS code Stub. If \(f\in \mathcal{P}_k\) with \(k<q\), then \(\sum_{\alpha\in\mathbb{F}_q}f(\alpha)=0\) which implies RS codes are odd-like. Hence, by adding a parity check coordinate with evaluation point \(\alpha_0=0\) to an RS code on \(q-1\) registers, the distance increases to \(\hat{d}=d+1\). This addition yields an \([q,k,q-k+1]\) extended RS code. Parents: Reed-Solomon (RS) code.


F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977
K. A. Bush, “Orthogonal Arrays of Index Unity”, The Annals of Mathematical Statistics 23, 426 (1952). DOI
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
R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes”, Information and Control 3, 68 (1960). DOI
V. D. Goppa, "A new class of linear error-correcting codes", Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970.
V. D. Goppa, "Rational representation of codes and (Lg) codes", Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971.
E. Berlekamp, “Goppa codes”, IEEE Transactions on Information Theory 19, 590 (1973). DOI