Decoding#

This section describes functions for decoding vectors from the ambient space of a code over ${\mathbb{Z}}_4$, or the corresponding space over ${\mathbb{Z}}_2$ under the Gray map, using four different algorithms: coset decoding, syndrome decoding, lifted decoding and permutation decoding. The reader is referred to [Fernández-Córdoba et al., 2008, Fernández-Córdoba et al., 2010, Villanueva et al., 2015] for more information on coset decoding; to [Hammons et al., 1994, MacWilliams and Sloane, 1978, Wan, 1997] on syndrome decoding; to [Babu and Zimmermann, 2001, Greferath and Velbinger, 1998] on lifted decoding; and to [Barrolleta and Villanueva, 2016, Barrolleta and Villanueva, 2016, Bernal et al., 2015] on permutation decoding.

Coset Decoding#

CosetDecode(C, u : parameters): CodeLinRng, ModTupFldElt -> BoolElt, ModTupRngElt, ModTupFldElt#

CosetDecode(C, u : parameters): CodeLinRng, ModTupRngElt -> BoolElt, ModTupRngElt, ModTupFldElt#

MinWeightCode  : RngIntElt                    Default: 
MinWeightKernel: RngIntElt                    Default: 

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a vector $u$ from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode $u$ with respect to $C$. If the decoding algorithm succeeds in computing a vector $u'\in C$ as the decoded version of $u \in V$, then the function returns true, $u'$ and $\Phi(u')$, where $\Phi$ is the Gray map. If the decoding algorithm does not succeed in decoding $u$, then the function returns false, the zero vector in $V$ and the zero vector in $V_2$.

The coset decoding algorithm considers the binary linear code $C_u=C_{bin} \cup (C_{bin}+\Phi(u))$, when $C_{bin}=\Phi(C)$ is linear. On the other hand, when $C_{bin}$ is nonlinear, we have $C_{bin}=\bigcup_{i=0}^t ( K_{bin}+\Phi(c_i))$, where $K_{bin}=\Phi(K_C)$, $K_C$ is the kernel of $C$ as a subcode over ${\mathbb{Z}}_4$, $[c_0,c_1,\ldots,c_t]$ are the coset representatives of $C$ with respect to $K_C$ (not necessarily of minimal weight in their cosets) and $c_0$ is the zero codeword. In this case, the algorithm considers the binary linear codes $K_0=K_{bin}\cup (K_{bin}+\Phi(u))$, $K_1=K_{bin} \cup (K_{bin}+\Phi(c_1)+\Phi(u))$, $\ldots$, $K_t=K_{bin} \cup (K_{bin}+ \Phi(c_t)+\Phi(u))$.

If the parameter MinWeightCode is not assigned, then the minimum weight of $C$, which coincides with the minimum weight of $C_{bin}$, denoted by $d$, is computed. Note that the minimum distance of $C_{bin}$ coincides with its minimum weight. If $C_{bin}$ is linear and the minimum weight of $C_u$ is less than $d$, then $\Phi(u')=\Phi(u)+e$, where $e$ is a word of minimum weight of $C_u$; otherwise, the decoding algorithm returns false. On the other hand, if $C_{bin}$ is nonlinear and the minimum weight of $\cup_{i=0}^t K_i$ is less than the minimum weight of $K_{bin}$, then $\Phi(u')=\Phi(u)+e$, where $e$ is a word of minimum weight of $\cup_{i=0}^t K_i$; otherwise, the decoding algorithm returns false. If the parameter MinWeightKernel is not assigned, then the minimum Hamming weight of $K_{bin}$ is computed.

CosetDecode(C, Q : parameters): CodeLinRng, [ModTupFldElt] -> SeqEnum, SeqEnum, SeqEnum#

CosetDecode(C, Q : parameters): CodeLinRng, [ModTupRngElt] -> SeqEnum, SeqEnum, SeqEnum#

MinWeightCode  : RngIntElt                    Default: 
MinWeightKernel: RngIntElt                    Default: 

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a sequence $Q$ of vectors from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode the vectors of $Q$ with respect to $C$. This function is similar to the function CosetDecode(C, u) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and two sequences of decoded vectors corresponding to the given sequence. The algorithm used and effect of the parameters MinWeightCode and MinWeightKernel are identical to those for the function CosetDecode(C, u).

Example: Spain Z4 12 (ex-68b44c)#

Starting with the Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 16 and type $2^04^3$, a codeword $c \in C$ is selected and then perturbed to give a vector $u$ in the ambient space of $C$. The vector $u$ is then decoded to recover $c$.

> C := HadamardCodeZ4(3, 5);
> C;
((16, 4^3 2^0)) Linear Code over IntegerRing(4)
Generator matrix:
[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 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3]
> d := MinimumLeeDistance(C);
> t := Floor((d-1)/2);
> t;
7
> c := C ! [1,1,1,1,2,2,2,2,3,3,3,3,0,0,0,0];
> c in C;
true
> u := c;
> u[5] := u[5] + 2;
> u[12] := u[12] + 1;
> u[13] := u[13] + 3;
> u[16] := u[16] + 2;
> c;
(1 1 1 1 2 2 2 2 3 3 3 3 0 0 0 0)
> u;
(1 1 1 1 0 2 2 2 3 3 3 0 3 0 0 2)
> grayMap := GrayMap(UniverseCode(Integers(4), Length(C)));
> grayMap(c-u);
(0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1)
> isDecoded, uDecoded := CosetDecode(C, u : MinWeightCode := d);
> isDecoded;
true
> uDecoded eq c;
true

Run in calculator

Syndrome Decoding#

SyndromeDecode(C, u): CodeLinRng, ModTupFldElt -> BoolElt, ModTupRngElt, ModTupFldElt#

SyndromeDecode(C, u): CodeLinRng, ModTupRngElt -> BoolElt, ModTupRngElt, ModTupFldElt#

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a vector $u$ from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode $u$ with respect to $C$. The decoding algorithm always succeeds in computing a vector $u'\in C$ as the decoded version of $u \in V$, and the function returns true, $u'$ and $\Phi(u')$, where $\Phi$ is the Gray map. Although the function never returns false, the first output parameter true is given to be consistent with the other decoding functions.

The syndrome decoding algorithm consists of computing a table pairing each possible syndrome $s$ with a vector of minimum Lee weight $e_s$, called coset leader, in the coset of $C$ containing all vectors having syndrome $s$. After receiving a vector $u$, its syndrome $s$ is computed using the parity check matrix. Then, $u$ is decoded into the codeword $c=u-e_s$.

SyndromeDecode(C, Q): CodeLinRng, [ModTupFldElt] -> SeqEnum, SeqEnum, SeqEnum#
SyndromeDecode(C, Q): CodeLinRng, [ModTupRngElt] -> SeqEnum, SeqEnum, SeqEnum#: Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a sequence $Q$ of vectors from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode the vectors of $Q$ with respect to $C$. This function is similar to the function SyndromeDecode(C, u) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and two sequences of decoded vectors corresponding to the given sequence. The algorithm used is the same as that of function SyndromeDecode(C, u).

Example: Spain Z4 13 (ex-1a7dd2)#

The Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 8 and type $2^14^2$ is constructed. Next information bits are encoded using $C$ and three errors are introduced to give the vector $u$. Then $u$ is decoded by calculating its syndrome and applying the map, given by the CosetLeaders function, to the syndrome to recover the original vector.

> C := HadamardCodeZ4(2, 4);
> C;
((8, 4^2 2^1, 8)) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 3 2 1 0 3 2]
[0 1 2 3 0 1 2 3]
[0 0 0 0 2 2 2 2]
> t := Floor((MinimumLeeDistance(C)-1)/2);
> t;
3
> R, V, f, fbin := InformationSpace(C);
> i := R![2,1,0];
> c := f(i);
> c;
(1 0 3 2 3 2 1 0)
> u := c;
> u[5] := u[5] + 3;
> u[7] := u[7] + 2;
> c;
(1 0 3 2 3 2 1 0)
> u;
(1 0 3 2 2 2 3 0)
> grayMap := GrayMap(UniverseCode(Integers(4), Length(C)));
> grayMap(c-u);
(0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0)
> isDecoded, uDecoded := SyndromeDecode(C, u);
> isDecoded;
true
> uDecoded eq c;
true

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

Run in calculator

Lifted Decoding#

LiftedDecode(C, u : parameters): CodeLinRng, ModTupFldElt -> BoolElt, ModTupRngElt, ModTupFldElt#

LiftedDecode(C, u : parameters): CodeLinRng, ModTupRngElt -> BoolElt, ModTupRngElt, ModTupFldElt#

AlgMethod: MonStgElt                    Default: "Euclidean"

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a vector $u$ from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode $u$ with respect to $C$. If the decoding algorithm succeeds in computing a vector $u'\in C$ as the decoded version of $u \in V$, then the function returns true, $u'$ and $\Phi(u')$, where $\Phi$ is the Gray map. If the decoding algorithm does not succeed in decoding $u$, then the function returns false, the zero vector in $V$ and the zero vector in $V_2$ (in the Euclidean case it may happen that $u'$ is not in $C$ because there are too many errors in $u$ to correct).

The lifted decoding algorithm comprises lifting decoding algorithms for two binary linear codes $C_0$ and $C_1$, being the residue and torsion codes of $C$. Let $t_0$ and $t_1$ be the error-correcting capability of $C_0$ and $C_1$, respectively. Assume the received vector $u=c+e$, where $c\in C$ and $e \in V$ is the error vector. Then, the lifted decoding algorithm can correct all error vectors $e$ such that $\tau_1+\tau_3 \leq t_0$ and $\tau_2+\tau_3 \leq t_1$, where $\tau_i$ is the number of occurrences of $i$ in $e$.

In the decoding process, the function Decode(C, u) for linear codes is used. The available algorithms for linear codes are: syndrome decoding and a Euclidean algorithm, which operates on alternant codes (BCH, Goppa, and Reed–Solomon codes, etc.). If $C_0$ or $C_1$ is alternant, the Euclidean algorithm is used by default, but the syndrome algorithm will be used if the parameter AlgMethod is assigned the value "Syndrome". For non-alternant codes $C_0$ and $C_1$, only syndrome decoding is possible, so the parameter AlgMethod is not relevant.

LiftedDecode(C, Q : parameters): CodeLinRng, [ModTupFldElt] -> SeqEnum, SeqEnum, SeqEnum#

LiftedDecode(C, Q : parameters): CodeLinRng, [ModTupRngElt] -> SeqEnum, SeqEnum, SeqEnum#

AlgMethod: MonStgElt                    Default: "Euclidean"

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a sequence $Q$ of vectors from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, attempt to decode the vectors of $Q$ with respect to $C$. This function is similar to the function LiftedDecode(C, u) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and two sequences of decoded vectors corresponding to the given sequence. The algorithm used and effect of the parameter AlgMethod are the same as for LiftedDecode(C, u).

Example: Hadamard Decoding (ex-403c77)#

The Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 8 and type $2^{1}4^{2}$ is constructed. Then an information word is encoded using $C$, three errors are introduced into the codeword $c$ and then $c$ is recovered by using the lifted decoding algorithm.

> C := HadamardCodeZ4(2, 4);
> C;
((8, 4^2 2^1, 8)) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 3 2 1 0 3 2]
[0 1 2 3 0 1 2 3]
[0 0 0 0 2 2 2 2]
> d := MinimumLeeDistance(C);
> t := Floor((d-1)/2);
> t;
3
> C0 := BinaryResidueCode(C);
> C1 := BinaryTorsionCode(C);
> t0 := Floor((MinimumDistance(C0)-1)/2);
> t1 := Floor((MinimumDistance(C1)-1)/2);
> t0, t1;
1 1

