Syndrome Decoding

Theorem

Let $C$ be a linear $\tuple {n, k}$-code whose master code is $\map V {n, p}$

To decode a given vector $v$ of $\map V {n, p}$, the syndrome of $v$ can be used as follows.

Create an array $T$ of $2$ column consisting of the following:

The top row contains:

in column $1$: the zero of $C$

The $r$th row subsequent contains:

in column $1$: any element of $\map V {n, p}$ of minimum weight which is not already included in the first $r - 1$ rows

To decode a given vector $v$ of $\map V {n, p}$:

Calculate its syndrome

Find it in column $2$ of $T$

See what is in column $1$ of $T$, and call it $u$, say

Subtract $u$ from $v$.

Let $C$ be the linear code:

$C = \set {000000, 100110, 010101, 110011, 001011, 101101, 011110, 111000}$

Then the Syndrome Decoding table $T$ for $C$ is:

$\begin{array} {cc}

000000 & 000 \\ 100000 & 110 \\ 010000 & 101 \\ 001000 & 011 \\ 000100 & 100 \\ 000010 & 010 \\ 000001 & 001 \\ 100001 & 111 \\ \end{array}$

1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $6$: Error-correcting codes: Example $6.22$