Description
A code that forms a subgroup of \(\mathbb{Z}_4^n\) under addition. More technically, linear codes over \(\mathbb{Z}_4\) are submodules of \(\mathbb{Z}_4^n\).
Linear codes over \(\mathbb{Z}_4\) can be defined in terms of a generator matrix \(G\), whose rows generate the \(k\)-dimensional codespace. Given a message (i.e., logical string) \(x\), the corresponding encoded codeword is \(G^T x\).
A code’s generator matrix can be reduced via coordinate permutations to its standard form \begin{align} G=\left[\begin{array}{ccc} I_{k_{1}} & A & B\\ 0 & 2I_{k_{2}} & 2C \end{array}\right]~, \tag*{(1)}\end{align} where \(A,C\) are binary matrices, and where \(B\) is a quaternary matrix. Such a code encodes \(4^{k_1} 2^{k_2}\) codewords, consisting of \(k_1\) logical quaternary digits and \(k_2\) logical bits. It is called an \((n,4^{k_1} 2^{k_2})_{\mathbb{Z}_4}\) linear code over \(\mathbb{Z}_4\) of type \(4^{k_1} 2^{k_2}\). The generator matrix forms a basis when there are no logical bits, i.e., the submodule is free if and only if \(k_2=0\) [1].
Two linear codes over \(\mathbb{Z}_4\) are monomially equivalent if the codewords of one code can be mapped into those of the other under a permutation and coordinate sign flips. The monomial automorphism group of a linear code over \(\mathbb{Z}_4\) is the largest subgroup of coordinate permutations and sign flips that maps the code onto itself.
Protection
Quaternary codes over \(\mathbb{Z}_4\) come with a Hamming distance, which is the minimum number of nonzero coordinates of a nonzero codeword. They also protect from cyclic shifts in each quaternary digit, which are quantified by the Lee metric. The Lee weight of a digit is given by \(w_L(0)=0\), \(w_L(1)=1\), \(w_L(2)=2\), and \(w_L(3)=1\), and the Lee weight of a string is the integral sum of the Lee weights of its digits. The Lee distance of a code is the minimum Lee weight of a nonzero codeword [2; Secs. 6.2 and 6.3].
The Lee distance \(d_L\) between two strings \(a,b\in\mathbb{Z}_4\) governs how many cyclic shifts it takes to connect the two strings, and is thus related to the Euclidean distance between the vectors \(i^a\) and \(i^b\) as \(2d_L(a,b) = \|i^a - i^b\|^2\). Quaternary codes over the Lee metric are thus naturally mapped to QPSK codes.
Weight enumerators have also been extended to the Lee metric [3].
Notes
Code Database, including quasi-cyclic and quasi-twisted codes [4].See books [1,5,6] for introductions.Cousins
- Linear binary code— A linear quaternary code over \(\mathbb{Z}_4\) of length \(n\), type \(4^{k_1}2^{k_2}\), and minimum Lee weight \(d\) maps under the Gray map to a binary code of length \(2n\), cardinality \(2^{2k_1+k_2}\), and minimum Hamming weight \(d\) [2; Sec. 6.3].
- Quadrature PSK (QPSK) code— The Lee distance \(d_L\) between two strings \(a,b\in\mathbb{Z}_4\) governs how many cyclic shifts it takes to connect the two strings, and is thus related to the Euclidean distance between \(i^a\) and \(i^b\) as \(2d_L(a,b) = \|i^a - i^b\|^2\). Quaternary codes over the Lee metric are thus naturally mapped to QPSK codes.
- Construction \(A_4\) code— Every linear code over \(\mathbb{Z}_4\) yields a lattice under Construction \(A_4\) [5; Sec. 12.5.3].
- \([2^m -1, 2^m - 1 - 2m, 5]\) Melas code— The even-weight subcode of the Melas code can be lifted to a linear code over \(\mathbb{Z}_4\) [7].
- Hergert code— Hergert codes can be seen, via the Gray map, as linear codes over \(\mathbb{Z}_4\) [1,8].
- Gray code— A linear code \(C\) over \(\mathbb{Z}_4\) can be mapped, via the Gray map, to a binary code. The binary code is linear if and only if doubling the component-wise product of any two codewords in \(C\) yields another codeword in \(C\) [5; Thm. 12.2.3]. More specifically, a linear quaternary code over \(\mathbb{Z}_4\) of length \(n\), type \(4^{k_1}2^{k_2}\), and minimum Lee weight \(d\) maps under the Gray map to a binary code of length \(2n\), cardinality \(2^{2k_1+k_2}\), and minimum Hamming weight \(d\) [2; Sec. 6.3].
- Delsarte-Goethals (DG) code— DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [8].
- Reed-Muller (RM) code— Binary Reed-Muller codes are images of linear quaternary codes over \(\mathbb{Z}_4\) under the Gray map [2; Sec. 6.3].
Member of code lists
Primary Hierarchy
References
- [1]
- Z. X. Wan, Quaternary Codes (WORLD SCIENTIFIC, 1997) DOI
- [2]
- S. T. Dougherty, “Codes over rings.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- M. Klemm, “Selbstduale Codes �ber dem Ring der ganzen Zahlen modulo 4”, Archiv der Mathematik 53, 201 (1989) DOI
- [4]
- N. Aydin, Y. Lu, and V. R. Onta, “An Updated Database of \(\mathbb{Z}_4\) Codes”, (2022) arXiv:2208.06832
- [5]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [6]
- R. Roth, Introduction to Coding Theory (Cambridge University Press, 2006) DOI
- [7]
- A. Alahmadi, H. Alhazmi, T. Helleseth, R. Hijazi, N. Muthana, and P. Solé, “On the lifted Melas code”, Cryptography and Communications 8, 7 (2015) DOI
- [8]
- A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
Page edit log
- Victor V. Albert (2022-03-04) — most recent
Cite as:
“Linear code over \(\mathbb{Z}_4\)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quaternary_over_z4