Root code for 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
- Additive \(q\)-ary code
- Algebraic-geometry (AG) code
- Weighed-covering code
- Locally recoverable code (LRC) — Locally recoverable codes protect against coordinate erasure.
- One-versus-one (OVO) code
- Identifiable parent property (IPP) code
- Matrix-product code
- Orthogonal array
- Subspace design code
- Universally optimal \(q\)-ary code
- Balanced code

## Cousins

- Combinatorial design code — Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
- Convolutional code — Convolutional codes for finite block size are \(q\)-ary codes.
- 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”, Journal of Algebra and Its Applications (2023) arXiv:2212.00431 DOI
- [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