Invariants

The Standard Form

A \({\mathbb{Z}}_4\)-linear code is in standard form if its generator matrix is of the form:

\[\begin{split}\begin{pmatrix}I_{k_1} & A & B \\ 0 & 2I_{k_2} & 2C\end{pmatrix}\end{split}\]

where \(I_{k_1}\) and \(I_{k_2}\) are the \(k_1\times k_1\) and \(k_2\times k_2\) identity matrices, respectively, \(A\) and \(C\) are \({\mathbb{Z}}_2\)-matrices, and \(B\) is a \({\mathbb{Z}}_4\)-matrix. Any \({\mathbb{Z}}_4\)-linear code \(C\) is permutation-equivalent to a code \(S\) which is in standard form. Furthermore, the integers \(k_1\) and \(k_2\), defined above, are unique [Wan97, Prop. 1.1].

StandardForm(C): Code -> Code, Map

This function, given any \({\mathbb{Z}}_4\)-linear code \(C\), returns a permutation-equivalent code \(S\) in standard form, together with the corresponding isomorphism from \(C\) onto \(S\).

Example: Standard Form of a Code over Z4 (ex-48fad2)

Run in calculator (opens in a new tab)Copy input

The standard form is computed for a small \({\mathbb{Z}}_4\) code. Note that the number of rows in the generator matrix of the standard code may be less than that in the original code.

> Z4 := IntegerRing(4);
> C := LinearCode<Z4, 4 | [2,2,1,1], [0,2,0,2]>;
> C;
[4, 3, 2] Linear Code over IntegerRing(4)
Generator matrix:
[2 0 1 3]
[0 2 0 2]
[0 0 2 2]
> S, f := StandardForm(C);
> S;
[4, 2, 2] Linear Code over IntegerRing(4)
Generator matrix:
[1 1 2 2]
[0 2 2 0]
> #S;
8
> #C;
8
> f(C.1);
(1 3 0 2)
> f(C.2);
(0 2 2 0)
> f(C.3);
(2 2 0 0)
> S.1@@f;
(2 2 1 1)
> S.2@@f;
(0 2 0 2)

Run in calculator (opens in a new tab)Copy input

StandardFormDual(C): CodeLinRng -> CodeLinRng, Map

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), return the dual of a permutation-equivalent code \(S\) in standard form, together with the corresponding isomorphism from the dual of \(C\) onto the dual of \(S\). Since \(S\) is generated by a matrix of the form

\[\begin{split}\begin{pmatrix}I_{k_1} & A & B \\ 0 & 2I_{k_2} & 2C\end{pmatrix}\end{split}\]

the dual of \(S\) is generated by the matrix

\[\begin{split}\begin{pmatrix}-(AC+B)^t & C^t & I_{n-k_1-k_2} \\ 2A^t & 2I_{k_2} & 0\end{pmatrix}\end{split}\]

where \(I_{k_1}\) and \(I_{k_2}\) are the \(k_1 \times k_1\) and \(k_2 \times k_2\) identity matrices, respectively, \(A\) and \(C\) are \({\mathbb{Z}}_2\)-matrices, and \(B\) is a \({\mathbb{Z}}_4\)-matrix.

Structures Associated with the Gray Map

MinRowsGeneratorMatrix(C): CodeLinRng -> ModMatRngElt

A generator matrix for the code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), with the minimum number of rows, that is with \(\gamma + \delta\) rows: \(\gamma\) rows of order two and \(\delta\) rows of order four. It also returns the parameters \(\gamma\) and \(\delta\).

MinRowsParityCheckMatrix(C): CodeLinRng -> ModMatRngElt

A parity check matrix for the code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), with the minimum number of rows, that is, with \(\gamma\) rows of order two and \(n-\gamma-\delta\) rows of order four. This function should be faster for most codes over \({\mathbb{Z}}_4\) than the general function ParityCheckMatrix(C) for codes over finite rings. Another parity check matrix for the code \(C\) can be obtained as the generator matrix of the dual of \(C\) with the minimum number of rows, that is, as MinRowsGeneratorMatrix(DualZ4(C)).