Run in calculator

Using the lifted decoding, it is possible to correct all error vectors $e$ such that $\tau_1+\tau_3 \leq t_0=1$ and $\tau_2+\tau_3 \leq t_1=1$, where $\tau_i$ is the number of occurrences of $i$ in $e$. The following statements show that it is not possible to correct the error vector $e=(0 0 0 0 3 0 2 0)$ since $\tau_2+\tau_3=2 > 1$, but it is possible to correct the error vector $e=(0 0 0 0 1 0 2 0)$ since $\tau_1+\tau_3=1 \leq 1$ and $\tau_2+\tau_3=1 \leq 1$.

> R, V, f, fbin := InformationSpace(C);
> i := R![2,1,0];
> c := f(i);
> c;
(1 0 3 2 3 2 1 0)

> u := c;
> u[5] := u[5] + 3;
> u[7] := u[7] + 2;
> c;
(1 0 3 2 3 2 1 0)
> u;
(1 0 3 2 2 2 3 0)
> e := u - c;
> e;
(0 0 0 0 3 0 2 0)

> isDecoded, uDecoded := LiftedDecode(C, u);
> isDecoded;
true
> uDecoded eq c;
false

> u := c;
> u[5] := u[5] + 1;
> u[7] := u[7] + 2;
> c;
(1 0 3 2 3 2 1 0)
> u;
(1 0 3 2 0 2 3 0)
> e := u - c;
> e;
(0 0 0 0 1 0 2 0)

