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.

References

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