DualZ4(C): CodeLinRng -> CodeLinRng

The dual \(D\) of the code \(C\) over \({\mathbb{Z}}_4\) of length \(n\). The dual consists of all codewords in the \({\mathbb{Z}}_4\)-space \(V={\mathbb{Z}}_4^n\) which are orthogonal to all codewords of \(C\). This function should be faster for most codes over \({\mathbb{Z}}_4\) than the general function Dual(C) for codes over finite rings.

Example: Generator Matrices with Minimum Rows (ex-3b2558)

Run in calculator (opens in a new tab)Copy input

> C := HadamardCodeZ4(3, 11);
> G, gamma, delta := MinRowsGeneratorMatrix(C);
> Nrows(G) eq gamma + delta;
true
> deltaH := Length(C) - gamma - delta;
> H1 := MinRowsParityCheckMatrix(C);
> Nrows(H1) eq gamma + deltaH;
true
> H2 := MinRowsGeneratorMatrix(DualZ4(C));
> Nrows(H2) eq gamma + deltaH;
true

> time D := Dual(C);
Time: 24.660
> time D4 := DualZ4(C);
Time: 0.340
> D eq D4, D4 eq LinearCode(H1), D4 eq LinearCode(H2);
true true true

> DualS, f := StandardFormDual(C);
> DualS eq LinearCode(Matrix([f(H1[i]) : i in [1..Nrows(H1)]]));
true

Run in calculator (opens in a new tab)Copy input

SpanZ2CodeZ4(C): CodeLinRng -> CodeLinFld

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), return \(S_C=\Phi^{-1}(S_{bin})\) as a code over \({\mathbb{Z}}_4\), and the linear span of \(C_{bin}\), \(S_{bin}=\langle C_{bin} \rangle\), as a binary linear code of length \(2n\), where \(C_{bin}=\Phi(C)\) and \(\Phi\) is the Gray map.

KernelZ2CodeZ4(C): CodeLinRng -> CodeLinRng

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), return its kernel \(K_C\) as a subcode over \({\mathbb{Z}}_4\) of \(C\), and \(K_{bin}=\Phi(K_C)\) as a binary linear subcode of \(C_{bin}\) of length \(2n\), where \(C_{bin}=\Phi(C)\) and \(\Phi\) is the Gray map.

The kernel \(K_C\) contains the codewords \(v\) such that \(2v*u \in C\) for all \(u \in C\), where \(*\) denotes the component-wise product. Equivalently, the kernel \(K_{bin}=\Phi(K_C)\) contains the codewords \(c\in C_{bin}\) such that \(c+C_{bin}=C_{bin}\), where \(C_{bin}=\Phi(C)\) and \(\Phi\) is the Gray map.

KernelCosetRepresentatives(C): CodeLinRng -> SeqEnum, SeqEnum

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), return the coset representatives \([c_1,\ldots, c_t]\) as a sequence of codewords of \(C\), such that \(C=K_C \cup \bigcup_{i=1}^t \big( K_C+c_i \big)\), where \(K_C\) is the kernel of \(C\) as a subcode over \({\mathbb{Z}}_4\). It also returns the coset representatives of the corresponding binary code \(C_{bin}=\Phi(C)\) as a sequence of binary codewords \([\Phi(c_1), \ldots, \Phi(c_t)]\), such that \(C_{bin}=K_{bin} \cup \bigcup_{i=1}^t \big( K_{bin}+\Phi(c_i)\big)\), where \(K_{bin}=\Phi(K_C)\) and \(\Phi\) is the Gray map.

DimensionOfSpanZ2(C): CodeLinRng -> RngIntElt

RankZ2(C): CodeLinRng -> RngIntElt

Given a code \(C\) over \({\mathbb{Z}}_4\), return the dimension of the linear span of \(C_{bin}\), that is, the dimension of \(\langle C_{bin} \rangle\), where \(C_{bin}=\Phi(C)\) and \(\Phi\) is the Gray map.

