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 [Wan, 1997, 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 (ex-48fad2)#

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

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: New Invar (ex-3b2558)#

> 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

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: Spain Z4 5 (ex-bb9d15)#

> 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

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: Spain Z4 7 (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

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: Spain Z4 9 (ex-5fc04a)#

> 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

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: Spain Z4 10 (ex-1d41b7)#

> 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

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: Spain Z4 11 (ex-5bce83)#

> 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

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)\).