Syndrome decoding

Let $ C$ be a linear code of length over $ \mathbb{F}_q$ having check matrix $ H$. Let $ V=\mathbb{F}_q^n$.

Definition 3.8.1   Let $ {\bf v}\in V$. The set

$\displaystyle {\bf v}+C=\{ {\bf v}+{\bf c}\ \vert\ {\bf c}\in C\}, $

is called the coset of v. The set of all cosets is denoted $ V/C$. The vector $ S({\bf v})=H{\bf v}$ is called the syndrome of v. The set of all cosets is denoted $ Im(H)$ or $ H(V)$.

Proposition 3.8.2   The cosets are in 1-1 correspondence with the cosets: there is a bijection

$\displaystyle \rho : V/C \rightarrow H(V), $

given by $ \rho({\bf v}+C)=H({\bf v})$.

proof: First, we show that the map is well-defined (i.e., independent of the choice of coset representative. For all $ {\bf u},{\bf v}\in V$, we have $ {\bf u}+C={\bf v}+C$ if and only if $ {\bf u}-{\bf v}\in C$ if and only if $ H({\bf u}-{\bf v})=0$ if and only if $ H{\bf u}=H{\bf v}$. Thus $ \rho$ is well-defined. $ \rho$ is 1-1 by the same reasoning. $ \rho$ is onto by definition. $ \Box$

Let $ {\bf v}\in V$. An element in $ {\bf v}+C$ of lowest weight is called a coset leader, and intuitively represents the ``mostly likely error vector''.

Algorithm:

This algorithm is fast, assuming that assessing the look-up table takes no time, but may require a lot of time and memory initially to build the look-up table in the first place.

Example 3.8.3   If $ C$ is the code over $ \mathbb{F}_2$ with check matrix given by

\begin{displaymath} H=\left( \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\... ...& 0 & 1 & 0 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array}\right). \end{displaymath}

Here is the look-up table:

syndrome coset leader
$ (0,0,0)$ $ (0,0,0,0,0,0,0)$
$ (1,0,0)$ $ (0,0,0,0,1,0,0)$
$ (0,1,0)$ $ (0,0,0,0,0,1,0)$
$ (0,0,1)$ $ (0,0,0,0,0,0,1)$
$ (1,1,0) $ $ (1,0,0,0,0,0,0)$
$ (1,0,1)$ $ (0,0,0,1,0,0,0)$
$ (0,1,1)$ $ (0,1,0,0,0,0,0)$
$ (1,1,1)$ $ (0,0,1,0,0,0,0)$

Exercise 3.8.4   Let $ C$ be the code in Example 3.8.3. Decode $ {\bf v}=(1,1,1,1,1,0,0)$ using the syndrome decoding algorithm. (Ans: $ {\bf v}=(1,0,1,1,1,0,0)$.)

Exercise 3.8.5   Count the number of vectors in a ball of radius $ 1$ in $ \mathbb{F}_2^7$.

Exercise 3.8.6   Show that the number of vectors in a ball of radius $ r$ in $ F^n$ does not depend on the radius. In other words, if $ v,v'\in F^n$ then show $ \vert B(v,r,F^n)\vert= \vert B(v',r,F^n)\vert$.

Exercise 3.8.7   In Example 3.3.2, the code $ C$ has minimum distance $ 2$.

Exercise 3.8.8   In Example 3.3.6, the code $ C$ has minimum distance $ 2$.

Exercise 3.8.9   Pick a book and check that its ISBN satisfies the condition $ x_1+2x_2+3x_3+...+9x_9+10x_{10}\equiv 0\ ({\rm mod}\ 11)$, in the notation of Example 3.3.6.

Exercise 3.8.10   For the code in Example 3.3.2, use the nearest neighbor algorithm to decode $ (1,0,0,1,0,0)$ and $ (1,0,1,0,1,1)$.

Exercise 3.8.11   Consider the code with generator matrix

\begin{displaymath} G= \left( \begin{array}{ccccccc} 1&0&0&0&1&1&1\ 0&1&0&0&0&1&1\ 0&0&1&0&1&0&1\ 0&0&0&1&1&1&0 \end{array}\right). \end{displaymath}

Find the codeword obtained by encoding $ (1,0,1,1)$.

Exercise 3.8.12   For $ G$ for the code in Example 3.3.2.

Exercise 3.8.13   Prove this Proposition 3.4.11.

Exercise 3.8.14   The vector $ 1010011$ was receieved. Assuming only one error was made, use the nearest neighbor algorithm to decode it.

Exercise 3.8.15   Show that the Hamming $ [7,4,3]$-code has minimum distance $ 3$.



David Joyner 2007-09-03