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 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:

This exercise belongs to the chapter "Basic structure of a product code".
Reference is made in particular to the section "Basic structure of a product code".
The two component codes are also covered in the "Exercise 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 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$.

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