Difference between revisions of "Aufgaben:Exercise 1.6: (7, 4) Hamming Code"

From LNTwww
 
(7 intermediate revisions by 2 users not shown)
Line 5: Line 5:
 
[[File:P_ID2388__KC_A_1_6_neu.png|right|frame|Code table of the  $\text{HC (7, 4)}$]]
 
[[File:P_ID2388__KC_A_1_6_neu.png|right|frame|Code table of the  $\text{HC (7, 4)}$]]
  
In 1962,  [https://en.wikipedia.org/wiki/Richard_Hamming Richard Wesley Hamming]  specified a class of binary block codes that differ in the number  $m$  of check bits supplied. The codeword length is always  $n = 2^m - 1$. The information word consists of  $k = n - m$  bits:
+
In 1962,  [https://en.wikipedia.org/wiki/Richard_Hamming Richard Wesley Hamming]  specified a class of binary block codes that differ in the number  $m$  of check bits supplied. The code word length is always  $n = 2^m - 1$. The information word consists of  $k = n - m$  bits:
  
 
*$m = 2$:   $\text{(3, 1)}$ Hamming code   ⇒   identical to  [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|$\text{RC (3, 1)}$]],
 
*$m = 2$:   $\text{(3, 1)}$ Hamming code   ⇒   identical to  [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|$\text{RC (3, 1)}$]],
Line 13: Line 13:
  
  
In the course of this task there are questions
+
In the course of this exercise there are questions
 
*to the code size  $ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}|$,
 
*to the code size  $ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}|$,
*to the code rate  $R$, and
+
*to the code rate  $R$,  and
 
*to the minimum distance  $d_{\rm min}$.
 
*to the minimum distance  $d_{\rm min}$.
  
  
Furthermore, we want to clarify whether the  $\underline{u}_{i} ⇒ \underline{x}_{i}$  given for this task by its code table  $\text{(7, 4)}$-Hamming code is systematic, and whether it is a so-called "perfect code". The running index can take the values  $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$ .
+
Furthermore,  we want to clarify whether the  $\text{(7, 4)}$  Hamming code  given for this task by its code table  $\underline{u}_{i} ⇒ \underline{x}_{i}$  is systematic,  and whether it is a so called  "perfect code".  The control index can take the values  $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$ .
  
One speaks of a  ''perfect code'' if the following condition is satisfied:
+
One speaks of a  "perfect code"  if the following condition is satisfied:
 
:$$2^k = \frac{2^n} {\sum_{f=0}^t {n \choose f}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
 
:$$2^k = \frac{2^n} {\sum_{f=0}^t {n \choose f}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
  
Here  $t$  denotes the number of correctable errors. For odd minimum distance  $d_{\rm min}$  holds:
+
Here  $t$  denotes the number of correctable errors.  For odd minimum distance  $d_{\rm min}$  holds:
 
:$$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$
 
:$$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$
  
Line 33: Line 33:
  
  
 +
Hints:
 +
*This exercise belongs to the chapter  [[Channel_Coding/Examples_of_Binary_Block_Codes|"Examples of Binary Block Codes"]].
  
 
+
*Reference is made to the section  [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|"Hamming Codes"]].
Hints:
+
*This exercise belongs to the chapter  [[Channel_Coding/Examples_of_Binary_Block_Codes|Examples of Binary Block Codes]].
+
*For this Hamming code,  different parity-check equations were used than in the  [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]].  Therefore,  the code tables also differ.
*Reference is made to the chapter  [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|Hamming Codes]].
 
 
   
 
   
*For this Hamming code, different test equations were used than in the  [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|Theory part]]. Therefore, the code tables also differ.
+
*In the  [[Aufgaben:Exercise_1.07:_Check_and_Generator_Matrix_of_the_HC_(7,_4,_3)|Exercise 1.7]],  where the same code is used,  the chart of the parity-check equations is given.
*In the  [[Aufgaben:Exercise_1.07:_Check_and_Generator_Matrix_of_the_HC_(7,_4,_3)|Exercise 1.7]], where the same code is used, the chart of the check equations is given.
 
  
  
Line 48: Line 48:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Specify the characteristics of the given code&nbsp; $\mathcal{C}$&nbsp;:
+
{Specify the characteristics of the given code&nbsp; $\mathcal{C}$:
 
|type="{}"}
 
