Aufgaben:Exercise 4.6: Product Code Generation

• Return to book

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 codeword 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 on page  "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:

• This exercise belongs to the chapter  "Basic structure of a product code".
• Reference is made in particular to the page  "Basic structure of a product code".
• The two component codes are also covered in the  Aufgabe 4.6Z .

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

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 codeword should be identical to the second column, since the same codeword $(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 shortened 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$.