Galois-field \(q\)-ary code

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

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.

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 [1], are maintained by M. Grassl at this website.

Parent

Child

Zoo code information

Internal code ID: q-ary_digits_into_q-ary_digits

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: q-ary_digits_into_q-ary_digits

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
BibTeX:
@incollection{eczoo_q-ary_digits_into_q-ary_digits, title={Galois-field \(q\)-ary code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/q-ary_digits_into_q-ary_digits} }
Permanent link:
https://errorcorrectionzoo.org/c/q-ary_digits_into_q-ary_digits

References

[1]
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.

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/q-ary_digits_into_q-ary_digits.yml.