Exercise 4.7Z: Principle of Syndrome Decoding

From LNTwww

Syndrome table for code  $\mathcal{C}_1$

The syndrome decoding was already treated in detail in the chapter  "Decoding of Linear Block Codes"

With all Hamming codes,  which are as well known perfect,  this gives a decoding result as good as with the  $($generally$)$ clearly more complicated maximum likelihood decoding.

For syndrome decoding one proceeds as follows:

  • One forms the syndrome from the received vector  $\underline{y}$  of length  $n$  and the parity-check matrix  $\mathbf{H}$:
$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}, \hspace{0.5cm}{\rm Note\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$
  • The received word  $\underline{y} = \underline{x} \ {\rm (code\:word)} + \underline{e} \ {\rm (error\:vector)}$  is not necessarily an element of  ${\rm GF}(2^m)$,  but certainly an element of  ${\rm GF}(2^n)$  and it holds because of   $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$   equally:
$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.05cm}. $$
  • Many error patterns  $\underline{e}$  lead to the same syndrome  $\underline{s}$. One now groups those error patterns with the same syndrome  $\underline{s}_{\mu}$  to the  "coset  ${\it \Psi}_{\mu}$".
  • The  "coset leader"  $\underline{e}_{\mu}$  is the error vector that has the lowest Hamming weight within the class  ${\it \Psi}_{\mu}$  and is accordingly the most probable.


The table above shows the list of the class leaders  $\underline{e}_{\mu}$  for each  $\underline{s}_{\mu}$  in the Hamming code  $\rm HC \ (7, 4, 3)$. This table is needed for the subtask  (1).

A similar table is to be created for the truncated Hamming code  $\rm HC \ (6, 3, 3)$.  This has already been used in the  $\text{Exercise 4.6}$  and the  $\text{Exercise 4.6Z}$  and is given by its generator matrix:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

Unlike the original  $\rm (7, 4, 3)$  Hamming code,  the shortened  $\rm (6, 3, 3)$  Hamming code is not perfect, so a single-error coset leader  $\underline{s}_{\mu}$  cannot be found for all possible  $\underline{e}_{\mu}$.




Hints:



Questions

1

The received word be  $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 0)$,  the syndrome  $\underline{s} = (0, \, 1, \, 1)$.  For which code word  $\underline{x}$  of  $\mathcal{C}_1$  does the syndrome decoder decide?

The most likely code word is  $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$.
The most likely code word is  $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$.
The most likely code word is  $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$.

2

What statements hold for the parity-check matrix  $\mathbf{H}$  of the truncated code  $\mathcal{C}_2$?

This is a  $4 × 6$  matrix.
The first row of this matrix is  "$110100$".
The second row of this matrix is  "$101010$".
The third row of this matrix is  "$011001$".

3

What syndrome  $\underline{s}$  results for the error pattern  $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$?

$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_0 = (0, \, 0, \, 0)$,
$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_1 = (0, \, 0, \, 1)$,
$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_7 = (1, \, 1, \, 1)$.

4

Which of the following statements are true regarding single-error patterns?

single-error pattern   $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0)$   ⇒   syndrome $\underline{s}_6 = (1, \, 1, \, 0)$,
single-error pattern   $\underline{e} = (0, \, 1, \, 0, \, 0, \, 0, \, 0)$   ⇒   syndrome $\underline{s}_5 = (1, \, 0, \, 1)$,
single-error pattern   $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0)$   ⇒   syndrome $\underline{s}_3 = (0, \, 1, \, 1)$,
single-error pattern   $\underline{e} = (0, \, 0, \, 0, \, 1, \, 0, \, 0)$   ⇒   syndrome $\underline{s}_4 = (1, \, 0, \, 0)$,
single-error pattern   $\underline{e} = (0, \, 0, \, 0, \, 0, \, 1, \, 0)$   ⇒   syndrome $\underline{s}_2 = (0, \, 1, \, 0)$,
single-error pattern   $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$   ⇒   syndrome $\underline{s}_1 = (0, \, 0, \, 1)$,

