# 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](../../references.md#cite-fepuvi08), [Fernández-Córdoba *et al.*, 2010](../../references.md#cite-fepuvi08a), [Villanueva *et al.*, 2015](../../references.md#cite-vzp2015)] for more information on coset decoding; to [[Hammons *et al.*, 1994](../../references.md#cite-sole), [MacWilliams and Sloane, 1978](../../references.md#cite-sloane), [Wan, 1997](../../references.md#cite-wan-z4)] on syndrome decoding; to [[Babu and Zimmermann, 2001](../../references.md#cite-lift), [Greferath and Velbinger, 1998](../../references.md#cite-lift2)] on lifted decoding; and to [[Barrolleta and Villanueva, 2016](../../references.md#cite-bv2015b), [Barrolleta and Villanueva, 2016](../../references.md#cite-bv2015a), [Bernal *et al.*, 2015](../../references.md#cite-bebofevi)] on permutation decoding.

## Coset Decoding

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

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

```magma
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`

```magma
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$.

```magma
> 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

```

## 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.

```magma
> 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

```

## Lifted Decoding

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

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

```magma
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`

```magma
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.

```magma
> 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

```

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$.

```magma
> 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

```

## 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

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

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](../../references.md#cite-bv2015b), [Barrolleta and Villanueva, 2016](../../references.md#cite-bv2015a)].

### `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$.

```magma
> 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

```

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

```magma
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](../../references.md#cite-bv2015a)]. 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](../../references.md#cite-bv2015b)].

### `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$.

```magma
> 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

```

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$.

```magma
> 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

```

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.

```magma
> C := KerdockCode(4);

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

```