Difference between revisions of "Aufgaben:Exercise 1.09: Extended Hamming Code"

From LNTwww
 
(3 intermediate revisions by one other user not shown)
Line 3: Line 3:
 
}}
 
}}
  
[[File:EN_KC_A_1_9.png|right|frame|$\text{(7, 4)}$ Hamming code (yellow background) <br>and&nbsp; $\text{(8, 4)}$ extension (green).]]
+
[[File:EN_KC_A_1_9_neu.png|right|frame|$\text{HC (7, 4)}$&nbsp; (yellow background) and&nbsp; $\text{(8, 4)}$&nbsp; extension&nbsp; (green background).]]
  
Two codes are to be compared, whose code tables are given on the right.  
+
Two codes are to be compared,&nbsp; whose code tables are given on the right.  
*The first four bits of each code word&nbsp; $\underline{x}$&nbsp; are equal to the respective information word&nbsp; $\underline{u}$&nbsp; (black font).  
+
*The first four bits of each code word&nbsp; $\underline{x}$&nbsp; are equal to the respective information word&nbsp; $\underline{u}$&nbsp; (black font).
*Then follow&nbsp; $m = n- k$&nbsp; parity bit (red font).
+
 +
*Then follow&nbsp; $m = n- k$&nbsp; parity bit&nbsp; (red font).
  
  
The systematic&nbsp; $\text{(7, 4)}$-Hamming code has already been discussed in&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|Exercise 1.6]]&nbsp; and&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|Exercise 1.7]]&nbsp;. The parity-check matrix and generator matrix of this code are given as follows:
+
The systematic&nbsp; $\text{(7, 4)}$&nbsp; Hamming code has already been discussed in&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|"Exercise 1.6"]]&nbsp; and&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|"Exercise 1.7"]].&nbsp; 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 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}.$$
 
:$${ \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&nbsp; $\mathcal{C}_{1}$&nbsp;.
+
In the further course of the exercise this&nbsp; (yellow highlighted)&nbsp; code is called&nbsp; $\mathcal{C}_{1}$.
 
 
  
The right column in the above table specifies a block code with parameters&nbsp; $n = 8$&nbsp; and&nbsp; $k = 4$&nbsp;, usually referred to in the literature as the "Extended Hamming Code". We refer to this code (highlighted in green) in the following&nbsp; $\mathcal{C}_{2}$&nbsp; and denote its parity-check matrix by&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; and the corresponding generator matrix by&nbsp; ${ \boldsymbol{\rm G}}_{2}$ .
+
The right column in the above table specifies a block code with parameters&nbsp; $n = 8$&nbsp; and&nbsp; $k = 4$,&nbsp; usually referred to in the literature as the&nbsp; "Extended Hamming Code".&nbsp; We refer to this code&nbsp; (highlighted in green)&nbsp; in the following&nbsp; $\mathcal{C}_{2}$&nbsp; and denote its parity-check matrix by&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; and the corresponding generator matrix by&nbsp; ${ \boldsymbol{\rm G}}_{2}$.
  
 
The questions for this exercise are related to
 
The questions for this exercise are related to
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|code rate]],
+
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"code rate"]],
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|minimum distance]]&nbsp; between two codewords,
+
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"minimum distance"]]&nbsp; between two code words,
*the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix|parity-check matrix]]&nbsp; and the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix|generator matrix]]&nbsp; of the extended&nbsp; $\text{(8, 4)}$ Hamming code.
+
*the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix|"parity-check matrix"]]&nbsp; and the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix|"generator matrix"]]&nbsp; of the extended&nbsp; $\text{(8, 4)}$&nbsp; Hamming code.
  
  
  
  
 +
Hints:
  
 +
*This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
  
 
+
*Note in the solution that&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$&nbsp; are each&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"systematic codes"]].
Hints:
+
 
+
*The following&nbsp; [[Aufgaben:Exercise_1.09Z:_Extension_and/or_Puncturing|"Exercise 1.9Z"]]&nbsp; deals with the extension of codes in somewhat more general terms.
*This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|General Description of Linear Block Codes]].
 
*Note in the solution that&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$&nbsp; are each&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|Systematic Codes]]&nbsp;.  
 
*The following&nbsp; [[Aufgaben:Exercise_1.09Z:_Extension_and/or_Puncturing|Exercise 1.9Z]]&nbsp; deals with the extension of codes in somewhat more general terms.
 
 
   
 
   
  
Line 44: Line 43:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Specify the code rates of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$&nbsp;.
+
{Specify the code rates of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$.
 
|type="{}"}
 
