|
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.
While syndrome decoding applies to any linear code it is restricted
to codes having small codimension since it needs to calculate the
coset leaders.
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.
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.
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)
]
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.
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.
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.
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)
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;
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
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 ⊆{1, ..., 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 Sym(n) acting on the set
{1, ..., n}. In either case S must be an s-PD-set for
C with respect to I;
- --
- and an integer s ∈{1, ..., 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
∑i=1s ((k)choose(i)) .((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], [GrpPermElt], RngIntElt, ModTupFldElt -> BoolElt, ModTupFldElt
Given
- --
- an [n, k] linear code C over a finite field K;
- --
- an information set I ⊆{1, ..., 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 Sym(n) acting on the set
{1, ..., n}. In either case S must be an s-PD-set for
C with respect to I;
- --
- an integer s ∈{1, ..., 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'∈C as the decoded version of u ∈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 ∈C and e ∈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≤t.
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 ⊆{1, ..., 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 Sym(n) acting on the set
{1, ..., n}. In either case S must be an s-PD-set for
C with respect to I;
- --
- an integer s ∈{1, ..., 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).
Given a finite field K of cardinality q, and a positive integer m,
the intrinsic constructs the [n=(qm - 1)/(q - 1), m, qm - 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= ⌊((qm - 1)/(m(q - 1))) ⌋ - 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 [FKM12].
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, ..., n }.
Given a positive integer m, the intrinsic constructs the
[2m, m + 1, 2m - 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 ⊆{1, ..., 2m } 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= ⌊(2m/(m + 1)) ⌋ - 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 2m over GF(2)
described in [BV16]. The function also returns the elements of S
represented as elements in the symmetric group Sym(2m) of permutations
on the set {1, ..., 2m }.
> 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
> 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|