> isDecoded, uDecoded := LiftedDecode(C, u);
> isDecoded;
true
> uDecoded eq c;
true

Run in calculator

Permutation Decoding#

Let $C$ be a code over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$ and $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map. A subset $S \subseteq {\operatorname{Sym}}(2n)$ is an $s$-PD-set for $C_{bin}$ with respect to a subset of coordinate positions $I\subseteq \{1,\ldots,2n\}$ if $S$ is a subset of the permutation automorphism group of $C_{bin}$, $I$ is an information set for $C_{bin}$, and every $s$-set of coordinate positions in $\{1,\ldots,2n\}$ is moved out of the information set $I$ by at least one element of $S$, where $1\leq s \leq t$ and $t$ is the error-correcting capability of $C_{bin}$.

If $I=[i_1,\ldots, i_{\gamma+\delta}] \subseteq \{1,\ldots,n \}$ is an information set for $C$ such that the code obtained by puncturing $C$ at positions $\{1,\ldots,n\} \backslash \{i_{\gamma+1},\ldots, i_{\gamma+\delta} \}$ is of type $4^\delta$, then $\Phi(I)=[2i_1-1,\ldots, 2i_\gamma-1, 2i_{\gamma+1}-1, 2i_{\gamma+1}, \ldots, 2i_{\gamma+\delta}-1, 2i_{\gamma+\delta}]$ is an information set for $C_{bin}$. It is also easy to see that if $S$ is a subset of the permutation automorphism group of $C$, that is, $S \subseteq {\operatorname{PAut}}(C) \subseteq {\operatorname{Sym}}(n)$, then $\Phi(S)=[ \Phi(\tau) : \tau \in S] \subseteq {\operatorname{PAut}}(C_{bin}) \subseteq {\operatorname{Sym}}(2n)$, where