|type="{}"}
 
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $ { 0.571 3% }
 
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $ { 0.571 3% }
Line 50: Line 49:
  
  
{Give the minimum distances of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$&nbsp; .
+
{Give the minimum distances of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$.
 
|type="{}"}
 
|type="{}"}
 
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 3 }
 
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 3 }
Line 58: Line 57:
 
{What is the format of the parity-check matrix&nbsp; $\boldsymbol{\rm H}_{2}$&nbsp; of&nbsp; $\mathcal{C}_{2}$?
 
{What is the format of the parity-check matrix&nbsp; $\boldsymbol{\rm H}_{2}$&nbsp; of&nbsp; $\mathcal{C}_{2}$?
 
|type="{}"}
 
|type="{}"}
${\rm Spaltenzahl} \ = \ $ { 8 }
+
$\text{Number of columns} \ = \ $ { 8 }
${\rm Zeilenzahl} \ = \ $    { 4 }
+
$\text{Number of rows} \ = \ $    { 4 }
  
{Derive the equation for the code bit&nbsp; $x_ {8} (= p_{4})$&nbsp; from the code table. Which specification is correct?
+
{Derive the equation for the code bit &nbsp; $x_ {8} (= p_{4})$ &nbsp; from the code table. Which specification is correct?
 
|type="()"}
 
|type="()"}
  
Line 68: Line 67:
 
+ $x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$
 
+ $x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$
  
{Which statements are true for&nbsp; ${ \boldsymbol{\rm H}}_{2}$? ''Hint:'' &nbsp;Correct are 3 out of 4 answers.
+
{Which statements are true for&nbsp; ${ \boldsymbol{\rm H}}_{2}$?&nbsp; Hint: &nbsp;Correct are three out of four answers.
 
|type="[]"}
 
|type="[]"}
  
Line 82: Line 81:
 
- $1 1 1 1 1 1 1 1  →  0 0 1 0 1 0 0 0.$
 
- $1 1 1 1 1 1 1 1  →  0 0 1 0 1 0 0 0.$
  
{Give the corresponding generator matrix&nbsp; ${ \boldsymbol{\rm G}}_{2}$&nbsp;. Which statements are true?
+
{Give the corresponding generator matrix&nbsp; ${ \boldsymbol{\rm G}}_{2}$.&nbsp; Which statements are true?
 
|type="[]"}
 
|type="[]"}
- ${ \boldsymbol{\rm G}}_{2}$&nbsp; has same format as matrix&nbsp; ${ \boldsymbol{\rm G}}_{1}$ of a&nbsp; $\text{(7, 4)}$ code.
+
- ${ \boldsymbol{\rm G}}_{2}$&nbsp; has same format as matrix&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; of the&nbsp; $\text{(7, 4)}$ code.
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; starts like ${ \boldsymbol{\rm G}}_{1}$&nbsp; with a diagonal matrix&nbsp; ${ \boldsymbol{\rm I}}_{4}$ .
+
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; starts like ${ \boldsymbol{\rm G}}_{1}$&nbsp; with a diagonal matrix&nbsp; ${ \boldsymbol{\rm I}}_{4}$.
 
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; in the considered example has the same format as&nbsp; ${ \boldsymbol{\rm H}}_{2}$ .
 
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; in the considered example has the same format as&nbsp; ${ \boldsymbol{\rm H}}_{2}$ .
  
Line 97: Line 96:
 
===Solution===
 
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; The corresponding equation for the code rate in both cases is $R = k/n\text{:}$
+
'''(1)'''&nbsp; The corresponding equation for the code rate in both cases is&nbsp; $R = k/n\text{:}$
 
*$\mathcal{C}_{1} \text{:} \  n = 7, k = 4\  ⇒ \ R = 4/7  \underline {= 0.571},$
 
*$\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}.$
 
*$\mathcal{C}_{2} \text{:} \ n = 8, k = 4 \ ⇒ \ R = 4/8  \underline { =0.5}.$
  
  
  
'''(2)'''&nbsp; 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.  
+
'''(2)'''&nbsp; The minimum distance of the&nbsp; $(7, 4, 3)$&nbsp; Hamming code&nbsp; $\mathcal{C}_{1}$&nbsp; is&nbsp; $d_{\rm min} \underline{= 3}$,&nbsp; which can be read from the naming alone.
 +
 
 +
*From the table in the information section,&nbsp; it can be seen that for the extended Hamming code&nbsp; $d_{\rm min} \underline{= 4}$&nbsp; holds.
 +
 
 +
