Exercise 4.7Z: Principle of Syndrome Decoding
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
Solution
- 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.
