Aufgaben:Exercise 4.7Z: Principle of Syndrome Decoding

• Return to book

Coset leader for the code under consideration  $\rm HC \ (7, \ 4, \ 3)$

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:

• The exercise refers to the chapter  "Basic Product Codes"  and is intended as a supplement to  $\text{Exercise 4.7}$.

• Similar task settings were covered in  $\text{Exercise 1.11}$  and  $\text{Exercise 1.11Z}$  from chapter  "Decoding Linear Block Codes".

• The relationship between generator matrix  $\mathbf{G}$  and parity-check matrix  $\mathbf{H}$  of systematic codes is given in chapter  "General Description of Linear Block Codes".

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

Solution

(1)  Correct is 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)$$

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

(2)  Correct are 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 proposed solution 1:

• According to the statements in the chapter "Decoding of Linear Block Codes", $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$ can be written.
• 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 solutions 2, 3, and 4:

• The first statement is false because the first two rows of the transposed parity-check matrix $\mathbf{H}^{\rm T}$ summed $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} ≠ \underline{s}_7$ results in.
• Statements 2, 3 and 4, on the other hand, 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.