* $\mathcal{C}_{2}$&nbsp; is therefore also called  in the literature a&nbsp; $\rm (8, 4, 4)$&nbsp; block code.
  
*From the table on the information page, it can be seen that for the extended Hamming code $d_{\rm min} \underline{= 4}$ holds.
 
* $\mathcal{C}_{2}$ is therefore also called a (8, 4, 4) block code in the literature.
 
  
  
 +
'''(3)'''&nbsp; The parity-check matrix&nbsp; ${ \boldsymbol{\rm H}}$&nbsp; generally consists of&nbsp; $n$&nbsp; columns and&nbsp; $m = n - k$ rows,&nbsp; where&nbsp; $m$&nbsp; indicates the number of parity-check equations.
  
'''(3)'''&nbsp; 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&nbsp; $(7, 4, 3)$&nbsp; Hamming code,&nbsp; ${ \boldsymbol{\rm H}}$&nbsp; is a&nbsp; $3 × 7$&nbsp; matrix.
*For the (7, 4, 3)-Hamming code, ${ \boldsymbol{\rm H}}$ is a 3 × 7 matrix.  
+
*For the extended Hamming code &nbsp; ⇒ &nbsp; code $\mathcal{C}_{2}$, on the other hand, $\underline{n = 8}$ (column number) and $\underline{m = 4}$ (row number) holds.
+
*For the extended Hamming code &nbsp; ⇒ &nbsp; $\mathcal{C}_{2}$,&nbsp; on the other hand:&nbsp; $\underline{n = 8}$&nbsp; (column number)&nbsp; and&nbsp; $\underline{m = 4}$&nbsp; (row number).
  
  
  
'''(4)'''&nbsp; From the code table on the information page you can see that only <u>answer 3</u> is correct.  
+
'''(4)'''&nbsp; From the code table in the information section you can see that only&nbsp; <u>answer 3</u>&nbsp; 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$.
+
*The parity bit&nbsp; $p_{4}$&nbsp; is to be determined in such a way that the modulo 2 sum over all bits of the code word results in the value&nbsp; $0$.
  
  
  
'''(5)'''&nbsp; 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.  
+
'''(5)'''&nbsp; It should first be noted that the specification of the parity-check matrix is never unambiguous,&nbsp; 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:
+
*However,&nbsp; considering that only one of the given rows is wrong,&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; 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}.$$
 
:$${ \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 <u>statements 1, 2 and 4</u>. The rows of this parity-check matrix represent the four parity-check equations in this order:
+
*Correct are therefore the&nbsp; <u>statements 1, 2 and 4</u>.&nbsp; 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_1\oplus  x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$
Line 134: Line 137:
  
  
 
+
'''(6)'''&nbsp;  Correct is&nbsp; <u>answer 2</u>:  
'''(6)'''&nbsp;  Correct is the <u>answer 2</u>:  
+
*This result is obtained by replacing the last row with the modulo 2 sum over all four rows,&nbsp; which is allowed.
*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.  
+
*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.
+
 +
*Proposal 3 represents the parity-check equation&nbsp; $x_{3}⊕x_{5} = 0$,&nbsp; which also does not correspond to the facts.
  
  
According to the correct solution suggestion 2, on the other hand, the parity-check equation becomes
+
According to the correct solution suggestion 2,&nbsp; on the other hand,&nbsp; 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$$
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$
replaced by the following new parity-check equation:
+
:is replaced by the following new parity-check equation:
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
The modified parity-check matrix is now:
+
*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}.$$
 
:$${ \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)'''&nbsp;  After this matrix manipulation,&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; is in the form typical for systematic codes:
'''(7)'''&nbsp;  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}.$$
 
:$${ \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:
+
*Thus,&nbsp; 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}.$$
 
:$${ \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 <u>statements 2 and 3</u> are correct:
+
So the&nbsp; <u>statements 2 and 3</u>&nbsp; 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.  
+
* ${ \boldsymbol{\rm G}}_{2}$&nbsp; starts like&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; $($see specification sheet$)$&nbsp; with a diagonal matrix&nbsp; ${ \boldsymbol{\rm I}}_{4}$,&nbsp; but unlike&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; 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.
+
 +
*In the present case&nbsp; $n = 8, k = 4 \ ⇒ \ m = 4$&nbsp; both&nbsp; ${ \boldsymbol{\rm G}}_{2}$&nbsp; and&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; are&nbsp; $4×8$&nbsp; matrices respectively.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Latest revision as of 17:01, 23 January 2023

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



Hints:

  • 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

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