Aufgaben:Exercise 4.7Z: Principle of Syndrome Decoding

• Return to book

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:

• 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 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:

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