Syndrome decoding

We construct a Hamming code C, encode an information word using C, introduce one error, and then decode by calculating the syndrome of the ``received'' vector and applying the CosetLeaders map to the syndrome to recover the original vector.

First we set C to be the third-order Hamming code over the finite field with two elements.

> C := HammingCode(GF(2), 3);
> C;
[7, 4, 3] Hamming code (r = 3) over GF(2)
Generator matrix:
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]

Then we set L to be the set of coset leaders of C in its ambient space V and f to be the map which maps the syndrome of a vector in V to its coset leader in L.

> L, f := CosetLeaders(C);
> L;
{@
    (0 0 0 0 0 0 0),
    (1 0 0 0 0 0 0),
    (0 1 0 0 0 0 0),
    (0 0 1 0 0 0 0),
    (0 0 0 1 0 0 0),
    (0 0 0 0 1 0 0),
    (0 0 0 0 0 1 0),
    (0 0 0 0 0 0 1)
@}

Since C has dimension 4, the degree of the information space I of C is 4. We set i to be an ``information vector'' of length 4 in I, and then encode i by C by setting w to be the product of i by the generator matrix of C.

> I := InformationSpace(C);
> I;         
Full Vector space of degree 4 over GF(2)
> i := I ! [1, 0, 1, 1];
> w := i * GeneratorMatrix(C);
> w;         
(1 0 1 1 0 1 0)

Now we set r to be the same as w but with an error in the 7th coordinate (so r is the ``received vector'').

> r := w;         
> r[7] := 1;
> r;                
(1 0 1 1 0 1 1)

Finally we let s be the syndrome of r with respect to C, apply f to s to get the coset leader l, and subtract l from r to get the corrected vector v. Finding the coordinates of v with respect to the basis of C (the rows of the generator matrix of C) gives the original information vector.

> s := Syndrome(r, C);
> s;
(1 1 1)
> l := f(s);
> l;    
(0 0 0 0 0 0 1)
> v := r - l;
> v;                     
(1 0 1 1 0 1 0)
> res := I ! Coordinates(C, v);
> res;
(1 0 1 1)

Next Group: Weight distribution of a Reed-Muller code Previous Group: Construction of Goppa codes