Decoding

Magma supplies functions for decoding vectors from the ambient space of a linear code \(C\). The functions in this section only apply to codes over finite fields.

Syndrome Decoding

While syndrome decoding applies to any linear code it is restricted to codes having small codimension since it needs to calculate the coset leaders.

SyndromeDecoding(C, v): CodeLinFld, ModTupRngElt -> BoolElt, ModTupRngElt

Given a linear code \(C\) and a vector \(v\) from the ambient space \(V\) of \(C\), attempt to decode \(v\) with respect to \(C\).

If the decoding algorithm succeeds in computing a vector \(v'\) as the decoded version of \(v\), then the function returns true and \(v'\). If the decoding algorithm does not succeed in decoding \(v\), then the function returns false and the zero vector.

SyndromeDecoding(C, Q): CodeLinFld, [ ModTupRngElt ] -> [ BoolElt ], [ ModTupRngElt ]

Given a linear code \(C\) and a sequence \(Q\) of vectors from the ambient space \(V\) of \(C\), attempt to decode the vectors of \(Q\) with respect to \(C\). This function is similar to the function SyndromeDecoding(C, v) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and a sequence of decoded vectors corresponding to the given sequence.

Example: Syn Decode (ex-8f7190)

We create a code \(C\) and a vector \(v\) of \(C\) and then perturb \(v\) to a new vector \(w\). We then decode \(w\) to find \(v\) again.

> C := GolayCode(GF(2), false);
> v := C ! [1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,1,1];
> w := v;
> w[5] := 1 - w[5];
> w[20] := 1 - w[20];
> v;
(1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1)
> w;
(1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1)
> v - w;
(0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0)
> b, d := SyndromeDecoding(C, w);
> b;
true
> d;
(1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1)
> d eq v;
true
> SyndromeDecoding(C, [w]);
[ true ]
[
    (1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1)
]

Run in calculatorCopy input

Euclidean Decoding

The Euclidean decoding algorithm applies to alternant codes which include BCH, Goppa, and Reed–Solomon codes. While the Euclidean algorithm cannot correct as many errors as can the syndrome algorithm, in general it is much faster and so can be applied to much larger codes. This is because the syndrome algorithm needs to determine the coset leaders of the code and so becomes inapplicable as soon as the codimension of the code is moderately large.

EuclideanDecoding(C, v): CodeLinFld, ModTupRngElt -> BoolElt, ModTupRngElt

Given a linear alternant code \(C\) and a vector \(v\) from the ambient space \(V\) of \(C\), attempt to decode \(v\) with respect to \(C\).

If the decoding algorithm succeeds in computing a vector \(v'\) as the decoded version of \(v\), then the function returns true and \(v'\). It may even happen that \(v'\) is not in \(C\) because there are too many errors in \(v\) to correct. If the decoding algorithm does not succeed in decoding \(v\), then the function returns false and the zero vector.

EuclideanDecoding(C, Q): CodeLinFld, [ ModTupRngElt ] -> [ BoolElt ], [ ModTupRngElt ]

Given a linear alternant code \(C\) and a sequence \(Q\) of vectors from the ambient space \(V\) of \(C\), attempt to decode the vectors of \(Q\) with respect to \(C\). This function is similar to the function EuclideanDecoding(C, v) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and a sequence of decoded vectors corresponding to the given sequence.

Example: Eucl Decode (ex-72e926)

We create a Reed-Solomon code \(C\) over \(GF(2^8)\) with designated minimum distance \(12\).

> K := GF(2^8);
> C := ReedSolomonCode(K, 12);
> C:Minimal;
[255, 244, 12] "BCH code (d = 12, b = 1)" Linear Code over GF(2^8)

Run in calculatorCopy input

So our code has length \(255\) and dimension \(244\). With minimum distance \(12\) it will correct \(5\) or fewer errors. We demonstrate this by introducing \(5\) errors into a random codeword \(c\).

> c := Random(C);
> V := VectorSpace(C);
> e := V![ 0 :i in [1..255]];
> for i := 1 to 5 do
> j := Random(1, 255);
> k := Random(K);
> e[j] := k;
> end for;
> d := c + e;
> _, cc := EuclideanDecoding(C, d);
> c eq cc;
true;

Run in calculatorCopy input

If we introduce \(6\) or more errors the decoding will usually fail:-

> e := V![ 0 :i in [1..255]];
> for i := 1 to 6 do
> j := Random(1, 255);
> k := Random(K);
> e[j] := k;
> end for;
> d := c + e;
> _, cc := EuclideanDecoding(C, d);
> c eq cc;
false

Run in calculatorCopy input

Permutation Decoding

IsPermutationDecodeSet(C, I, S, s): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt -> BoolElt

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

Given

–

an \([n,k]\) linear code \(C\) over a finite field \(K\);

–

an information set \(I \subseteq \{1,\ldots,n \}\) for \(C\) as a sequence of coordinate positions;

–

a sequence \(S\) of elements in the group of monomial matrices of degree \(n\) over \(K\), OR if \(C\) is a binary code, a sequence of elements in the symmetric group \({\operatorname{Sym}}(n)\) acting on the set \(\{1,\ldots,n\}\). In either case \(S\) must be an \(s\)-PD-set for \(C\) with respect to \(I\);

–

and an integer \(s \in \{1,\ldots,t\}\), where \(t\) is the error-correcting capability of \(C\);

this intrinsic returns true if and only if \(S\) is an \(s\)-PD-set for \(C\) with respect to the information set \(I\).

Depending on the length of the code \(C\), its dimension \(k\), and the integer \(s\), this function could take some time to compute whether \(S\) is an \(s\)-PD-set for \(C\) with respect to \(I\). Specifically, if the function returns true, it is necessary to check \(\sum_{i=1}^s {{k}\choose{i}} \cdot {{n-k}\choose{s-i}}\) \(s\)-sets.

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 the function returns false is also shown, that is, whether \(I\) is not an information set, \(S\) is not a subset of the monomial automorphism group of \(C\) 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): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt, ModTupFldElt -> BoolElt, ModTupFldElt

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