DimensionOfKernelZ2(C): CodeLinRng -> RngIntElt

Given a code \(C\) over \({\mathbb{Z}}_4\), return the dimension of the Gray map image of its kernel \(K_C\) over \({\mathbb{Z}}_4\), that is the dimension of \(K_{bin}=\Phi(K_C)\), where \(\Phi\) is the Gray map. Note that \(K_{bin}\) is always a binary linear code.

Example: Kernel and Span of a Code over Z4 (ex-bb9d15)

Run in calculator (opens in a new tab)Copy input

> C := ReedMullerCodeRMZ4(0,3,5);
> DimensionOfKernelZ2(C);
20
> DimensionOfSpanZ2(C);
27
> K, Kb := KernelZ2CodeZ4(C);
> S, Sb := SpanZ2CodeZ4(C);
> K subset C;
true
> C subset S;
true
> Dimension(Kb) eq DimensionOfKernelZ2(C);
true
> Dimension(Sb) eq DimensionOfSpanZ2(C);
true

Run in calculator (opens in a new tab)Copy input

Coset Representatives

CosetRepresentatives(C): CodeLinRng -> SeqEnum

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), with ambient space \(V={\mathbb{Z}}_4^n\), return a set of coset representatives (not necessarily of minimal weight in their cosets) for \(C\) in \(V\) as an indexed set of vectors from \(V\). The set of coset representatives \(\{c_0, c_1, \ldots, c_t \}\) satisfies the two conditions that \(c_0\) is the zero codeword, and \(V=\bigcup_{i=0}^t \big( C+c_i \big)\). Note that this function is only applicable when \(V\) and \(C\) are small.

CosetRepresentatives(C, S): CodeLinRng, CodeLinRng -> SeqEnum, SeqEnum

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), and a subcode \(S\) over \({\mathbb{Z}}_4\) of \(C\), return a set of coset representatives (not necessarily of minimal weight in their cosets) for \(S\) in \(C\) as an indexed set of codewords from \(C\). The set of coset representatives \(\{c_0, c_1, \ldots, c_t \}\) satisfies the two conditions that \(c_0\) is the zero codeword, and \(C= \bigcup_{i=0}^t \big( S+c_i \big)\). Note that this function is only applicable when \(S\) and \(C\) are small.

Example: Coset Representatives of a Code (ex-551655)

> C := LinearCode<Integers(4), 4 | [[1,0,0,3],[0,1,1,3]]>;
> L := CosetRepresentatives(C);
> Set(RSpace(Integers(4),4)) eq {v+ci : v in Set(C), ci in L};
true

> K := KernelZ2CodeZ4(C);
> L := CosetRepresentatives(C, K);
> {C!0} join Set(KernelCosetRepresentatives(C)) eq L;
true
> Set(C) eq {v+ci : v in Set(K), ci in L};
true

Run in calculator (opens in a new tab)Copy input

Information Space and Information Sets