|type="{}"}
$ \hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 }
+
$ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 }
 
$ k \hspace{0.46cm} = \ $ { 4 }
 
$ k \hspace{0.46cm} = \ $ { 4 }
 
$ n \hspace{0.44cm} = \ $ { 7 }
 
$ n \hspace{0.44cm} = \ $ { 7 }
Line 56: Line 56:
  
  
{is this a systematic code?
+
{Is this a systematic code?
 
|type="()"}
 
|type="()"}
 
+ Yes,
 
+ Yes,
Line 70: Line 70:
 
$t\hspace{0.28cm} = \ $ { 1 }
 
$t\hspace{0.28cm} = \ $ { 1 }
  
{Is the hamming code considered here perfect?
+
{Is the Hamming code considered here&nbsp; "perfect"?
 
|type="()"}
 
|type="()"}
 
+ Yes,
 
+ Yes,
 
- No.
 
- No.
  
{Which statements are true regarding a perfect code?
+
{Which statements are true regarding a&nbsp; "perfect code"?
 
|type="[]"}
 
|type="[]"}
 
- A perfect code always results in zero block error probability.
 
- A perfect code always results in zero block error probability.
+ All receive words&nbsp; $\underline{y}$&nbsp; are assignable to a valid codeword.
+
+ All receive words&nbsp; $\underline{y}$&nbsp; are assignable to a valid code word.
+ For perfect codes, the minimum Hamming&ndash;distance is odd.
+
+ For perfect codes,&nbsp; the minimum Hamming distance is odd.
  
 
{Which of the codes listed below are perfect?
 
{Which of the codes listed below are perfect?
Line 94: Line 94:
 
===Solution===
 
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; The code table has 16 entries: $\underline{|C| = 16}$.  
+
'''(1)'''&nbsp; The code table has sixteen entries: $\underline{|C| = 16}$.  
*From the equation $|C| = 2^k$ it follows that $\underline{k = 4}$.  
+
*From the equation&nbsp; $|C| = 2^k$&nbsp; it follows that&nbsp; $\underline{k = 4}$.  
*The length of each codeword is $\underline{n = 7}$.  
+
*The length of each code word is&nbsp; $\underline{n = 7}$.  
*Thus, the code rate is $\underline{R = 4/7} = 0.571$.
+
*Thus,&nbsp; the code rate is $\underline{R = 4/7} = 0.571$.
  
  
  
'''(2)'''&nbsp; Correct <u>YES</u>:
+
'''(2)'''&nbsp; Correct&nbsp; <u>YES</u>:
*Each codeword $\underline{x}$ first contains the $k = 4$ bits of the information word $\underline{u}$. This is followed by $m = 3$ check bits:
+
*Each code word&nbsp; $\underline{x}$&nbsp; first contains the&nbsp; $k = 4$&nbsp; bits of the information word&nbsp; $\underline{u}$.&nbsp; This is followed by&nbsp; $m = 3$&nbsp; check bits:
 
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_5,x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3) \hspace{0.05cm}.$$
 
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_5,x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3) \hspace{0.05cm}.$$
*This corresponds exactly to the definition of a [[Channel_Coding/General_Description_linear_Block_codes|systematic code]] .
+
*This corresponds exactly to the definition of a&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"systematic code"]] .
  
  
  
'''(3)'''&nbsp; For any Hamming code, the minimum distance $d_{\rm min} \underline{= 3}$.  
+
'''(3)'''&nbsp; For any Hamming code,&nbsp; the minimum distance $d_{\rm min} \underline{= 3}$.  
*From the table, you can see that the minimum [[Channel_Coding/Objective_of_Channel_Coding#Some_Important_Definitions_of_Block_Coding|Hamming_Weight]] (the number of ones in a codeword) is equal to 3.  
+
*From the table,&nbsp; you can see that the minimum&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Some_Important_Definitions_of_Block_Coding|Hamming weight]]&nbsp; (the number of ones in a code word)&nbsp; is equal to 3.  
*A linear code, in fact, also includes the zero word, so that holds:
+
*A linear code,&nbsp; in fact,&nbsp; also includes the zero word,&nbsp; so that holds:
 
:$$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}') = \min_{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} }\hspace{0.1cm}w_{\rm H}(\underline{x}) = 3 \hspace{0.05cm}.$$
 