\[\begin{split}\Phi(\tau)(i)=\cases{ 2\tau(i/2), &if $i$ is even, \\ 2\tau((i+1)/2) -1 &if $i$ is odd.\\}\end{split}\]

Given a subset of coordinate positions $I\subseteq \{1,\ldots, n\}$ and a subset $S \subseteq {\operatorname{Sym}}(n)$, in order to check that $\Phi(S)$ is an $s$-PD-set for $C_{bin}$ with respect to $\Phi(I)$, it is enough to check that $S$ is a subset of the permutation automorphism group of $C$, $I$ is an information set for $C$, and every $s$-set of coordinate positions in $\{1,\ldots,n\}$ is moved out of the information set $I$ by at least one element of $S$ [Barrolleta and Villanueva, 2016, Barrolleta and Villanueva, 2016].

IsPermutationDecodeSet(C, I, S, s): CodeLinRng, [RngIntElt], [GrpPermElt], RngIntElt -> BoolElt#

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, a sequence $I \subseteq \{1,\ldots,2n \}$, a sequence $S$ of elements in the symmetric group ${\operatorname{Sym}}(2n)$ of permutations on the set $\{1,\ldots,2n \}$, and an integer $s\geq 1$, return true if and only if $S$ is an $s$-PD-set for $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map, with respect to the information set $I$.

