Exercise 4.6: Product Code Generation

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

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

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

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

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