:$$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}') = \min_{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} }\hspace{0.1cm}w_{\rm H}(\underline{x}) = 3 \hspace{0.05cm}.$$
  
  
'''(4)'''&nbsp; The specification $d_{\rm min} = 3$ means that $\underline{e = 2}$ errors can be detected and $\underline{t = 1}$ errors can be corrected.
+
'''(4)'''&nbsp; The specification&nbsp; $d_{\rm min} = 3$&nbsp; means that&nbsp; $\underline{e = 2}$&nbsp; errors can be detected and&nbsp; $\underline{t = 1}$&nbsp; errors can be corrected.
  
  
  
'''(5)'''&nbsp; Correct is <u>YES</u>:
+
'''(5)'''&nbsp; Correct is&nbsp; <u>YES</u>:
 
*The condition for a perfect code is according to the specification:
 
*The condition for a perfect code is according to the specification:
  
 
:$$ 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
 
:$$ 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
  
*In the (7, 4)-Hamming code considered here, $n = 7$, $m = 3$, and $t = 1$, giving a value of 8 on both sides of the equation:
+
*In the&nbsp; $\text{(7, 4) Hamming code}$&nbsp; considered here,&nbsp; $n = 7$,&nbsp; $m = 3$,&nbsp; and&nbsp; $t = 1$,&nbsp; giving a value of&nbsp; $8$&nbsp; on both sides of the equation:
  
 
:$$ 2^3 = 8\hspace{0.05cm}, \hspace{0.35cm} {\sum_{f=0}^1 {7 \choose f}} = {7 \choose 0} + {7 \choose 1} = 1 + 7 = 8 \hspace{0.05cm}.$$
 
:$$ 2^3 = 8\hspace{0.05cm}, \hspace{0.35cm} {\sum_{f=0}^1 {7 \choose f}} = {7 \choose 0} + {7 \choose 1} = 1 + 7 = 8 \hspace{0.05cm}.$$
Line 129: Line 129:
  
  
'''(6)'''&nbsp; Correct <u>statements 2 and 3</u>:
+
'''(6)'''&nbsp; Correct&nbsp; <u>statements 2 and 3</u>:
*If there were a channel code with finite codeword length $n$ that made the block error probability zero for all channels, it would not only be perfect, but a miracle.  
+
*If there were a channel code with finite code word length&nbsp; $n$&nbsp; that made the block error probability zero for all channels,&nbsp; it would not only be perfect,&nbsp; but a&nbsp; "miracle".  
*But due to the channel coding theorem, ${\rm Pr(block error)} = 0$ is not even possible with finite $n$.
+
*But due to the channel coding theorem,&nbsp; ${\rm Pr(block error)} = 0$&nbsp; is not even possible with finite&nbsp; $n$.
  
  
[[File:P_ID2389__KC_A_1_6_ML.png|right|frame|illustration of a perfect code]]
+
[[File:P_ID2389__KC_A_1_6_ML.png|right|frame|Illustration of a&nbsp; "perfect code"]]
  
Let's illustrate statement 2 with a graph. Here, the high-dimensional space is shown in a highly simplified way (in 2D). We assume the numerical values $k = 4$, $n = 7$, $m = 3$ and $t = 1$ of the (7, 4, 3)-Hamming code:
+
Let's illustrate statement 2 with a graph.&nbsp; Here,&nbsp; the high-dimensional space is shown in a highly simplified way&nbsp; ("2D").&nbsp; We assume the numerical values&nbsp; $k = 4$,&nbsp; $n = 7$,&nbsp; $m = 3$&nbsp; and&nbsp; $t = 1$&nbsp; of the&nbsp; $\text{(7, 4, 3)}$&nbsp; Hamming code:
  
*For the receive word, $2^7 = 128$ points are possible in 7-dimensional space. The red dots mark the $2^4 = 16$ valid codewords.
+
*For the receive word,&nbsp; $2^7 = 128$&nbsp; points are possible in seven-dimensional space.&nbsp; The red dots mark the&nbsp; $2^4 = 16$&nbsp; valid code words.
  