The arguments $I$ and $S$ can also be given as a sequence $I \subseteq \{1,\ldots,n \}$ and a sequence $S$ of elements in the symmetric group ${\operatorname{Sym}}(n)$ of permutations on the set $\{1,\ldots,n \}$, respectively. In this case, the function returns true if and only if $\Phi(S)$ is an $s$-PD-set for $C_{bin}=\Phi(C)$ with respect to the information set $\Phi(I)$, where $\Phi(I)$ and $\Phi(S)$ are the sequences defined as above.

Depending on the length of the code $C$, its type, and the integer $s$, this function could take some time to compute whether $S$ or $\Phi(S)$ is an $s$-PD-set for $C_{bin}$ with respect to $I$ or $\Phi(I)$, respectively. Specifically, if the function returns true, it is necessary to check $\sum_{i=1}^s {{|I|}\choose{i}} \cdot {{N-|I|}\choose{s-i}}$ $s$-sets, where $N=n$ and $|I|=\gamma+\delta$ when $I$ is given as an information set for $C$, or $N=2n$ and $|I|=\gamma+2\delta$ when $I$ is given as an information set for $C_{bin}$.

The verbose flag IsPDSetFlag is set to level 0 by default. If it is set to level 1, the total time used to check the condition is shown. Moreover, the reason why the function returns false is also shown, that is, whether $I$ is not an information set, $S$ is not a subset of the permutation automorphism group or $S$ is not an $s$-PD-set. If it is set to level 2, the percentage of the computation process performed is also printed.

PermutationDecode(C, I, S, s, u): CodeLinRng, [RngIntElt], [GrpPermElt], RngIntElt, ModTupFldElt -> BoolElt, ModTupRngElt, ModTupFldElt#

PermutationDecode(C, I, S, s, u): CodeLinRng, [RngIntElt], [GrpPermElt], RngIntElt, ModTupRngElt -> BoolElt, ModTupRngElt, ModTupFldElt#

The arguments for the intrinsic are as follows:

$C$ is a code over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$;
$I=[i_1,\ldots, i_{\gamma+\delta}] \subseteq \{1,\ldots,n \}$ is the information set for $C$ given as a sequence of coordinate positions such that the code obtained by puncturing $C$ at coordinate positions $\{1,\ldots,n\} \backslash \{i_{\gamma+1},\ldots,i_{\gamma+1},\ldots, i_{\gamma+\delta} \}$ is of type $4^\delta$;
$S$ is a sequence such that either $S$ or $\Phi(S)$ is an $s$-PD-set for $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map, with respect to $\Phi(I)$;
$s$ is an integer such that $s \in \{1,\ldots,t\}$ where $t$ is the error-correcting capability of $C_{bin}$;
$u$ is a vector from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$.