Given

–

an \([n,k]\) linear code \(C\) over a finite field \(K\);

–

an information set \(I \subseteq \{1,\ldots,n \}\) for \(C\) as a sequence of coordinate positions;

–

a sequence \(S\) of elements in the group of monomial matrices of degree \(n\) over \(K\), OR if \(C\) is a binary code, a sequence of elements in the symmetric group \({\operatorname{Sym}}(n)\) acting on the set \(\{1,\ldots,n\}\). In either case \(S\) must be an \(s\)-PD-set for \(C\) with respect to \(I\);

–

an integer \(s \in \{1,\ldots,t\}\), where \(t\) is the error-correcting capability of \(C\);

–

and a vector \(u\) from the ambient space \(V\) of \(C\),

the intrinsic 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 true and the codeword \(u'\). If the decoding algorithm does not succeed in decoding \(u\), then the function returns false and the zero vector in \(V\).

The decoding algorithm works by moving all errors in the received vector \(u=c+e\), where \(c \in C\) and \(e \in V\) is the error vector with at most \(t\) errors, out of the information positions, that is, moving the nonzero coordinates of \(e\) out of the information set \(I\) for \(C\), by using an automorphism of \(C\). Note that the function does not check any of the conditions that \(I\) is an information set for \(C\), \(S\) is an \(s\)-PD-set for \(C\) with respect to \(I\), or \(s\leq t\).

PermutationDecode(C, I, S, s, Q): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt, [ModTupFldElt] -> [BoolElt], [ModTupFldElt]

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

Given

–

an \([n,k]\) linear code \(C\) over a finite field \(K\);

–

an information set \(I \subseteq \{1,\ldots,n \}\) for \(C\) as a sequence of coordinate positions;

–

a sequence \(S\) of elements in the group of monomial matrices of degree \(n\) over \(K\), OR if \(C\) is a binary code, a sequence of elements in the symmetric group \({\operatorname{Sym}}(n)\) acting on the set \(\{1,\ldots,n\}\). In either case \(S\) must be an \(s\)-PD-set for \(C\) with respect to \(I\);

–

an integer \(s \in \{1,\ldots,t\}\), where \(t\) is the error-correcting capability of \(C\);

–

a sequence \(Q\) of vectors from the ambient space \(V\) of \(C\),

the intrinsic attempts to decode the vectors of \(Q\) with respect to \(C\). This function is similar to the function PermutationDecode(C, I, S, s, u) except that rather than decoding a single vector, it decodes a sequence of vectors and returns a sequence of booleans and a sequence of decoded vectors corresponding to the given sequence. The algorithm used is as for the function PermutationDecode(C, I, S, s, u).

PDSetSimplexCode(K, m): FldFin, RngIntElt -> SeqEnum, SeqEnum, SeqEnum

Given a finite field \(K\) of cardinality \(q\), and a positive integer \(m\), the intrinsic constructs the \([n=(q^m-1)/(q-1), m, q^{m-1}]\) linear simplex code \(C\) over \(K\), as Dual(HammingCode(K, m)), and then searches for an \(s\)-PD-set for \(C\). The function returns an information set \(I\) for \(C\) together with a subset \(S\) of the monomial automorphism group of \(C\) such that \(S\) is an \(s\)-PD-set for \(C\) with respect to \(I\), where \(s=\left \lfloor{(q^{m}-1)/(m(q-1))} \right \rfloor -1\).

The information set \(I\) is returned as a sequence of \(m\) integers, giving the coordinate positions that correspond to the information set for \(C\). The set \(S\) is also returned as a sequence, which contains the \(s+1\) elements in the group of monomial matrices of degree \(n\) over \(K\) described in [Fish et al., 2012]. When \(K\) is \(GF(2)\), the function also returns the elements of \(S\) represented as elements in the symmetric group \(Sym(n)\) of permutations on the set \(\{1,\ldots,n \}\).

PDSetHadamardCode(m): RngIntElt -> SeqEnum, SeqEnum, SeqEnum

Given a positive integer \(m\), the intrinsic constructs the \([2^m, m+1, 2^{m-1}]\) binary linear Hadamard code \(C\), as Dual(ExtendCode(HammingCode(GF(2), m))), and then searches for an \(s\)-PD-set for \(C\). The function returns an information set \(I \subseteq \{1,\ldots, 2^m \}\) for \(C\) together with a subset \(S\) of the permutation automorphism group of \(C\) such that \(S\) is an \(s\)-PD-set for \(C\) with respect to \(I\), where \(s= \left \lfloor {2^{m}/(m+1)} \right \rfloor -1\).

The information set \(I\) is returned as a sequence of \(m+1\) integers, giving the coordinate positions that correspond to the information set for \(C\). The set \(S\) is also returned as a sequence, which contains the \(s+1\) elements in the group of permutation matrices of degree \(2^m\) over \(GF(2)\) described in [Barrolleta and Villanueva, 2016]. The function also returns the elements of \(S\) represented as elements in the symmetric group \({\operatorname{Sym}}(2^m)\) of permutations on the set \(\{1,\ldots,2^m \}\).

Example: Spain Decode 1 (ex-7bde55)

> C := Dual(ExtendCode(HammingCode(GF(2), 5)));
> C;
[32, 6, 16] Linear Code over GF(2)
Generator matrix:
[1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1]
[0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0]
[0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1]
[0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0]
[0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0]
[0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1]

> I, SMAut, SPAut := PDSetHadamardCode(5);
> I in AllInformationSets(C);
true
> s := #SMAut-1;  s;
4
> [ LinearCode(GeneratorMatrix(C)*SMAut[i]) eq C : i in [1..s+1] ];
[true, true, true, true, true];
> [ LinearCode(GeneratorMatrix(C)^SPAut[i]) eq C : i in [1..s+1] ];
[true, true, true, true, true];
> IsPermutationDecodeSet(C, I, SMAut, s);
true
> IsPermutationDecodeSet(C, I, SPAut, s);
true

> c := C ! [1^^32];
> c in C;
true
> u := c;
> u[1] := c[1] + 1;
> u[2] := c[2] + 1;
> u[4] := c[4] + 1;
> u[32] := c[32] + 1;
> u in C;
false
> isDecoded, uDecoded := PermutationDecode(C, I, SMAut, s, u);
> isDecoded;
true
> uDecoded eq c;
true
> isDecoded, uDecoded := PermutationDecode(C, I, SPAut, s, u);
> isDecoded;
true
> uDecoded eq c;
true

Run in calculatorCopy input

Example: Spain Decode 2 (ex-982ee0)

> K<a> := GF(4);
> C := Dual(HammingCode(K, 3));
> C;
[21, 3, 16] Linear Code over GF(2^2)
Generator matrix:
[1 0 a^2 a 1 0 a^2 a 1 a^2 0 1 a a 1 0 a^2 1 a a^2 0]
[0 1 1 1 1 0 0 0 0 a^2 a^2 a^2 a^2 a a a a 1 1 1 1]
[0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

> I, SMAut := PDSetSimplexCode(K, 3);
> I in AllInformationSets(C);
true
> s := #SMAut-1;  s;
6
> [ LinearCode(GeneratorMatrix(C)*SMAut[i]) eq C : i in [1..s+1] ];
[true, true, true, true, true, true, true];
> IsPermutationDecodeSet(C, I, SMAut, s);
true

> c := C ! [0,1,1,1,1,0,0,0,0,a^2,a^2,a^2,a^2,a,a,a,a,1,1,1,1];
> c in C;
true
> u := c;
> u[1] := c[1] + a;
> u[2] := c[2] + a^2;
> u[3] := c[3] + a;
> u[4] := c[4] + a^2;
> u[5] := c[5] + a;
> u[6] := c[6] + a^2;
> u in C;
false
> isDecoded, uDecoded := PermutationDecode(C, I, SMAut, s, u);
> isDecoded;
true
> uDecoded eq c;
true

Run in calculatorCopy input