InformationSpace(C): CodeLinRng -> ModTupRng, ModTupFld, Map, Map

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), return the \({\mathbb{Z}}_4\)-submodule of \({\mathbb{Z}}_4^{\gamma+\delta}\) isomorphic to \({\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^\delta\) such that the first \(\gamma\) coordinates are of order two, that is, the space of information vectors for \(C\). The function also returns the \((\gamma+2\delta)\)-dimensional binary vector space, which is the space of information vectors for the corresponding binary code \(C_{bin}=\Phi(C)\), where \(\Phi\) is the Gray map. Finally, for the encoding process, it also returns the corresponding isomorphisms \(f\) and \(f_{bin}\) from these spaces of information vectors onto \(C\) and \(C_{bin}\), respectively.

Example: Information Space of a Code over Z4 (ex-5fc04a)

Run in calculator (opens in a new tab)Copy input

> C := LinearCode<Integers(4), 4 | [[2,0,0,2],[0,1,1,3]]>;
> R, V, f, fbin := InformationSpace(C);
> G := MinRowsGeneratorMatrix(C);

> (#R eq #C) and (#V eq #C);
true
> Set([f(i) : i in R]) eq Set(C);
true
> Set([i*G : i in R]) eq Set(C);
false

> i := R![2,3];
> c := f(i);
> c;
(2 3 3 3)
> c in C;
true
> i*G eq c;
false

> ibin := V![1,1,0];
> cbin := fbin(ibin);
> cbin;
(1 1 1 0 1 0 1 0)
> cbin in GrayMapImage(C);
true
> cbin eq GrayMap(C)(c);
true

Run in calculator (opens in a new tab)Copy input

InformationSet(C): CodeLinRng -> ModTupRng, ModTupFld, Map, Map

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), return an information set \(I=[i_1,\ldots,i_{\gamma+\delta}] \subseteq \{1,\ldots,n\}\) for \(C\) such that the code \(C\) punctured on \(\{1,\ldots,n\} \backslash \{i_{\gamma+1},\ldots, i_{\gamma+\delta} \}\) is of type \(4^\delta\), and the corresponding information set \(\Phi(I)=[2i_1-1,\ldots, 2i_\gamma-1, 2i_{\gamma+1}-1, 2i_{\gamma+1}, \ldots, 2i_{\gamma+\delta}-1, 2i_{\gamma+\delta}] \subseteq \{1,\ldots,2n\}\) for the binary code \(C_{bin}=\Phi(C)\), where \(\Phi\) is the Gray map. The information sets \(I\) and \(\Phi(I)\) are returned as a sequence of \(\gamma+\delta\) and \(\gamma+2\delta\) integers, giving the coordinate positions that correspond to the information set of \(C\) and \(C_{bin}\), respectively.

An information set \(I\) for \(C\) is an ordered set of \(\gamma+\delta\) coordinate positions such that \(|C^I|=2^{\gamma}4^\delta\), where \(C^I=\{v^I : v\in C \}\) and \(v^I\) is the vector \(v\) restricted to the \(I\) coordinates. An information set \(J\) for \(C_{bin}\) is an ordered set of \(\gamma+2\delta\) coordinate positions such that \(|{C^{J}_{bin}}|=2^{\gamma+2\delta}\).

IsInformationSet(C, I): CodeLinRng, [RngIntElt] -> BoolElt, BoolElt

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\) and a sequence \(I \subseteq \{1,\ldots,n \}\) or \(I \subseteq \{1,\ldots,2n \}\), return true if and only if \(I\subseteq \{1,\ldots,n \}\) is an information set for \(C\). This function also returns another boolean, which is true if and only if \(I \subseteq \{1,\ldots,2n \}\) is an information set for the corresponding binary code \(C_{bin}=\Phi(C)\), where \(\Phi\) is the Gray map.

An information set \(I\) for \(C\) is an ordered set of \(\gamma+\delta\) coordinate positions such that \(|C^I|=2^{\gamma}4^\delta\), where \(C^I=\{v^I : v\in C \}\) and \(v^I\) is the vector \(v\) restricted to the \(I\) coordinates. An information set \(J\) for \(C_{bin}\) is an ordered set of \(\gamma+2\delta\) coordinate positions such that \(|{C^{J}_{bin}}|=2^{\gamma+2\delta}\).

Example: Information Sets of a Hadamard Code (ex-1d41b7)

Run in calculator (opens in a new tab)Copy input