*The circles include 8 points each, namely a valid codeword and $n = 7$ receive words after only one error, which are assigned to exactly this codeword during decoding.
+
*The circles include&nbsp; $8$&nbsp; points each,&nbsp; namely a valid code word and&nbsp; $n = 7$&nbsp; receive words after only one error,&nbsp; which are assigned to exactly this code word during decoding.
  
*Total there are $2^4 = 16$ such circles. Therefore, because of $128 = 16 - 8$, not a single receive word $\underline{y}$ lies outside such an assignment circle.
+
*Total there are&nbsp; $2^4 = 16$&nbsp; such circles.&nbsp; Therefore,&nbsp; because of $128 = 16 \cdot 8$,&nbsp; not a single receive word&nbsp; $\underline{y}$&nbsp; lies outside such an assignment circle.
  
  
Also the <u>last statement</u> is true, which shall be shown exemplarily for $d_{\rm min} = 4$:  
+
Also the&nbsp; <u>last statement</u>&nbsp; is true,&nbsp; which shall be shown exemplarily for&nbsp; $d_{\rm min} = 4$:  
*Hereby also only $t = 1$ error can be corrected.  
+
*Hereby also only&nbsp; $t = 1$&nbsp; error can be corrected.  
*If a receive word $\underline{y}$ differs from permissible code words in two bits, this point is not to be assigned to any circle. Then there are also points outside the circles and the condition of a perfect code is no longer fulfilled.
+
*If a receive word&nbsp; $\underline{y}$&nbsp; differs from permissible code words in two bits,&nbsp; this point is not to be assigned to any circle.&nbsp; Then there are also points outside the circles and the condition of a&nbsp; "perfect code"&nbsp; is no longer fulfilled.
  
  
  
'''(7)'''&nbsp; Correct are <u>statements 1, 2, 3 and 5</u>:  
+
'''(7)'''&nbsp; Correct are&nbsp; <u>statements 1, 2, 3&nbsp; and&nbsp; 5</u>:  
*All Hamming codes have the minimum Hamming distance $d_{\rm min} = 3$ &nbsp; &rArr; &nbsp; $t = 1$.  
+
*All Hamming codes have the minimum Hamming distance&nbsp; $d_{\rm min} = 3$ &nbsp; &rArr; &nbsp; $t = 1$.  
*At the same time, any $(n, k)$ Hamming code can also be written as a $(2^m - 1, 2^m - 1 - m)$ code, where $m = n - k$ indicates the number of check bits.  
+
*At the same time,&nbsp; any&nbsp; $(n, k)$&nbsp; Hamming code can also be written as a&nbsp; $(2^m - 1, 2^m - 1 - m)$&nbsp; code,&nbsp; where $m = n - k$&nbsp; indicates the number of parity bits.  
*Thus, the equation of a perfect code is always satisfied:
+
*Thus,&nbsp; the equation of a&nbsp; "perfect code"&nbsp; is always satisfied:
  
 
:$${\sum_{f=0}^1 {n \choose f}} = 1 + n = 2^m \hspace{0.05cm}.$$
 
:$${\sum_{f=0}^1 {n \choose f}} = 1 + n = 2^m \hspace{0.05cm}.$$
  
 
Where:
 
