Galois-field \(q\)-ary code
This code defines the Galois-field Kingdom
Description
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
The standard metric for Galois-field \(q\)-ary codes is the Hamming metric, but other metrics also exist [1]. 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.
Rate
The rate of a \(q\)-ary code is usually defined as \(R=\frac{1}{n}\log_{q}K\) dits per symbol.
Decoding
For small \(n\), decoding can be based on a lookup table. For infinite code families, the size of such a table scales exponentially with \(n\), so approximate decoding algorithms scaling polynomially with \(n\) have to be used. The decoder determining the most likely error given a noise channel is called the maximum-likelihood decoder.Given a received string \(x\) and an error bound \(e\), a list decoder returns a list of all codewords that are at most \(e\) from \(x\). The number of codewords in a neighborhood of \(x\) has to be polynomial in \(n\) in order for this decoder to run in time polynomial in \(n\).
Notes
Tables of bounds and examples of linear codes for various \(n\) and \(k\), extending code tables by Brouwer [2], are maintained by M. Grassl at this website.
Parent
- Ring code — Galois fields are rings under addition.
Children
- Binary code
- Algebraic-geometry (AG) code
- Convolutional code — Convolutional codes for finite block size are \(q\)-ary codes.
- Weighed-covering code
- Locally recoverable code (LRC) — Locally recoverable codes protect against coordinate erasure.
- Identifiable parent property (IPP) code
- Matrix-product code
- Additive \(q\)-ary code
- Universally optimal \(q\)-ary code
- Divisible code
Cousin
- Polyphase code — Polyphase codes are spherical codes that can be obtained from \(q\)-ary codes.
References
- [1]
- M. Grassl, A.-L. Horlemann, and V. Weger, “The Subfield Metric and its Application to Quantum Error Correction”, (2022) arXiv:2212.00431
- [2]
- Andries E. Brouwer, Bounds on linear codes, in: Vera S. Pless and W. Cary Huffman (Eds.), Handbook of Coding Theory, pp. 295-461, Elsevier, 1998.
Page edit log
- Victor V. Albert (2022-02-16) — most recent
- Victor V. Albert (2021-10-29)
Cite as:
“Galois-field \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_digits_into_q-ary_digits