Exercise 4.6: Product Code Generation

From LNTwww
Revision as of 17:50, 30 November 2022 by Guenter (talk | contribs)

Used component codes

A  $\rm product\:code \ (42, \ 12)$  shall be generated, based on the following component codes:

  • the Hamming code  $\rm HC \ (7, \ 4, \ 3)$  ⇒   $\mathcal{C}_1$,
  • the truncated Hamming code $\rm HC \ (6, \ 3, \ 3)$   ⇒   $\mathcal{C}_2$.

The corresponding code tables are given on the right, with three rows incomplete in each case. These are to be completed by you.

The code word belonging to an information block  $\underline{u}$  generally results according to the equation  $\underline{x} = \underline{u} \cdot \mathbf{G}$. As in the  "Exercise 4.6Z"  following generator matrices are assumed here:

$${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.8cm} { \boldsymbol{\rm G}}_2 = \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}.$$

Throughout the exercise, apply to the information block:

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

Searched for according to the nomenclature in section  "Basic structure of a product code":

  • the parity-check matrix  $\mathbf{P}^{(1)}$  with respect to the horizontal code  $\mathcal{C}_1$,
  • the parity-check matrix  $\mathbf{P}^{(2)}$  with respect to the vertical code  $\mathcal{C}_2$,
  • the checks–on–checks matrix  $\mathbf{P}^{(12)}$.





Hints:



Questions

1

What are the results of row coding with the  $(7, \ 4, \ 3)$ code  $\mathcal{C}_1$?

1. row:   $\underline{u} = (0, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 1)$.
2. row:   $\underline{u} = (0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$.
3. row:   $\underline{u} = (1, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0)$.

2

What are the results of column coding with the  $(6, \ 3, \ 3)$ code  $\mathcal{C}_2$?

1. row:   $\underline{u} = (0, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 1, \, 0, \, 1, \, 1)$.
2. row:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 0, \, 1, \, 1, \, 0, \, 1)$.
3. row:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 0, \, 0, \, 1, \, 1)$.
4. row:   $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \,0, \, 0)$.

3

What statements apply to the checks–on–checks matrix?

The first row is  $(1, \, 0, \, 1)$  and the first column  $(1, \, 1, \, 0)$.
The second row is  $(1, \, 0, \, 1)$  and the second column  $(0, \, 0, \, 0)$.
The third row is  $(0, \, 0, \, 0)$  and the third column  $(0, \, 0, \, 0)$.


Solution

(1)  Correct are the proposed solutions 1 and 3:

In general $\underline{x} = \underline{u} \cdot \mathbf{G}$. From this follows for

  • the first row vector:
$$\begin{pmatrix} 0 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &1 &1 &0 &1 &0 &1 \end{pmatrix} \hspace{0.05cm},$$
  • the second row vector:
$$\begin{pmatrix} 0 &0 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm},$$
  • the third row vector:
$$\begin{pmatrix} 1 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &1 &1 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm}.$$


(2)  Correct are the proposed solutions 1, 2 and 4:

$$\begin{pmatrix} 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$
$$\begin{pmatrix} 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &0 &1 &1 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

To this subtask is to be noted further:

  • The given first column is correct if only because it coincides with a row (the third) of the generator matrix $\mathbf{G}_2$.
  • The third column of the 2D code word should be identical to the second column, since the same code word $(1, \, 0, \, 1)$ is assumed.
  • However, the given vector $(1, \, 1, \, 0, \, 0, \, 1, \, 1)$ cannot be correct if only because $\mathcal{C}_2$ is a systematic code just like $\mathcal{C}_1$.
  • Also the truncated $(6, \ 3, \ 3)$–Hamming code $C_2$ is linear, so that the assignment $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \ \underline{x} = (0, \, 0, \, 0, \, 0)$ can be stated without calculation.


Complete code tables

(3)  The complete code tables

  • of the Hamming code $(7, \ 4, \ 3)$, and
  • of the truncated Hamming code $(6, \ 3, \ 3)$ are given on the right.

One can see from this (without it being of interest for this exercise) that the codes considered here each have Hamming distance $d_{\rm min} = 3$.

Wanted product code



The left graph shows the result of the whole coding. At the bottom right you can see the checks–on–checks matrix of dimension $3 × 3$.
Concerning the subtask (3) the suggested solutions 1 and 2 are correct:

  • It is a coincidence that here in the checks–on–checks matrix two rows and two columns are identical.
  • It doesn't matter whether rows 4 to 6 of the total matrix are obtained using the code $\mathcal{C}_1$ or columns 5 to 7 are obtained using the code $\mathcal{C}_2$.