Where:
*$m = 2$:   (3, 1) Hamming code, ⇒ identical to [[Channel_Coding/Examples_binary_BlockCodes#RepeatCodes|'''RC (3, 1)''',]]
+
*$m = 2$:&nbsp;  $\rm  (3, 1)$&nbsp; Hamming code, ⇒ identical to&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#RepetitionCodes|$\text{RC (3, 1)}$]],
*$m = 3$:  (7, 4) Hamming code,
+
 
*$m = 4$:  (15, 11) Hamming code,
+
*$m = 3$:&nbsp;   $\rm (7, 4)$&nbsp; Hamming code,
*$m = 5$:  (31, 26) Hamming code,
+
*$m = 4$:&nbsp;   $\rm (15, 11)$&nbsp; Hamming code,
*$m = 6$:  (63, 57) Hamming code,   
+
*$m = 5$:&nbsp;   $\rm (31, 26)$&nbsp; Hamming code,
 +
*$m = 6$:&nbsp;   $\rm (63, 57)$&nbsp; Hamming code,   
 
          
 
          
  
The repetition code with $n = 5$ also satisfies the condition. With $d_{\rm min} = 5$, $t = 2$ and $m = 4$ we obtain:
+
The repetition code with&nbsp; $n = 5$&nbsp; also satisfies the condition.&nbsp; With&nbsp; $d_{\rm min} = 5$,&nbsp; $t = 2$&nbsp; and&nbsp; $m = 4$&nbsp; we obtain:
 
:$${\sum_{f=0}^2 {5 \choose f}} = 1 + 5 + 10 = 16 = 2^m \hspace{0.05cm}.$$
 
:$${\sum_{f=0}^2 {5 \choose f}} = 1 + 5 + 10 = 16 = 2^m \hspace{0.05cm}.$$
  
The other repetition codes (RC) with odd $n$ are also perfect, but not with even $n$: RC (4, 1), RC (6, 1), etc. This has already been justified in the sample solution to the subtask '''(6)'''.
+
The other repetition codes&nbsp; $\rm (RC)$&nbsp; with odd&nbsp; $n$&nbsp; are also perfect,&nbsp; but not with even&nbsp; $n$:&nbsp; $\text{RC (4, 1)}$,&nbsp; $\text{RC (6, 1)}$,&nbsp; etc. This has already been justified in the solution to the subtask&nbsp; '''(6)'''.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Latest revision as of 18:56, 1 November 2022

Code table of the  $\text{HC (7, 4)}$

In 1962,  Richard Wesley Hamming  specified a class of binary block codes that differ in the number  $m$  of check bits supplied. The code word length is always  $n = 2^m - 1$. The information word consists of  $k = n - m$  bits:

  • $m = 2$:   $\text{(3, 1)}$ Hamming code   ⇒   identical to  $\text{RC (3, 1)}$,
  • $m = 3$:   $\text{(7, 4)}$ Hamming code,
  • $m = 4$:   $\text{(15, 11)}$ Hamming code,
  • $m = 5$:   $\text{(31, 26)}$ Hamming code, etc.


In the course of this exercise there are questions

  • to the code size  $ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}|$,
  • to the code rate  $R$,  and
  • to the minimum distance  $d_{\rm min}$.


Furthermore,  we want to clarify whether the  $\text{(7, 4)}$  Hamming code given for this task by its code table  $\underline{u}_{i} ⇒ \underline{x}_{i}$  is systematic,  and whether it is a so called  "perfect code".  The control index can take the values  $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$ .

One speaks of a  "perfect code"  if the following condition is satisfied:

$$2^k = \frac{2^n} {\sum_{f=0}^t {n \choose f}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$

Here  $t$  denotes the number of correctable errors.  For odd minimum distance  $d_{\rm min}$  holds:

$$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$

The interpretation to this condition can be found in the sample solution.



Hints:

  • For this Hamming code,  different parity-check equations were used than in the  theory section.  Therefore,  the code tables also differ.
  • In the  Exercise 1.7,  where the same code is used,  the chart of the parity-check equations is given.


Questions

1

Specify the characteristics of the given code  $\mathcal{C}$:

$ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $

$ k \hspace{0.46cm} = \ $

$ n \hspace{0.44cm} = \ $

$ R \hspace{0.40cm} = \ $

2

Is this a systematic code?

Yes,
No.

3

What is the minimum distance between any two code words?

$ \ d_{\rm min} \ = \ $

4

How many transmission errors can be detected  $(e)$  or corrected  $(t)$  respectively?

$e\hspace{0.22cm} = \ $

$t\hspace{0.28cm} = \ $

5

Is the Hamming code considered here  "perfect"?

Yes,
No.

6

Which statements are true regarding a  "perfect code"?

A perfect code always results in zero block error probability.
All receive words  $\underline{y}$  are assignable to a valid code word.
For perfect codes,  the minimum Hamming distance is odd.

7

Which of the codes listed below are perfect?

The  $\text{(15, 11)}$ Hamming code,
the  $\text{(63, 57)}$ Hamming code,
the  $\text{(3, 1)}$ repetition code,
the  $\text{(4, 1)}$ repetition Code,
the  $\text{(5, 1)}$ repetition code.


Solution

(1)  The code table has sixteen entries: $\underline{|C| = 16}$.

  • From the equation  $|C| = 2^k$  it follows that  $\underline{k = 4}$.
  • The length of each code word is  $\underline{n = 7}$.
  • Thus,  the code rate is $\underline{R = 4/7} = 0.571$.


(2)  Correct  YES:

  • Each code word  $\underline{x}$  first contains the  $k = 4$  bits of the information word  $\underline{u}$.  This is followed by  $m = 3$  check bits:
$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_5,x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3) \hspace{0.05cm}.$$


(3)  For any Hamming code,  the minimum distance $d_{\rm min} \underline{= 3}$.

  • From the table,  you can see that the minimum  Hamming weight  (the number of ones in a code word)  is equal to 3.
  • A linear code,  in fact,  also includes the zero word,  so that holds:
$$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}') = \min_{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} }\hspace{0.1cm}w_{\rm H}(\underline{x}) = 3 \hspace{0.05cm}.$$


