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

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  $\text{Exercise 4.6Z}$,  the 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:

• This exercise belongs to the chapter  "Basics of Product Code".

• Reference is also made to the section  "Basic structure of a product code".

• The two component codes are also covered in the  $\text{Exercise 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. column:   $\underline{u} = (0, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 1, \, 0, \, 1, \, 1)$.
	2. column:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 0, \, 1, \, 1, \, 0, \, 1)$.
	3. column:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 0, \, 0, \, 1, \, 1)$.
	4. column:   $\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 is  $(1, \, 1, \, 0)$.
	The second row is  $(1, \, 0, \, 1)$  and the second column is  $(0, \, 0, \, 0)$.
	The third row is  $(0, \, 0, \, 0)$  and the third column is  $(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:

1. The given first column is correct if only because it coincides with a row  $($the third$)$  of the generator matrix $\mathbf{G}_2$.
2. The third column of the two-dimensional code word should be identical to the second column,  since the same code word  $(1, \, 0, \, 1)$  is assumed.
3. 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$.
4. 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)  Given on the right are the complete code tables

• of the Hamming code $(7, \ 4, \ 3)$,  and

• of the truncated Hamming code $(6, \ 3, \ 3)$.

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