# Coset Leaders

## `CosetLeaders(C): Code -> { @ ModTupFldElt  @}, Map`

Given a code $C$ with ambient space $V$ over a finite field, return a set of coset leaders (vectors of minimal weight in their cosets) for $C$ in $V$ as an indexed set of vectors from $V$. Note that this function is only applicable when $V$ and $C$ are small. This function also returns a map from the syndrome space of $C$ into the coset leaders (mapping a syndrome into its corresponding coset leader).

## `Example: Coset Leaders (ex-6ef726)`

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.

```magma
> 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$.

```magma
> 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$ using $C$ by setting $w$ to be the product of $i$ by the generator matrix of $C$.

```magma
> 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 $7$-th coordinate (so $r$ is the “received vector”).

```magma
> 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.

```magma
> 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)

```