Given the above assumptions, the function attempts to decode $u$ with respect to $C$. If the decoding algorithm succeeds in computing a vector $u'\in C$ as the decoded version of $u \in V$, then the function returns the values true, $u'$ and $\Phi(u')$. If the decoding algorithm does not succeed in decoding $u$, then the function returns the values false, the zero vector in $V$ and the zero vector in $V_2$.

Assume that the received vector $\Phi(u)=c+e$, where $u \in V$, $c \in C_{bin}$ and $e \in V_2$ is the error vector with at most $t$ errors. The permutation decoding algorithm proceeds by moving all errors in the received vector $\Phi(u)$ out of the information positions. That is, the nonzero coordinates of $e$ are moved out of the information set $\Phi(I)$ for $C_{bin}$, by using an automorphism of $C_{bin}$.

Note that $\Phi(I)$ and $\Phi(S)$ are the sequences defined as above. Moreover, the function does not check whether $I$ is an information set for $C$, nor whether $S$ or $\Phi(S)$ is an $s$-PD-set for $C_{bin}$ with respect to $\Phi(I)$, nor that $s\leq t$.

PermutationDecode(C, I, S, s, Q): CodeLinRng, [RngIntElt], [GrpPermElt], RngIntElt, [ModTupFldElt] -> [BoolElt], [ModTupRngElt], [ModTupFldElt]#

PermutationDecode(C, I, S, s, Q): CodeLinRng, [RngIntElt], [GrpPermElt], RngIntElt, [ModTupRngElt] -> [BoolElt], [ModTupRngElt], [ModTupFldElt]#

Given

a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$;
an information set $I=[i_1,\ldots, i_{\gamma+\delta}] \subseteq \{1,\ldots,n \}$ for $C$ as a sequence of coordinate positions, such that the code $C$ punctured on $\{1,\ldots,n\} \backslash \{i_{\gamma+1},\ldots, i_{\gamma+\delta} \}$ is of type $4^\delta$;
a sequence $S$ such that either $S$ or $\Phi(S)$ is an $s$-PD-set for $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map, with respect to $\Phi(I)$;
an integer $s \in \{1,\ldots,t\}$, where $t$ is the error-correcting capability of $C_{bin}$;
and a sequence $Q$ of vectors from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$,

attempt to decode the vectors of $Q$ with respect to $C$. This function is similar to the version of PermutationDecode that decodes a single vector except that it decodes a sequence of vectors and returns a sequence of booleans and two sequences of decoded vectors corresponding to the given sequence. The algorithm used is the same as that used by the single vector version of PermutationDecode.

Example: Spain Z4 15 (ex-446a9b)#

First the Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 32 and type $2^14^3$ is constructed. It is known that $I=[17,1,2,5]$ is an information set for $C$ and $S=\{ \pi^i : 1\leq i \leq 8 \}$, where $\pi=(1,24,26,15,3,22,28,13)$ $(2, 23, 27, 14, 4, 21, 25, 16)$ $(5, 11, 32, 20, 7, 9, 30, 18)$ $(6, 10, 29, 19, 8,$ $12, 31,17)$, is a subset of the permutation automorphism group of $C$ such that $\Phi(S)$ is a 7-PD-set for $C_{bin}=\Phi(C)$ with respect to $\Phi(I)$. Then, choosing a codeword $c$ of $C$, $c$ is perturbed by the addition of an error vector to give a new vector $u$, and finally permutation decoding is applied to $u$ to recover $c$.

> 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]
> t := Floor((MinimumLeeDistance(C) - 1)/2);
> t;
15
> I := [17, 1, 2, 5];
> p := Sym(32)!(1, 24, 26, 15, 3, 22, 28, 13)(2, 23, 27, 14, 4, 21, 25, 16)
>                 (5, 11, 32, 20, 7, 9, 30, 18)(6, 10, 29, 19, 8, 12, 31,17);
> S := [ p^i : i in [1..8] ];
> SetVerbose("IsPDSetFlag", 2);
> IsPermutationDecodeSet(C, I, S, 7);
Checking whether I is an information set...
Checking whether S is in the permutation automorphism group...
Checking whether S is an s-PD-set...
10 %
20 %
30 %
40 %
50 %
60 %
70 %
80 %
90 %
Took 136.430 seconds (CPU time)
true
> SetVerbose("IsPDSetFlag", 0);
> c := C ! [1,2,3,0,0,1,2,3,3,0,1,2,2,3,0,1,3,0,1,2,2,3,0,1,1,2,3,0,0,1,2,3];
> c in C;
true
> u := c;
> u[1] := c[1] + 2;
> u[2] := c[2] + 2;
> u[3] := c[3] + 1;
> u[16] := c[16] + 3;
> u[27] := c[27] + 1;
> u in C;
false
> LeeDistance(u, c);
7