(4)  The specification  $d_{\rm min} = 3$  means that  $\underline{e = 2}$  errors can be detected and  $\underline{t = 1}$  errors can be corrected.


(5)  Correct is  YES:

  • The condition for a perfect code is according to the specification:
$$ 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
  • In the  $\text{(7, 4) Hamming code}$  considered here,  $n = 7$,  $m = 3$,  and  $t = 1$,  giving a value of  $8$  on both sides of the equation:
$$ 2^3 = 8\hspace{0.05cm}, \hspace{0.35cm} {\sum_{f=0}^1 {7 \choose f}} = {7 \choose 0} + {7 \choose 1} = 1 + 7 = 8 \hspace{0.05cm}.$$


(6)  Correct  statements 2 and 3:

  • If there were a channel code with finite code word length  $n$  that made the block error probability zero for all channels,  it would not only be perfect,  but a  "miracle".
  • But due to the channel coding theorem,  ${\rm Pr(block error)} = 0$  is not even possible with finite  $n$.


Illustration of a  "perfect code"

Let's illustrate statement 2 with a graph.  Here,  the high-dimensional space is shown in a highly simplified way  ("2D").  We assume the numerical values  $k = 4$,  $n = 7$,  $m = 3$  and  $t = 1$  of the  $\text{(7, 4, 3)}$  Hamming code:

  • For the receive word,  $2^7 = 128$  points are possible in seven-dimensional space.  The red dots mark the  $2^4 = 16$  valid code words.
  • The circles include  $8$  points each,  namely a valid code word and  $n = 7$  receive words after only one error,  which are assigned to exactly this code word during decoding.
  • Total there are  $2^4 = 16$  such circles.  Therefore,  because of $128 = 16 \cdot 8$,  not a single receive word  $\underline{y}$  lies outside such an assignment circle.


Also the  last statement  is true,  which shall be shown exemplarily for  $d_{\rm min} = 4$:

  • Hereby also only  $t = 1$  error can be corrected.
  • If a receive word  $\underline{y}$  differs from permissible code words in two bits,  this point is not to be assigned to any circle.  Then there are also points outside the circles and the condition of a  "perfect code"  is no longer fulfilled.


(7)  Correct are  statements 1, 2, 3  and  5:

  • All Hamming codes have the minimum Hamming distance  $d_{\rm min} = 3$   ⇒   $t = 1$.
  • At the same time,  any  $(n, k)$  Hamming code can also be written as a  $(2^m - 1, 2^m - 1 - m)$  code,  where $m = n - k$  indicates the number of parity bits.
  • Thus,  the equation of a  "perfect code"  is always satisfied:
$${\sum_{f=0}^1 {n \choose f}} = 1 + n = 2^m \hspace{0.05cm}.$$

Where:

  • $m = 3$:  $\rm (7, 4)$  Hamming code,
  • $m = 4$:  $\rm (15, 11)$  Hamming code,
  • $m = 5$:  $\rm (31, 26)$  Hamming code,
  • $m = 6$:  $\rm (63, 57)$  Hamming code,


The repetition code with  $n = 5$  also satisfies the condition.  With  $d_{\rm min} = 5$,  $t = 2$  and  $m = 4$  we obtain:

$${\sum_{f=0}^2 {5 \choose f}} = 1 + 5 + 10 = 16 = 2^m \hspace{0.05cm}.$$

The other repetition codes  $\rm (RC)$  with odd  $n$  are also perfect,  but not with even  $n$:  $\text{RC (4, 1)}$,  $\text{RC (6, 1)}$,  etc. This has already been justified in the solution to the subtask  (6).