5

Which of the following error patterns lead to the syndrome  $\underline{s}_7 = (1, \, 1, \, 1)$?

$\underline{e} = (1, \, 1, \, 0, \, 0, \, 0, \, 0)$,
$\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 1)$,
$\underline{e} = (0, \, 1, \, 0, \, 0, \, 1, \, 0)$,
$\underline{e} = (1, \, 1, \, 1, \, 1, \, 1, \, 1)$.


Solution

(1)  Correct is the  proposed solution 2:

  • From the  "syndrome table"  on the information page – valid for the  $\rm (7, 4, 3)$  Hamming code – it can be read that the syndrome   $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$  corresponds to the error pattern   $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$. Thus the code word
$$\underline{x} = \underline{y} \hspace{0.15cm}+ \hspace{0.15cm} \underline{y} = (0, 1, 1, 0, 1, 1, 0) \hspace{0.15cm}+ \hspace{0.15cm}(0, 0, 1, 0, 0, 0, 0) \hspace{0.15cm}= \hspace{0.15cm}(0, 1, 0, 0, 1, 1, 0)$$

is most likely and the syndrome decoder will output this as the result.


(2)  Correct are the  solutions 2, 3, and 4:

  • The parity-check matrix  $\mathbf{H}$  of the truncated  $\rm (6, 3)$  Hamming code  $C_2$  has  $m = n - k = 3$  rows and  $n$  columns. 
  • Consequently,  it is a  $3 × 6$  matrix   ⇒   statement 1 is false.
  • Since  $\mathcal{C}_2$  is also a systematic code,  the generator matrix  $\mathbf{G}$  can be represented  in the following form:
$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} = \left ( { \boldsymbol{\rm I}}_3 ; \hspace{0.15cm} { \boldsymbol{\rm P}} \right ) \hspace{0.5cm}{\rm mit }\hspace{0.5cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 1 &1 &0 \\ 1 &0 &1 \\ 0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • So it can be written for the parity-check matrix:
$${ \boldsymbol{\rm H}} = \left ( { \boldsymbol{\rm P}}^{\rm T} ; \hspace{0.15cm} { \boldsymbol{\rm I}}_3 \right ) = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • Here  $\mathbf{I}_3$  denotes a  $3 × 3$  diagonal matrix typical of the systematic code.
  • Proposed solutions 2, 3, and 4  are therefore correct:
  • Row 1:   $110100$,
  • Row 2:   $101010$,
  • Row 3:   $011001$.


(3)  Correct is the  proposed solution 1:

  • Thus,  for the error-free case   ⇒   $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$:
$$\underline{s}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \begin{pmatrix} 1 &1 &0 \\ 1 &0 &1 \\ 0 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_0.$$


(4)  All statements  are true,  as can be seen from the sample solution to the last subtask:

  • The rows of the transposed parity-check matrix,  read from top to bottom,  give the respective syndromes for the error patterns $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \hspace{0.05cm} \text{ ... } \hspace{0.05cm} , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$.


(5)  Correct are the  solutions 2, 3, and 4:

  • The first statement is false because the sum of the first two rows of the transposed parity-check matrix results in   $\mathbf{H}^{\rm T}$ summed $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} ≠ \underline{s}_7$.
  • The statements 2, 3 and 4 are correct:
  • First and last row: $\ (1, \, 1, \, 0) + (0, \, 0, \, 1) = (1, \, 1, \, 1) = \underline{s}_7$,
  • second and fifth row: $\ (1, \, 0, \, 1) + (0, \, 1, \, 0) = (1, \, 1, \, 1) = \underline{s}_7$,
  • The sum over all rows also gives  $\underline{s}_7$,  since there are exactly three  "ones"  in each matrix column.