> grayMap := GrayMap(UniverseCode(Integers(4), Length(C)));
> cbin := grayMap(c);
> ubin := grayMap(u);
> Distance(ubin, cbin);
7
> isDecoded, uDecoded, ubinDecoded := PermutationDecode(C, I, S, 7, u);
> isDecoded;
true
> uDecoded eq c;
true
> ubinDecoded eq cbin;
true

> isDecoded, uDecoded, ubinDecoded := PermutationDecode(C, I, S, 7, ubin);
> isDecoded;
true
> uDecoded eq c;
true
> ubinDecoded eq cbin;
true

Run in calculator

PDSetHadamardCodeZ4(δ, m): RngIntElt, RngIntElt -> SeqEnum, SeqEnum, SeqEnum, SeqEnum, SeqEnum#

AlgMethod: MonStgElt                    Default: "Deterministic"

Given an integer $m\geq 5$, and an integer $\delta$ such that $3\leq \delta \leq \lfloor (m+1)/2 \rfloor$, the Hadamard code $C$ over ${\mathbb{Z}}_4$ of length $n=2^{m-1}$ and type $2^\gamma 4^\delta$, where $\gamma=m+1-2\delta$, given by the function HadamardCodeZ4(\delta, m), is considered. The function returns an information set $I=[i_1,\ldots,i_{\gamma+\delta}] \subseteq \{1,\ldots, n \}$ for $C$ together with a subset $S$ of the permutation automorphism group of $C$ such that $\Phi(S)$ is an $s$-PD-set for $C_{bin}=\Phi(C)$ with respect to $\Phi(I)$, where $\Phi$ is the Gray map and $\Phi(I)$ and $\Phi(S)$ are defined above. The function also returns the information set $\Phi(I)$ and the $s$-PD-set $\Phi(S)$. For $m\geq 1$ and $1 \leq \delta \leq 2$, the Gray map image of $C$ is linear and it is possible to find an $s$-PD-set for $C_{bin}=\Phi(C)$, for any $s\leq \left \lfloor {2^{m}/(m+1)} \right \rfloor -1$, by using the function PDSetHadamardCode(m).

The information sets $I$ and $\Phi(I)$ are returned as sequences of $\gamma+\delta$ and $\gamma+2\delta$ integers, giving the coordinate positions that correspond to the information sets for $C$ and $C_{bin}$, respectively. The sets $S$ and $\Phi(S)$ are also returned as sequences of elements in the symmetric groups ${\operatorname{Sym}}(n)$ and ${\operatorname{Sym}}(2n)$ of permutations on the set $\{1,\ldots,n \}$ and $\{1,\ldots,2n \}$, respectively.

A deterministic algorithm is used by default. In this case, the function returns the $s$-PD-set of size $s+1$ with $s=\lfloor{(2^{2\delta-2}-\delta)/\delta} \rfloor$, which is the maximum value of $s$ when $\gamma=0$, as described in [Barrolleta and Villanueva, 2016]. If the parameter AlgMethod is assigned the value "Nondeterministic", the function tries to improve the previous result by finding an $s$-PD-set of size $s+1$ such that $\lfloor{(2^{2\delta-2}-\delta)/\delta} \rfloor \leq s \leq \lfloor{(2^{m-1}+\delta-m-1)/(m+1-\delta)} \rfloor$. In this case, the function starts from the maximum value of $s$ and decreases it if the $s$-PD-set is not found after a specified time.

PDSetKerdockCodeZ4(m): RngIntElt -> SeqEnum, SeqEnum, SeqEnum, SeqEnum#

