Linear \(q\)-ary code

Description

An \((n,K,d)_q\) linear code is denoted as \([n,k,d]_q\), where \(k=\log_{q}K\) need not be an integer. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(\alpha x+ \beta y\) is also a codeword for any \(q\)-ary digits \(\alpha,\beta\).

Linear codes can be defined in terms of a generator matrix \(G\), whose rows form a basis for the \(k\)-dimensional codespace. Given a codeword \(x\), the corresponding encoded codeword is \(G^T x\). The generator matrix can be reduced via coordinate permutations to its standard or systematic form \(G = [I_k~~A]\), where \(I_k\) is a \(k\times k\) identity matrix and \(A\) is a \(k \times (n-k)\) \(q\)-ary matrix.

Protection

Distance \(d\) of a linear code is the number of nonzero entries in the (nonzero) codeword with the smallest such number. Corrects any error set such that the difference of any pair of distinct elements of the set is a codeword.

Decoding

Random linear codes over large fields are list-recoverable and list-decodable up to near-optimal rates [1].

Notes

Admits a parity check matrix \(H\), whose columns make up a maximal linearly independent set of vectors that are in the kernel of \(G\).

Parent

  • Additive \(q\)-ary code — For \(q>2\), additive codes need not be linear since linearity also requires closure under multiplication.

Children

Cousins

Zoo code information

Internal code ID: q-ary_linear

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: q-ary_linear

Cite as:
“Linear \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_linear
BibTeX:
@incollection{eczoo_q-ary_linear, title={Linear \(q\)-ary code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/q-ary_linear} }
Permanent link:
https://errorcorrectionzoo.org/c/q-ary_linear

References

[1]
Atri Rudra and Mary Wootters, “Average-radius list-recovery of random linear codes: it really ties the room together”. 1704.02420

Cite as:

“Linear \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_linear

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