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 message \(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

Soft-decision maximum-likelihood trellis-based decoder [1].Random linear codes over large fields are list-recoverable and list-decodable up to near-optimal rates [2].Extensions of algebraic-geometry decoders to linear codes [3][4].

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\).University of Salzburg's MinT application generates an optimal parameter table for a linear code \([n,k,d]_q\), contingent on an optional fluctuation of maximal Hamming code distance, rank, and length, along with other specifications.

Parents

Children

Cousins

  • \(q\)-ary linear LTC — Linear \(q\)-ary codes with distances \(\frac{1}{2}n-\sqrt{t n}\) for some \(t\) are called almost-orthogonal and are locally testable with query complexity of order \(O(t)\) [7]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [8], provided that the number of codewords is polynomial in \(n\).
  • Entanglement-assisted (EA) QECC — Any linear \(q\)-ary code can be used to construct an EAQECC.
  • Entanglement-assisted (EA) stabilizer code — Any linear quaternary (\(q=4\)) code can be used to construct an EA stabilizer code.
  • Evaluation code — Evaluation codes are defined using polynomial or rational functions evaluated on a subset of affine or projective space. Given access to more general structures (i.e., morphisms of algebras), any \(q\)-ary linear code can be formulated as an evaluation code ([9], Sec. 4.1; [10], Prop. 1.1.4).
  • Galois-qudit CSS code — Construction uses two related \(q\)-ary linear codes \(C_X\) and \(C_Z\).
  • Modular-qudit CSS code — Construction for prime \(q=p\) uses two related \(p\)-ary linear codes \(C_X\) and \(C_Z\).
  • True Galois-qudit stabilizer code — A true Galois-qudit stabilizer code is the closest quantum analogue of a linear code over \(GF(q)\) because the \(q\)-ary vectors corresponding to the symplectic representation of the stabilizers form a linear subspace.

References

[1]
J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis”, IEEE Transactions on Information Theory 24, 76 (1978). DOI
[2]
Atri Rudra and Mary Wootters, “Average-radius list-recovery of random linear codes: it really ties the room together”. 1704.02420
[3]
R. Kotter. A unified description of an error locating procedure for linear codes. In D. Yorgov, editor, Proc. 3rd International Workshop on Algebraic and Combinatorial Coding Theory, pages 113–117, Voneshta Voda, Bulgaria, June 1992. Hermes.
[4]
R. Pellikaan, “On decoding by error location and dependent sets of error positions”, Discrete Mathematics 106-107, 369 (1992). DOI
[5]
R. Pellikan, B.-Z. Shen, and G. J. M. van Wee, “Which linear codes are algebraic-geometric?”, IEEE Transactions on Information Theory 37, 583 (1991). DOI
[6]
I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001). DOI
[7]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). DOI
[8]
T. Kaufman and M. Sudan, “Sparse Random Linear Codes are Locally Decodable and Testable”, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) (2007). DOI
[9]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[10]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
Page edit log

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

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