Galois-field \(q\)-ary code 

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]. A code 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.

Weight enumerator and four fundamental parameters: Determining protection and bounds on code parameters can also be done using the code's weight enumerator (cf. quantum weight enumerators), \begin{align} \begin{split} A(x,y)&=\sum_{j=0}^{n}A_{j}x^{n-j}y^{j}\\ A_{j}&=\text{number of wt-}j\text{ codewords}~. \end{split} \tag*{(1)}\end{align} The weight enumerator and it's Fourier transform the dual weight enumerator satisfy the MacWilliams identity [2,3]; see [4; Ch. 5].

The distance of the code is the value of the first nonzero coefficient \(A_j\), while the dual distance is the first nonzero coefficient of the dual weight enumerator. The number of the code is the number of nonzero \(A_j\)'s, corresponding to the number of distinct nonzero distances between codewords. The external distance is the number of nonzero coefficients of the dual weight enumerator. The distance, dual distance, number and external distance make up the four fundamental parameters of a code [5][4; Ch. 5].

Other types of weight enumerators includes the Hamming weight enumerator, Lee weight enumerator, joint weight enumerator, split weight enumerator, and biweight enumerator [4].

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

Parent

  • Ring code — Galois fields are rings under addition.

Children

Cousins

  • Combinatorial design — Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
  • Traceability code — A \(q\)-ary code with distance \(d \geq n(1-1/t^2)\) has the \(t\)-traceability property [7; Thm. 4.3].
  • 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]
J. Macwilliams, “A Theorem on the Distribution of Weights in a Systematic Code†”, Bell System Technical Journal 42, 79 (1963) DOI
[3]
F. J. MacWilliams, N. J. A. Sloane, and J.-M. Goethals, “The MacWilliams Identities for Nonlinear Codes”, Bell System Technical Journal 51, 803 (1972) DOI
[4]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[5]
P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
[6]
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.
[7]
J. N. Staddon, D. R. Stinson, and Ruizhong Wei, “Combinatorial properties of frameproof and traceability codes”, IEEE Transactions on Information Theory 47, 1042 (2001) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/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

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