Description
Encodes \(K\) states (codewords) in \(n\) \(q\)-ary coordinates over the field \(GF(q)\), i.e., \(q\)-ary strings. Error-correcting performance is quantified by some distance \(d\), which in turn is defined using a metric. The default distance is the Hamming distance \(d\), the weight (i.e., number of nonzero coordinates) of the lowest-weight nonzero codeword; such codes are usually denoted as \((n,K,d)_q\). The corresponding Hamming metric between two \(q\)-ary strings is the number of coordinates in which they differ. Unless stated otherwise, the distance for this class is the Hamming distance.
Two \(q\)-ary codes are equivalent if the codewords of one code can be mapped into those of the other under a combination of a coordinate permutation and a permutation of the elements of each coordinate. The full group of such composite permutations is \(S_q \wr S_n\) [2][1; Def. 1.8.8].
Protection
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. Often, the relative Hamming distance \(\delta=d/n\) is used to compare codes of different lengths.
An analogue of the Gray map and Lee weight can be defined for codes over \(GF(4)\) by identifying \((0,\omega,\bar{\omega},1)\) with \((00),(10),(01),(11)\) [3].
Noise channels
Noise channels include the symmetric noise channel, asymmetric noise channels [4–8], and insertion/deletion noise.
Weight enumerator and four fundamental parameters
Weight enumerator: 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 [9,10]; see [11; 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 [12][11; Ch. 5].
Other types of weight enumerators includes the Hamming weight enumerator, Lee weight enumerator, joint weight enumerator, split weight enumerator, and biweight enumerator [11].
Bounds on code parameters
Bounds on the parameters of an \((n,K,d)_q\) code include the Hamming a.k.a. sphere-packing bound, Singleton bound, Gilbert-Varshamov (GV) bound, Griesmer bound, Plotkin bound, Johnson bound, and various linear programming (LP) bounds; see [1]. A code whose parameters attain the Hamming bound (Singleton bound, Griesmer bound, Johnson bound, Delsarte LP bound) is called a perfect code (an MDS code, a Griesmer code, a nearly perfect code, an LP universally optimal code).
Gilbert-Varshamov (GV) bound: The Gilbert-Varshamov [13,14], or Gilbert-Shannon-Varshamov, bound states that the maximum size \(K\) of a \(q\)-ary code with distance \(d\) satisfies \begin{align} K\sum_{j=0}^{d-1}{n \choose j}(q-1)^{j}\geq q^{n}~. \tag*{(2)}\end{align} In other words, if the left-hand side of the above is less than or equal to the right-hand side, then a code with such parameters exists. The GV bound gives rise to the asymptotic GV bound (i.e., GV bound in the \(n\to\infty\) limit), expressed in terms of the maximum achievable rate \(R\) and relative distance \(\delta\), \begin{align} R\geq 1-h_{q}(\delta)~, \tag*{(3)}\end{align} where \(h_q\) is the \(q\)-ary entropy function, \begin{align} h_{q}(\delta)=-\delta\log_{q}\frac{\delta}{q-1}-(1-\delta)\log_{q}(1-\delta)~. \tag*{(4)}\end{align}
Rate
The rate of a \(q\)-ary code is usually defined as \(R=\frac{1}{n}\log_q K\) dits per symbol. The maximum rate of a \(q\)-ary code with linear distance is lower bounded by the asymptotic GV bound and upper bounded by the \(q\)-ary version of the MRRW LP bound [15].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\).Threshold
Threshold for large-alphabet circuits codes is higher than for Boolean circuits [16].Notes
Tables of bounds and examples of linear codes for various \(n\) and \(k\), extending code tables by Brouwer [17], are maintained by M. Grassl at this website.Cousins
- Matrix-based code— Elements of fields such as \(GF(p^{ml})\) can be written as \(m\)-dimensional vectors over \(GF(p^l)\) or \((m\times l)\)-dimensional matrices over \(GF(p)\). This idea is used to convert between ordinary block codes and matrix-based codes such as disk array codes and rank-metric codes.
- Combinatorial design— Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
- Constantin-Rao (CR) code— CR codes, and their special cases the VT codes, can be converted to ternary codes with nice structure via a binary-to-ternary map \(00\to 0\), \(11\to 0\), \(01\to 1\), and \(10\to 2\) [18].
- Traceability code— A \(q\)-ary code with distance \(d \geq n(1-1/t^2)\) has the \(t\)-traceability property [19; 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.
Primary Hierarchy
References
- [1]
- W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- P. Gaborit, V. Pless, P. Solé, and O. Atkin, “Type II Codes over F4”, Finite Fields and Their Applications 8, 171 (2002) DOI
- [4]
- Varshamov, R. R. "Some features of linear codes that correct asymmetric errors." Soviet Physics Doklady. Vol. 9. 1965.
- [5]
- R. Varshamov, “A class of codes for asymmetric channels and a problem from the additive theory of numbers”, IEEE Transactions on Information Theory 19, 92 (1973) DOI
- [6]
- S. D. Constantin and T. R. N. Rao, “On the theory of binary asymmetric error correcting codes”, Information and Control 40, 20 (1979) DOI
- [7]
- Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
- [8]
- T. Kløve, Codes for Error Detection (WORLD SCIENTIFIC, 2007) DOI
- [9]
- J. Macwilliams, “A Theorem on the Distribution of Weights in a Systematic Code†”, Bell System Technical Journal 42, 79 (1963) DOI
- [10]
- 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
- [11]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [12]
- P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
- [13]
- E. N. Gilbert, “A Comparison of Signalling Alphabets”, Bell System Technical Journal 31, 504 (1952) DOI
- [14]
- R. R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk SSSR Soviet Math. - Doklady 117 (1957), 739–741.
- [15]
- M. Aaltonen, “A new upper bound on nonbinary block codes”, Discrete Mathematics 83, 139 (1990) DOI
- [16]
- A. K. Tan, M. H. Ho, and I. L. Chuang, “Reliable Computation by Large-Alphabet Formulas in the Presence of Noise”, IEEE Transactions on Information Theory 70, 9152 (2024) arXiv:2306.13262 DOI
- [17]
- 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.
- [18]
- M. Grassl, P. W. Shor, G. Smith, J. Smolin, and B. Zeng, “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
- [19]
- 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
- [20]
- Lenstra, Hendrik W. "Codes from algebraic number fields." Mathematics and computer science II, Fundamental contributions in the Netherlands since 4 (1945): 94-104.1
- [21]
- Tsfasman, Michael A. "Global fields, codes and sphere packings." Journees Arithmetiques 1989,-” Asterisque 198 (1992): 199-200.
- [22]
- V. Guruswami, “Constructions of codes from number fields”, IEEE Transactions on Information Theory 49, 594 (2003) DOI
- [23]
- B. Cambou and D. Telesca, “Ternary Computing to Strengthen Cybersecurity”, Advances in Intelligent Systems and Computing 898 (2018) DOI
- [24]
- S. Assiri, B. Cambou, D. D. Booher, D. Ghanai Miandoab, and M. Mohammadinodoushan, “Key Exchange using Ternary system to Enhance Security”, 2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC) (2019) DOI
- [25]
- A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays (Springer New York, 1999) DOI
Page edit log
- Victor V. Albert (2022-02-16) — most recent
- Victor V. Albert (2021-10-29)
Cite as:
“\(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