> C := HadamardCodeZ4(3,6);
> C;
((32, 4^3 2^1)) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 3 2 0 3 2 1 3 2 1 0 2 1 0 3 1 0 3 2 0 3 2 1 3 2 1 0 2 1 0 3]
[0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3]
[0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

> I, Ibin := InformationSet(C);
> I;
[ 16, 28, 31, 32 ]
> Ibin;
[ 31, 55, 56, 61, 62, 63, 64 ]
> #PunctureCode(C, {1..32} diff Set(I)) eq #C;
true
> Cbin := GrayMapImage(C);
> V := VectorSpace(GF(2), 7);
> #{V![c[i] : i in Ibin] : c in Cbin} eq #Cbin;
true

> IsInformationSet(C, I);
true false
> IsInformationSet(C, Ibin);
false true

> IsInformationSet(C, [1, 2, 5, 17]);
true false
> IsInformationSet(C, [1, 2, 3, 4, 9, 10, 33]);
false true

> D := LinearCode<Integers(4), 5 | [[2,0,0,2,0],[0,2,0,2,2],[0,0,2,2,0]]>;
> IsInformationSet(D, [1,3,5]);
true true

Run in calculator (opens in a new tab)Copy input

Syndrome Space and Coset Leaders

SyndromeSpace(C): CodeLinRng -> ModTupRng, ModTupFld

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), return the \({\mathbb{Z}}_4\)-submodule of \({\mathbb{Z}}_4^{n-\delta}\) isomorphic to \({\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^{n-\gamma-\delta}\) such that the first \(\gamma\) coordinates are of order two, that is, the space of syndrome vectors for \(C\). The function also returns the \((2n-2\delta-\gamma)\)-dimensional binary vector space, which is the space of syndrome vectors for the corresponding binary code \(C_{bin}=\Phi(C)\), where \(\Phi\) is the Gray map. Note that these spaces are computed by using the function InformationSpace(C) applied to the dual code of \(C\), produced by function DualZ4(C).

Syndrome(u, C): ModTupFldElt, CodeLinRng -> ModTupRngElt

Syndrome(u, C): ModTupRngElt, CodeLinRng -> ModTupRngElt

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\) and type \(2^\gamma 4^\delta\), and a vector \(u\) from the ambient space \(V={\mathbb{Z}}_4^n\) or \(V_2={\mathbb{Z}}_2^{2n}\), construct the syndrome of \(u\) relative to the code \(C\). This will be an element of the syndrome space of \(C\), considered as the \({\mathbb{Z}}_4\)-submodule of \({\mathbb{Z}}_4^{n-\delta}\) isomorphic to \({\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^{n-\gamma-\delta}\) such that the first \(\gamma\) coordinates are of order two.

CosetLeaders(C): CodeLinRng -> SetIndx, Map

Given a code \(C\) over \({\mathbb{Z}}_4\) of length \(n\), with ambient space \(V={\mathbb{Z}}_4^{n}\), return a set of coset leaders (vectors of minimal Lee weight in their cosets) for \(C\) in \(V\) as an indexed set of vectors from \(V\). This function also returns a map from the syndrome space of \(C\) onto the coset leaders (mapping a syndrome into its corresponding coset leader). Note that this function is only applicable when \(V\) and \(C\) are small.

Example: Syndrome Space and Coset Leaders (ex-5bce83)

Run in calculator (opens in a new tab)Copy input

> C := LinearCode<Integers(4), 4 | [[2,0,0,2],[0,1,1,3]]>;
> R, V, f, fbin := InformationSpace(C);
> Rs, Vs := SyndromeSpace(C);

> #R * #Rs eq 4^Length(C);
true
> #V * #Vs eq 4^Length(C);
true

> i := R![2,3];
> c := f(i);
> c;
(2 3 3 3)
> u := c;
> u[2] := u[2] + 3;
> u;
(2 2 3 3)

> s := Syndrome(u, C);
> s in Rs;
true
> H := Transpose(MinRowsGeneratorMatrix(Dual(C)));
> s eq u*H;
true

> L, mapCosetLeaders := CosetLeaders(C);
> ev := mapCosetLeaders(s);
> ev;
(0 3 0 0)
> ev in L;
true
> u - ev eq c;
true

Run in calculator (opens in a new tab)Copy input

Miscellaneous Functions

Correlation(v): ModTupRngElt -> RngQuadElt

Let \(v\) be a codeword over \({\mathbb{Z}}_4\). Define \(w_j = \#\{k : v[k] = j\}\) for \(j = 0,\ldots,3\). Then the correlation of \(v\) is the Gaussian integer \((w_0 - w_2) + i*(w_1 - w_3)\).