Aufgaben:Exercise 1.07: Check and Generator Matrix of the HC (7, 4, 3)

• Return to book

Parity-check equations of the
$(7, 4, 3)$  Hamming code

The graph shows the parity-check equations of the  $(7, 4, 3)$  Hamming code,  which has already been considered in detail in the  "Exercise 1.6"  and described using the code table.

In this task,  this code is now characterized by two matrices  –  as is common in Channel Coding:

• The parity-check matrix  $\boldsymbol{\rm H}$  is a matrix with  $m = n - k$  rows and  $n$  columns.  It describes the  $m = 3$  parity-check equations,  where the first row refers to the elements of the red circle and the second row refers to those of the green circle.  The last row gives the modulo-2 sum of the blue circle.

• A second description possibility is provided by the generator matrix  $ \boldsymbol{\rm G}$  with  $k$  rows and  $n$  columns.  It gives the relationship between the information words  $ \underline{u}$  and the code words  $\underline{x}$ :

$$ \underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.$$

From this and from the equation  $ \boldsymbol{\rm H} · \underline{x}^{\rm T} = \underline{0}$  the relation between the parity-check matrix  $ \boldsymbol{\rm H}$  and the generator matrix  $ \boldsymbol{\rm G}$  can be established:

$$\underline{x}^{\rm T} = { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} = \underline{0}\hspace{0.5cm} \forall \hspace{0.15cm}\underline{u} \in {\rm GF}(2^k)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.$$

Note that in these equations  "$\underline{0}$"  denotes a row vector with  $k$  elements and  "$\boldsymbol{\rm 0}$"  denotes a matrix with  $m$  rows and  $k$  columns.  All elements of  "$\underline{0}$"  or  "$\boldsymbol{\rm 0}"$  are zero.

If the code is a  systematic code, the description variables  $\boldsymbol{\rm H}$  and  $\boldsymbol{\rm G}$  can be written with the aid of  identity matrices  $\boldsymbol{\rm I}$  as follows:

$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right) \hspace{0.5cm} \Rightarrow \hspace{0.5cm} { \boldsymbol{\rm H}} = \left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$

$\boldsymbol{\rm P}$  is thereby a matrix with  $k$  rows and  $m$  columns.  Accordingly, the transposed matrix  ${ \boldsymbol{\rm P}}^{\rm T}$  consists of  $m$  rows and  $k$  columns.

Hints :

• This exercise belongs to the chapter  "General Description of Linear Block Codes".

• Reference is made in particular to the sections  "Code definition by the parity-check matrix"  and  "Code definition by the generator matrix".

Questions

1

What is the format of the parity-check matrix  $\boldsymbol{\rm H}$?

$\text{number of columns} \ = \ $

$\text{number of rows} \ = \ $

2

Which statements are true regarding the parity-check matrix  $\boldsymbol{\rm H}$ ?

	The first row is:   $(1101100)$.
	The second row is:   $(0111010)$.
	The third row is:   $(1011001)$.

3

How can you tell that there is a systematic code?

	In each row there is an even number of ones.
	At the end of  $\boldsymbol{\rm H}$  you can recognize an identity matrix.
	The middle column of  $\boldsymbol{\rm H}$  is occupied by ones.

4

Give the generator matrix  $\boldsymbol{\rm G}$ . Which statements are true?

	The first row is:   $(1000101)$,
	The second row is:   $(0111010)$,
	The last row is:   $(0001111)$.

5

What code word  $x_{11}$  results for  $u_{11} = (1, 0, 1, 1)$?

	$x_{11} = (1, 1, 1, 1, 0, 0, 0),$
	$x_{11} = (1, 0, 1, 1, 0, 0, 0),$
	$x_{11} = (1, 0, 1, 1, 0, 0, 1).$

Solution

Solution

(1)  The number of columns of the parity-check matrix  $\boldsymbol{\rm H}$  is equal to the code length  $\underline{n = 7}$.

The number of rows is equal to the number of parity-check equations,  in this case  $\underline{m = 3} = n - k$.

(2)  A comparison with the graph in the information section shows that  all statements  are true.  With

$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3)$$

results in the following parity-check equations:

$$x_1 \oplus x_2 \oplus x_4 \oplus x_5 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (red\hspace{0.15cm}circle)}\hspace{0.05cm},$$

$$x_2 \oplus x_3 \oplus x_4 \oplus x_6 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (green\hspace{0.15cm}circle)}\hspace{0.05cm},$$

$$ x_1 \oplus x_3 \oplus x_4 \oplus x_7 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (blue\hspace{0.15cm}circle)}\hspace{0.05cm}.$$

This gives for the parity-check matrix:

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

The specification of  $\boldsymbol{\rm H}$  is not unique.  A different order of the parity-check equations would,  for example,  result in a second parity-check matrix which is also correct:

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

(3) Statement 2  is correct:

• For a systematic code,  the parity-check matrix can be represented in the following form:

$${ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$

• In the present example,  with  $m = 3$:

$${ \boldsymbol{\rm P}}^{\rm T} = \begin{pmatrix} 1 &1 &0 &1\\ 0 &1 &1 &1\\ 1 &0 &1 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm I}}_3 = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

(4) Statement 1 and 3  are correct:

• In general,  the relationship between the  $m×n$  parity-check matrix and the  $k×n$  generator matrix is:

$${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}$$

• The matrix  "$ \boldsymbol{\rm 0}$"  is filled with zeros only and has  $m$  rows and  $k$  columns.  For a systematic code – like here – the following relation exists:

$${ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm}{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.05cm}.$$

• In the present case,  one  obtains:

$${ \boldsymbol{\rm I}}_4 = \begin{pmatrix} 1 &0 &0 &0\\ 0 &1 &0 &0\\ 0 &0 &1 &0\\ 0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1 \end{pmatrix}\hspace{0.3cm}\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm G}} = \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}.$$

(5)  The equation to be used is:

$$\underline{x}_{11} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} \underline{u}_{11} \cdot { \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &1 &1 \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 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

A comparison with the table of  "Exercise 1.6"  shows the correctness of this calculation   ⇒   Answer 3.

• The answer 1 cannot be correct already because this does not correspond to any systematic coding.
• (1, 0, 1, 1, 0, 0)  according to suggestion 2 is not a valid code word.  Hereby the blue parity-check equation in the graphic in the information section is not fulfilled.