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

$${\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

$$\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:

• Precomputation. Compute all syndromes ${\bf s}=H{\bf w}$, for ${\bf w}\in V$ and the corresponding coset leaders $L({\bf s})$. (The table of values of the function $f$ is called the look-up table.)

• If v is the received vector, compute ${\bf s}=H{\bf v}$.

• Let ${\bf e}=L({\bf s})$ be the corresponding coset leader obtained from the look-up table.

• Decode v as ${\bf c}={\bf v}-{\bf e}$.

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

$$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).$$

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

$$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).$$

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