This section describes functions for decoding vectors from the ambient space of a code over Z4, or the corresponding space over Z2 under the Gray map, using four different algorithms: coset decoding, syndrome decoding, lifted decoding and permutation decoding. The reader is referred to [FCPV08], [FCPV10], [VZP15] for more information on coset decoding; to [HKC+94], [MS78], [Wan97] on syndrome decoding; to [BZ01], [GV98] on lifted decoding; and to [BV16a], [BV16b], [BBFCV15] on permutation decoding.
MinWeightCode: RngIntElt Default:
MinWeightKernel: RngIntElt Default:
Given a code C over Z4 of length n, and a vector u from the ambient space V=Z4n or V2=Z22n, attempt to decode u with respect to C. If the decoding algorithm succeeds in computing a vector u'∈C as the decoded version of u ∈V, then the function returns true, u' and Φ(u'), where Φ 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 V2.The coset decoding algorithm considers the binary linear code Cu=Cbin ∪(Cbin + Φ(u)), when Cbin=Φ(C) is linear. On the other hand, when Cbin is nonlinear, we have Cbin=bigcupi=0t ( Kbin + Φ(ci)), where Kbin=Φ(KC), KC is the kernel of C as a subcode over Z4, [c0, c1, ..., ct] are the coset representatives of C with respect to KC (not necessarily of minimal weight in their cosets) and c0 is the zero codeword. In this case, the algorithm considers the binary linear codes K0=Kbin∪(Kbin + Φ(u)), K1=Kbin ∪(Kbin + Φ(c1) + Φ(u)), ..., Kt=Kbin ∪(Kbin + Φ(ct) + Φ(u)).
If the parameter MinWeightCode is not assigned, then the minimum weight of C, which coincides with the minimum weight of Cbin, denoted by d, is computed. Note that the minimum distance of Cbin coincides with its minimum weight. If Cbin is linear and the minimum weight of Cu is less than d, then Φ(u')=Φ(u) + e, where e is a word of minimum weight of Cu; otherwise, the decoding algorithm returns false. On the other hand, if Cbin is nonlinear and the minimum weight of ∪i=0t Ki is less than the minimum weight of Kbin, then Φ(u')=Φ(u) + e, where e is a word of minimum weight of ∪i=0t Ki; otherwise, the decoding algorithm returns false. If the parameter MinWeightKernel is not assigned, then the minimum Hamming weight of Kbin is computed.
MinWeightCode: RngIntElt Default:
MinWeightKernel: RngIntElt Default:
Given a code C over Z4 of length n, and a sequence Q of vectors from the ambient space V=Z4n or V2=Z22n, 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).
> 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
Given a code C over Z4 of length n, and a vector u from the ambient space V=Z4n or V2=Z22n, attempt to decode u with respect to C. The decoding algorithm always succeeds in computing a vector u'∈C as the decoded version of u ∈V, and the function returns true, u' and Φ(u'), where Φ 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 es, 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 - es.
Given a code C over Z4 of length n, and a sequence Q of vectors from the ambient space V=Z4n or V2=Z22n, 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).
> 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
AlgMethod: MonStgElt Default: "Euclidean"
Given a code C over Z4 of length n, and a vector u from the ambient space V=Z4n or V2=Z22n, attempt to decode u with respect to C. If the decoding algorithm succeeds in computing a vector u'∈C as the decoded version of u ∈V, then the function returns true, u' and Φ(u'), where Φ 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 V2 (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 C0 and C1, being the residue and torsion codes of C. Let t0 and t1 be the error-correcting capability of C0 and C1, respectively. Assume the received vector u=c + e, where c∈C and e ∈V is the error vector. Then, the lifted decoding algorithm can correct all error vectors e such that τ1 + τ3 ≤t0 and τ2 + τ3 ≤t1, where τ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 C0 or C1 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 C0 and C1, only syndrome decoding is possible, so the parameter AlgMethod is not relevant.
AlgMethod: MonStgElt Default: "Euclidean"
Given a code C over Z4 of length n, and a sequence Q of vectors from the ambient space V=Z4n or V2=Z22n, 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).
> 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 τ1 + τ3 ≤t0=1 and τ2 + τ3 ≤t1=1, where τ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 τ2 + τ3=2 > 1, but it is possible to correct the error vector e=(0 0 0 0 1 0 2 0) since τ1 + τ3=1 ≤1 and τ2 + τ3=1 ≤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
Let C be a code over Z4 of length n and type 2γ 4δ and Cbin=Φ(C), where Φ is the Gray map. A subset S ⊆Sym(2n) is an s-PD-set for Cbin with respect to a subset of coordinate positions I⊆{1, ..., 2n} if S is a subset of the permutation automorphism group of Cbin, I is an information set for Cbin, and every s-set of coordinate positions in {1, ..., 2n} is moved out of the information set I by at least one element of S, where 1≤s ≤t and t is the error-correcting capability of Cbin.
If I=[i1, ..., iγ + δ] ⊆{1, ..., n } is an
information set for C such that the code obtained by puncturing C at
positions {1, ..., n} \ {iγ + 1, ..., iγ + δ }
is of type 4δ, then Φ(I)=[2i1 - 1, ..., 2iγ - 1, 2iγ + 1 - 1,
2iγ + 1, ..., 2iγ + δ - 1, 2iγ + δ] is an
information set for Cbin. It is also easy to see that if S is a
subset of the permutation automorphism group of C, that is, S ⊆PAut(C) ⊆Sym(n), then Φ(S)=[ Φ(τ) : τ ∈S]
⊆PAut(Cbin) ⊆Sym(2n), where
Φ(τ)(i)=cases(
2τ(i/2), &if i is even,
2τ((i + 1)/2) - 1 &if i is odd.
)
Given a subset of coordinate positions I⊆{1, ..., n} and a subset S ⊆Sym(n), in order to check that Φ(S) is an s-PD-set for Cbin with respect to Φ(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, ..., n} is moved out of the information set I by at least one element of S [BV16a], [BV16b].
Given a code C over Z4 of length n and type 2γ 4δ, a sequence I ⊆{1, ..., 2n }, a sequence S of elements in the symmetric group Sym(2n) of permutations on the set {1, ..., 2n }, and an integer s≥1, return true if and only if S is an s-PD-set for Cbin=Φ(C), where Φ is the Gray map, with respect to the information set I.The arguments I and S can also be given as a sequence I ⊆{1, ..., n } and a sequence S of elements in the symmetric group Sym(n) of permutations on the set {1, ..., n }, respectively. In this case, the function returns true if and only if Φ(S) is an s-PD-set for Cbin=Φ(C) with respect to the information set Φ(I), where Φ(I) and Φ(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 Φ(S) is an s-PD-set for Cbin with respect to I or Φ(I), respectively. Specifically, if the function returns true, it is necessary to check ∑i=1s ((|I|)choose(i)) .((N - |I|)choose(s - i)) s-sets, where N=n and |I|=γ + δ when I is given as an information set for C, or N=2n and |I|=γ + 2δ when I is given as an information set for Cbin.
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.
The arguments for the intrinsic are as follows:Given the above assumptions, the function attempts to decode u with respect to C. If the decoding algorithm succeeds in computing a vector u'∈C as the decoded version of u ∈V, then the function returns the values true, u' and Φ(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 V2.
- -
- C is a code over Z4 of length n and type 2γ 4δ;
- -
- I=[i1, ..., iγ + δ] ⊆{1, ..., 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, ..., n} \ {iγ + 1, ..., iγ + 1, ..., iγ + δ } is of type 4δ;
- -
- S is a sequence such that either S or Φ(S) is an s-PD-set for Cbin=Φ(C), where Φ is the Gray map, with respect to Φ(I);
- -
- s is an integer such that s ∈{1, ..., t} where t is the error-correcting capability of Cbin;
- -
- u is a vector from the ambient space V=Z4n or V2=Z22n.
Assume that the received vector Φ(u)=c + e, where u ∈V, c ∈Cbin and e ∈V2 is the error vector with at most t errors. The permutation decoding algorithm proceeds by moving all errors in the received vector Φ(u) out of the information positions. That is, the nonzero coordinates of e are moved out of the information set Φ(I) for Cbin, by using an automorphism of Cbin.
Note that Φ(I) and Φ(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 Φ(S) is an s-PD-set for Cbin with respect to Φ(I), nor that s≤t.
Given
- -
- a code C over Z4 of length n and type 2γ 4δ;
- -
- an information set I=[i1, ..., iγ + δ] ⊆{1, ..., n } for C as a sequence of coordinate positions, such that the code C punctured on {1, ..., n} \ {iγ + 1, ..., iγ + δ } is of type 4δ;
- -
- a sequence S such that either S or Φ(S) is an s-PD-set for Cbin=Φ(C), where Φ is the Gray map, with respect to Φ(I);
- -
- an integer s ∈{1, ..., t}, where t is the error-correcting capability of Cbin;
- -
- and a sequence Q of vectors from the ambient space V=Z4n or V2=Z22n,
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.
> 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
AlgMethod: MonStgElt Default: "Deterministic"
Given an integer m≥5, and an integer δ such that 3≤δ ≤⌊(m + 1)/2 ⌋, the Hadamard code C over Z4 of length n=2m - 1 and type 2γ 4δ, where γ=m + 1 - 2δ, given by the function HadamardCodeZ4(δ, m), is considered. The function returns an information set I=[i1, ..., iγ + δ] ⊆{1, ..., n } for C together with a subset S of the permutation automorphism group of C such that Φ(S) is an s-PD-set for Cbin=Φ(C) with respect to Φ(I), where Φ is the Gray map and Φ(I) and Φ(S) are defined above. The function also returns the information set Φ(I) and the s-PD-set Φ(S). For m≥1 and 1 ≤δ ≤2, the Gray map image of C is linear and it is possible to find an s-PD-set for Cbin=Φ(C), for any s≤ ⌊(2m/(m + 1)) ⌋ - 1, by using the function PDSetHadamardCode(m).The information sets I and Φ(I) are returned as sequences of γ + δ and γ + 2δ integers, giving the coordinate positions that correspond to the information sets for C and Cbin, respectively. The sets S and Φ(S) are also returned as sequences of elements in the symmetric groups Sym(n) and Sym(2n) of permutations on the set {1, ..., n } and {1, ..., 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=⌊((22δ - 2 - δ)/δ) ⌋, which is the maximum value of s when γ=0, as described in [BV16a]. 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 ⌊((22δ - 2 - δ)/δ) ⌋≤s ≤⌊((2m - 1 + δ - m - 1)/(m + 1 - δ)) ⌋. 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.
Given an integer m≥4 such that 2m - 1 is not a prime number, the Kerdock code C over Z4 of length n=2m and type 4m + 1, given by the function KerdockCodeZ4(m) is considered. The function returns the information set I=[1, ..., m + 1] for C together with a subset S of the permutation automorphism group of C such that Φ(S) is an s-PD-set for Cbin=Φ(C) with respect to Φ(I), where Φ is the Gray map and Φ(I) and Φ(S) are defined above. The function also returns the information set Φ(I)=[1, ..., 2m + 2] and the s-PD-set Φ(S). The size of the s-PD-set S is always λ = s + 1, where λ is the greatest divisor of 2m - 1 such that λ ≤2m/(m + 1).The information sets I and Φ(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 Cbin, respectively. The sets S and Φ(S) are also returned as sequences of elements in the symmetric groups Sym(n) and Sym(2n) of permutations on the sets {1, ..., n } and {1, ..., 2n }, respectively. The s-PD-set S contains the s + 1 permutations described in [BV16b].
> 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 Z4 of length 32 and type 2143, 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≤s ≤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
Finally, a 2-PD-set of size 3 is constructed for the Kerdock code of length 16 and type 20 45, 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