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\). This extra structure yields much information about their properties, making them a large and well-studied subset of codes.
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. The code also comes with a parity check matrix \(H\), whose columns make up a maximal linearly independent set of vectors that are in the kernel of \(G\).
The monomial group of order \((q-1)^n n!\) is formed by \(n\)-dimensional matrices with one nonzero field element in each row and column. Two linear \(q\)-ary codes are (monomial) equivalent if the codewords of one code can be mapped into those of the other under a monomial group element [1; Ch. 8][2; Ch. 3]. The automorphism group of a linear \(q\)-ary code is the largest subgroup of the monomial group that maps the code onto itself.
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.
Geometrically local \(q\)-ary codes are limited by the classical Bravyi-Poulin-Terhal (BPT) bound [3], known to be tight in any Euclidean dimension [4].
Rate
Any code admitting a two-transitive automorphism group achieves capacity under the binary erasure channel [5–7].
Decoding
Maximum likelihood (ML) decoding. This algorithm decodes a received word to the most likely sent codeword based on the received word. ML decoding of reduced complexity is possible for virtually all \(q\)-ary linear codes [8].Optimal symbol-by-symbol decoding rule [9].Information set decoding (ISD) [10], a probabilistic decoding strategy that essentially tries to guess \(k\) correct positions in the received word, where \(k\) is the size of the code. Then, an error vector is constructed to map the received word onto the nearest codeword, assuming the \(k\) positions are error free. When the Hamming weight of the error vector is low enough, that codeword is assumed to be the intended transmission.Generalized minimum-distance decoder [11].Soft-decision maximum-likelihood trellis-based decoder [12].Random linear codes over large fields are list-recoverable and list-decodable up to near-optimal rates [13].Extensions of algebraic-geometry decoders to linear codes [14,15].
Notes
The two extreme examples of codes are the \([n,0,n]_q\) zero code and its dual the \([n,n,1]_q\) universe code.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.Julia CodingTheory framework by E. Sabo.
Parents
- Additive \(q\)-ary code — For \(q>2\), additive codes need not be linear since linearity also requires closure under multiplication.
- \(R\)-linear code — Linear \(q\)-ary codes are \(GF(q)\)-linear.
Children
- Linear binary code — Linear binary codes are linear \(q\)-ary codes for \(q=2\).
- 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 [16; Sec. 4.1][17; Prop. 1.1.4].
- Berlekamp code
- Interleaved RS (IRS) code — IRS codes are linear over \(GF(q)\) but not necessarily over \(GF(q^t)\).
- Cartier code
- Alternant code
- Pyramid code
- \(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)\) [18]. This was later improved to codes with distance \(\frac{1}{2}n-O(n^{1-\gamma})\) for any positive \(\gamma\) [19], provided that the number of codewords is polynomial in \(n\).
- Maximum distance separable (MDS) code
- \(q\)-ary linear LCC
- Dual linear code
- \(q\)-ary Hamming code
- Quasi group-algebra code — A linear code is a quasi group-algebra code for a group \(G\) and index \(\ell\) if and only if \(G\) is isomorphic to a regular subgroup of the code's permutation automorphism group which acts freely of index \(\ell\) on the coordinates [20; Thm. 3.5].
- Projective geometry code — Columns of the generator matrix of a projective linear \([n,k]_q\) code correspond to distinct nonzero points in projective space. In general, linear codes admit repeating columns or columns proportional to each other. In that case, the columns correspond to a multiset of non-distinct nonzero points, and multisets are in one-to-one correspondence to arcs in projective space ([21], Thm. 1.1).
- Classical fractal liquid code
- \(q\)-ary LDGM code
- Tanner code
- Divisible code
- Two-weight code
- Wozencraft ensemble code
Cousins
- Rank-modulation code — Almost all linear \(q\)-ary codes can be converted to rank-modulation codes [22].
- Gabidulin code — Gabidulin codes over \(GF(q^N)\), when expressed as vectors over \(GF(q^N)\), are linear \(q\)-ary codes.
- Locally recoverable code (LRC) — A \(q\)-ary linear code is an LRC of locality \(r\) if each coordinate participates in at least one parity check of weight \(\leq r\) [23][24; Sec. 31.3.4.5].
- Evaluation AG code — The degree of the divisor for evaluation AG codes is restricted to be less than \(n\). When there is no restriction, any \(q\)-ary linear code can be formulated as an evaluation AG code [25].
- Generalized RS (GRS) code — Concatenations of GRS codes with random linear codes almost surely attain the GV bound [26].
- EA qubit stabilizer code — Any linear quaternary linear code can be used to construct an EA qubit stabilizer code [27].
- Galois-qudit CSS code — The Galois-qudit CSS construction uses two related \(q\)-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 Galois symplectic representation of the stabilizers form a linear subspace.
- Galois-qudit HGP code — Galois-qudit HGP codes are constructed out of two classical linear \(q\)-ary codes.
References
- [1]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [2]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [3]
- S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for Reliable Quantum Information Storage in 2D Systems”, Physical Review Letters 104, (2010) arXiv:0909.5200 DOI
- [4]
- N. Baspin, “On combinatorial structures in linear codes”, (2023) arXiv:2309.16411
- [5]
- S. Kumar and H. D. Pfister, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2015) arXiv:1505.05123
- [6]
- S. Kudekar et al., “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2016) arXiv:1601.04689
- [7]
- K. Ivanov and R. L. Urbanke, “Capacity-achieving codes: a review on double transitivity”, (2020) arXiv:2010.15453
- [8]
- I. Dumer, “Maximum likelihood decoding with reduced complexity”, Proceedings of IEEE International Symposium on Information Theory DOI
- [9]
- C. Hartmann and L. Rudolph, “An optimum symbol-by-symbol decoding rule for linear codes”, IEEE Transactions on Information Theory 22, 514 (1976) DOI
- [10]
- C. Peters, “Information-Set Decoding for Linear Codes over F q”, Post-Quantum Cryptography 81 (2010) DOI
- [11]
- G. Forney, “Generalized minimum distance decoding”, IEEE Transactions on Information Theory 12, 125 (1966) DOI
- [12]
- J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis”, IEEE Transactions on Information Theory 24, 76 (1978) DOI
- [13]
- A. Rudra and M. Wootters, “Average-radius list-recovery of random linear codes: it really ties the room together”, (2017) arXiv:1704.02420
- [14]
- 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.
- [15]
- R. Pellikaan, “On decoding by error location and dependent sets of error positions”, Discrete Mathematics 106–107, 369 (1992) DOI
- [16]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [17]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [18]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
- [19]
- 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
- [20]
- M. Borello and W. Willems, “On the algebraic structure of quasi group codes”, (2021) arXiv:1912.09167
- [21]
- I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001) DOI
- [22]
- A. Mazumdar, A. Barg, and G. Zémor, “Constructions of Rank Modulation Codes”, (2011) arXiv:1110.2557
- [23]
- L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
- [24]
- V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, "Codes for Distributed Storage." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [25]
- 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
- [26]
- C. Thommesen, “The existence of binary linear concatenated codes with Reed - Solomon outer codes which asymptotically meet the Gilbert- Varshamov bound”, IEEE Transactions on Information Theory 29, 850 (1983) DOI
- [27]
- T. Brun, I. Devetak, and M.-H. Hsieh, “Correcting Quantum Errors with Entanglement”, Science 314, 436 (2006) arXiv:quant-ph/0610092 DOI
Page edit log
- Victor V. Albert (2022-08-04) — most recent
- Micah Shaw (2022-06-08)
- Victor V. Albert (2022-03-21)
- Victor V. Albert (2021-10-30)
Cite as:
“Linear \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_linear