Description
Encodes \(K\) states (codewords) in \(n\) \(q\)-ary coordinates over the field \(GF(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.
Finite fields
Finite fields: Galois or finite fields \(GF(q)=\mathbb{F}_q\) are sets of \(q\) elements closed under addition and multiplication. They are finite analogues of the real or complex numbers, and a unique field exists for every power \(q=p^m\) of a prime \(p\). The prime-field case reduces to \(\mathbb{Z}_p\), a group under addition that is promoted to a field by defining multiplication modulo \(p\). Every finite field comes with a 0 element (additive identity), a 1 element (multiplicative identity), and additive (multiplicative) inverses for all (nonzero) elements. An element whose powers exhaust all nonzero field elements is called primitive. Fields come with a trace operation, the field trace, which maps elements \(\gamma \in GF(q)\) to elements of \(GF(p)\) as \begin{align} \text{tr}(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~. \tag*{(1)}\end{align} The field trace can be thought of as an averaging over the field's Galois group, which is the cyclic group generated by \(\gamma\to\gamma^p\) [1; pg. 113]. Fields also come with a field norm, \begin{align} N(\gamma)=\prod_{k=0}^{m-1}\gamma^{p^{k}}=\gamma^{(p^{m}-1)/(p-1)}~. \tag*{(2)}\end{align} In the case of the complex numbers, analogues of the field trace and field norm are the real part and norm squared of a complex number, respectively.
Any field \(GF(q)\) can be thought of as an \(m\)-dimensional vector space over \(GF(p)\) a.k.a. the \(m\)th extension of \(GF(p)\) (similar to the complex numbers being an extension of the reals). More generally, 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. The field norm and field trace can likewise be defined for fields \(GF(q^m)\) that are extensions of \(GF(q)\) for non-prime \(q\).
An example of a field is the quaternary Galois field \(GF(4) = \{0,1,\omega, \omega^2=\bar{\omega}\}\) with \(p=m=2\). In this case, \(\omega\) can be interpreted as a third root of unity, but more formally it is defined as a solution to the polynomial equation \(1+x+x^2=0\). Field elements can be represented as two-dimensional vectors with binary elements, \(GF(4)=GF(2^2)\), using the basis \(1\cong(1,0)\) and \(\omega\cong(0,1)\): \begin{align} 0&\leftrightarrow(0,0)\cong0\cdot1+0\cdot\omega\tag*{(3)}\\1&\leftrightarrow(0,1)\cong0\cdot1+1\cdot\omega\tag*{(4)}\\\omega&\leftrightarrow(1,1)\cong1\cdot1+1\cdot\omega\tag*{(5)}\\\bar{\omega}&\leftrightarrow(1,0)\cong1\cdot1+0\cdot\omega~. \tag*{(6)}\end{align} In this way, the field elements form the Klein four group \(\mathbb{Z}_2\times\mathbb{Z}_2\) under addition. One can check that the trace operation, \(\text{tr}(\gamma) = \gamma + \gamma^2\), outputs either 0 or 1 for any element \(\gamma\in GF(4)\).
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\) [3][2; Def. 1.8.8].
Protection
The standard metric for Galois-field \(q\)-ary codes is the Hamming metric, but other metrics also exist [4]. 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 distance \(\delta=d/n\) is used to compare codes of different lengths.
Noise channels
Noise channels include the symmetric noise channel, asymmetric noise channels [5–9], 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*{(7)}\end{align} The weight enumerator and it's Fourier transform the dual weight enumerator satisfy the MacWilliams identity [10,11]; see [1; 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][1; Ch. 5].
Other types of weight enumerators includes the Hamming weight enumerator, Lee weight enumerator, joint weight enumerator, split weight enumerator, and biweight enumerator [1].
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 [2]. 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*{(8)}\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*{(9)}\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*{(10)}\end{align}
Rate
Decoding
Notes
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.
- 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\) [17].
- Traceability code — A \(q\)-ary code with distance \(d \geq n(1-1/t^2)\) has the \(t\)-traceability property [18; 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]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [2]
- W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [4]
- 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
- [5]
- Varshamov, R. R. "Some features of linear codes that correct asymmetric errors." Soviet Physics Doklady. Vol. 9. 1965.
- [6]
- 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
- [7]
- S. D. Constantin and T. R. N. Rao, “On the theory of binary asymmetric error correcting codes”, Information and Control 40, 20 (1979) DOI
- [8]
- Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
- [9]
- T. Kløve, Codes for Error Detection (WORLD SCIENTIFIC, 2007) DOI
- [10]
- J. Macwilliams, “A Theorem on the Distribution of Weights in a Systematic Code†”, Bell System Technical Journal 42, 79 (1963) DOI
- [11]
- 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
- [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]
- 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.
- [17]
- M. Grassl et al., “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
- [18]
- 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
- Victor V. Albert (2022-02-16) — most recent
- Victor V. Albert (2021-10-29)
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