Given an integer $m\geq 4$ such that $2^m-1$ is not a prime number, the Kerdock code $C$ over ${\mathbb{Z}}_4$ of length $n=2^m$ and type $4^{m+1}$, given by the function KerdockCodeZ4(m) is considered. The function returns the information set $I=[1,\ldots,m+1]$ for $C$ together with a subset $S$ of the permutation automorphism group of $C$ such that $\Phi(S)$ is an $s$-PD-set for $C_{bin}=\Phi(C)$ with respect to $\Phi(I)$, where $\Phi$ is the Gray map and $\Phi(I)$ and $\Phi(S)$ are defined above. The function also returns the information set $\Phi(I)=[1,\ldots,2m+2]$ and the $s$-PD-set $\Phi(S)$. The size of the $s$-PD-set $S$ is always $\lambda = s+1$, where $\lambda$ is the greatest divisor of $2^m-1$ such that $\lambda \leq 2^m/(m+1)$.

The information sets $I$ and $\Phi(I)$ are returned as sequences of $m+1$ and $2m+2$ integers, giving the coordinate positions that correspond to the information sets for $C$ and $C_{bin}$, respectively. The sets $S$ and $\Phi(S)$ are also returned as sequences of elements in the symmetric groups ${\operatorname{Sym}}(n)$ and ${\operatorname{Sym}}(2n)$ of permutations on the sets $\{1,\ldots,n \}$ and $\{1,\ldots,2n \}$, respectively. The $s$-PD-set $S$ contains the $s+1$ permutations described in [Barrolleta and Villanueva, 2016].

Example: Spain Z4 16 (ex-a6009d)#

A 4-PD-set $S$ of size 5 for the Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 16 and type $2^04^3$ is constructed. A check that it really is a 4-PD-set for $C$ is then made. Note that $\lfloor{(2^{2\delta-2}-\delta)/\delta} \rfloor=4$. Finally, a codeword $c$ of $C$ is selected, perturbed by an error vector $e$ to give a vector $u$, to which permutation decoding is applied to recover $c$.

> C := HadamardCodeZ4(3, 5);

> I, S, Ibin, Sbin := PDSetHadamardCodeZ4(3, 5);
> s := #Sbin-1; s;
4
> s eq Floor((2^(2*3-2)-3)/3);
true
> IsPermutationDecodeSet(C, I, S, s);
true
> IsPermutationDecodeSet(C, Ibin, Sbin, s);
true

> c := C ! [3,2,1,0,1,0,3,2,3,2,1,0,1,0,3,2];
> R := UniverseCode(Integers(4), Length(C));
> u := R ! [2,3,2,0,1,0,3,2,3,2,1,0,1,0,3,3];
> u in C;
false
> LeeDistance(u, c);
4
> grayMap := GrayMap(R);
> cbin := grayMap(c);

> isDecoded, uDecoded, ubinDecoded := PermutationDecode(C, I, S, 4, u);
> isDecoded;
true
> uDecoded eq c;
true
> ubinDecoded eq cbin;
true

Run in calculator

For the Hadamard code $C$ over ${\mathbb{Z}}_4$ of length 32 and type $2^14^3$, a $4$-PD-set of size $5$ can be constructed either by using the deterministic method (by default), or by using a nondeterministic method to obtain an $s$-PD-set of size $s+1$ with $4\leq s \leq 7$. In both cases, the given sets are checked for really being $s$-PD-sets for $C$.

> C := HadamardCodeZ4(3, 6);

> I, S, Ibin, Sbin := PDSetHadamardCodeZ4(3, 6);
> s := #Sbin-1; s;
4
> IsPermutationDecodeSet(C, I, S, s);
true

> I, S, Ibin, Sbin := PDSetHadamardCodeZ4(3, 6 : AlgMethod := "Nondeterministic");
> s := #Sbin-1; s;
6
> IsPermutationDecodeSet(C, I, S, s);
true

Run in calculator

Finally, a 2-PD-set of size 3 is constructed for the Kerdock code of length 16 and type $2^0 4^5$, and formally checked for being a 2-PD-set for this code.

> C := KerdockCode(4);

> I, S, Ibin, Sbin := PDSetKerdockCodeZ4(4);
> IsPermutationDecodeSet(C, I, S, 2);
true
> IsPermutationDecodeSet(C, Ibin, Sbin, 2);
true

Run in calculator