Example CodeZ4_hadamard_decoding (H169E22)

> 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 τ₁ + τ₃ ≤t₀=1 and τ₂ + τ₃ ≤t₁=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 > 1, but it is possible to correct the error vector e=(0 0 0 0 1 0 2 0) since τ₁ + τ₃=1 ≤1 and τ₂ + τ₃=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

Permutation Decoding

Let C be a code over Z₄ of length n and type 2^γ 4^δ and C_bin=Φ(C), where Φ is the Gray map. A subset S ⊆Sym(2n) is an s-PD-set for C_bin with respect to a subset of coordinate positions I⊆{1, ..., 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, ..., 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 C_bin.

If I=[i₁, ..., 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)=[2i₁ - 1, ..., 2i_γ - 1, 2i_{γ + 1} - 1, 2i_{γ + 1}, ..., 2i_{γ + δ} - 1, 2i_{γ + δ}] 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 ⊆PAut(C) ⊆Sym(n), then Φ(S)=[ Φ(τ) : τ ∈S] ⊆PAut(C_bin) ⊆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 C_bin 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].

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

Given a code C over Z₄ 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 C_bin=Φ(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 C_bin=Φ(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 C_bin with respect to I or Φ(I), respectively. Specifically, if the function returns true, it is necessary to check ∑_i=1^s ((|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 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 Z₄ of length n and type 2^γ 4^δ;

-

I=[i₁, ..., 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 C_bin=Φ(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 C_bin;

-

u is a vector from the ambient space V=Z₄ⁿ or V₂=Z₂²ⁿ.

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 V₂.

Assume that the received vector Φ(u)=c + e, where u ∈V, c ∈C_bin and e ∈V₂ 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 C_bin, by using an automorphism of C_bin.

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 C_bin with respect to Φ(I), nor that s≤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 Z₄ of length n and type 2^γ 4^δ;

-

an information set I=[i₁, ..., 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 C_bin=Φ(C), where Φ is the Gray map, with respect to Φ(I);

-

an integer s ∈{1, ..., t}, where t is the error-correcting capability of C_bin;

-

and a sequence Q of vectors from the ambient space V=Z₄ⁿ or V₂=Z₂²ⁿ,

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"

> 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

> 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

> C := KerdockCode(4);

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