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 Anmerkung\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$

• The received word  $\underline{y} = \underline{x} \ {\rm (codeword)} + \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 minor 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  "Exercise 4.6"  and the  "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-w 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  "Exercise 4.7" .
• Similar exercises were covered in the  "Exercise 1.11"  and the  "Exercise 1.11Z"  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 codeword is  $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$.
	The most likely codeword is  $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$.
	The most likely codeword 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 &times 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 &times 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 &times 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.