Exercise 1.09: Extended Hamming Code

• Return to book

$\text{HC (7, 4)}$  (yellow background) and  $\text{(8, 4)}$  extension  (green background).

Two codes are to be compared,  whose code tables are given on the right.

• The first four bits of each code word  $\underline{x}$  are equal to the respective information word  $\underline{u}$  (black font).

• Then follow  $m = n- k$  parity bit  (red font).

The systematic  $\text{(7, 4)}$  Hamming code has already been discussed in  "Exercise 1.6"  and  "Exercise 1.7".  The parity-check matrix and generator matrix of this code are given as follows:

$${ \boldsymbol{\rm H}}_1 = \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},$$

$${ \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}.$$

In the further course of the exercise this  (yellow highlighted)  code is called  $\mathcal{C}_{1}$.

The right column in the above table specifies a block code with parameters  $n = 8$  and  $k = 4$,  usually referred to in the literature as the  "Extended Hamming Code".  We refer to this code  (highlighted in green)  in the following  $\mathcal{C}_{2}$  and denote its parity-check matrix by  ${ \boldsymbol{\rm H}}_{2}$  and the corresponding generator matrix by  ${ \boldsymbol{\rm G}}_{2}$.

The questions for this exercise are related to

• the  "code rate",
• the  "minimum distance"  between two code words,
• the  "parity-check matrix"  and the  "generator matrix"  of the extended  $\text{(8, 4)}$  Hamming code.

Hints:

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

• Note in the solution that  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$  are each  "systematic codes".

• The following  "Exercise 1.9Z"  deals with the extension of codes in somewhat more general terms.

Questions

1

Specify the code rates of  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}R \ = \ $

2

Give the minimum distances of  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

3

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

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

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

4

Derive the equation for the code bit   $x_ {8} (= p_{4})$   from the code table. Which specification is correct?

	$x_{8} = 0.$
	$x_{8} = x_{1}⊕x_{2}⊕x_{4}⊕x_{5}.$
	$x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$

5

Which statements are true for  ${ \boldsymbol{\rm H}}_{2}$?  Hint:  Correct are three out of four answers.

	Row 1 reads:   $1 1 0 1 1 0 0 0$.
	Row 2 reads:   $0 1 1 1 0 1 0 0$.
	Row 3 reads:   $0 0 0 0 1 1 1 1$.
	Row 4 reads:   $1 1 1 1 1 1 1 1$.

6

Which transformation is allowed for the last row of  ${ \boldsymbol{\rm H}}_{2}$ ?

	$1 1 1 1 1 1 1 1 → 0 0 0 0 0 0 0 0,$
	$1 1 1 1 1 1 1 1 → 1 1 1 0 0 0 0 1,$
	$1 1 1 1 1 1 1 1 → 0 0 1 0 1 0 0 0.$

7

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

	${ \boldsymbol{\rm G}}_{2}$  has same format as matrix  ${ \boldsymbol{\rm G}}_{1}$  of the  $\text{(7, 4)}$ code.
	${ \boldsymbol{\rm G}}_{2}$  starts like ${ \boldsymbol{\rm G}}_{1}$  with a diagonal matrix  ${ \boldsymbol{\rm I}}_{4}$.
	${ \boldsymbol{\rm G}}_{2}$  in the considered example has the same format as  ${ \boldsymbol{\rm H}}_{2}$ .

Solution

Solution

(1)  The corresponding equation for the code rate in both cases is  $R = k/n\text{:}$

• $\mathcal{C}_{1} \text{:} \ n = 7, k = 4\ ⇒ \ R = 4/7 \underline {= 0.571},$

• $\mathcal{C}_{2} \text{:} \ n = 8, k = 4 \ ⇒ \ R = 4/8 \underline { =0.5}.$

(2)  The minimum distance of the  $(7, 4, 3)$  Hamming code  $\mathcal{C}_{1}$  is  $d_{\rm min} \underline{= 3}$,  which can be read from the naming alone.

• From the table in the information section,  it can be seen that for the extended Hamming code  $d_{\rm min} \underline{= 4}$  holds.

• $\mathcal{C}_{2}$  is therefore also called in the literature a  $\rm (8, 4, 4)$  block code.

(3)  The parity-check matrix  ${ \boldsymbol{\rm H}}$  generally consists of  $n$  columns and  $m = n - k$ rows,  where  $m$  indicates the number of parity-check equations.

• For the  $(7, 4, 3)$  Hamming code,  ${ \boldsymbol{\rm H}}$  is a  $3 × 7$  matrix.

• For the extended Hamming code   ⇒   $\mathcal{C}_{2}$,  on the other hand:  $\underline{n = 8}$  (column number)  and  $\underline{m = 4}$  (row number).

(4)  From the code table in the information section you can see that only  answer 3  is correct.

• The parity bit  $p_{4}$  is to be determined in such a way that the modulo 2 sum over all bits of the code word results in the value  $0$.

(5)  It should first be noted that the specification of the parity-check matrix is never unambiguous,  if only because the order of the parity-check equations is interchangeable.

• However,  considering that only one of the given rows is wrong,  ${ \boldsymbol{\rm H}}_{2}$  is uniquely determined:

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

• Correct are therefore the  statements 1, 2 and 4.  The rows of this parity-check matrix represent the four parity-check equations in this order:

$$x_1\oplus x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$

$$x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$

$$x_1 \oplus x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},$$

$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0 \hspace{0.05cm}.$$

(6)  Correct is  answer 2:

• This result is obtained by replacing the last row with the modulo 2 sum over all four rows,  which is allowed.

• Proposition 1 does not represent a parity-check equation.

• Proposal 3 represents the parity-check equation  $x_{3}⊕x_{5} = 0$,  which also does not correspond to the facts.

According to the correct solution suggestion 2,  on the other hand,  the parity-check equation becomes

$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$

is replaced by the following new parity-check equation:

$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$

• The modified parity-check matrix is now:

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

(7)  After this matrix manipulation,  ${ \boldsymbol{\rm H}}_{2}$  is in the form typical for systematic codes:

$${ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} m = 4 {\rm :}\hspace{0.3cm}{ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_4 \right) \hspace{0.05cm}.$$

• Thus,  the generator matrix is:

$${ \boldsymbol{\rm G_{2}}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 &1\\ 0 &1 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$

So the  statements 2 and 3  are correct:

• ${ \boldsymbol{\rm G}}_{2}$  starts like  ${ \boldsymbol{\rm G}}_{1}$  $($see specification sheet$)$  with a diagonal matrix  ${ \boldsymbol{\rm I}}_{4}$,  but unlike  ${ \boldsymbol{\rm G}}_{1}$  now has 8 columns.

• In the present case  $n = 8, k = 4 \ ⇒ \ m = 4$  both  ${ \boldsymbol{\rm G}}_{2}$  and  ${ \boldsymbol{\rm H}}_{2}$  are  $4×8$  matrices respectively.