Aufgaben:Exercise 1.6: (7, 4) Hamming Code - Revision history

Hwang at 16:56, 1 November 2022

2022-11-01T16:56:17Z

Guenter at 09:22, 15 June 2022

2022-06-15T09:22:10Z

Guenter at 09:19, 15 June 2022

2022-06-15T09:19:28Z

Guenter at 08:06, 15 June 2022

2022-06-15T08:06:15Z

Guenter at 08:03, 15 June 2022

2022-06-15T08:03:04Z

Noah at 03:46, 11 June 2022

2022-06-11T03:46:47Z

Noah at 03:45, 11 June 2022

2022-06-11T03:45:12Z

Noah at 03:24, 11 June 2022

2022-06-11T03:24:44Z

Noah at 03:24, 11 June 2022

2022-06-11T03:24:29Z

Show changes

Guenter at 09:28, 11 May 2022

2022-05-11T09:28:18Z

@@ Line 5: / Line 5: @@
 [[File:P_ID2388__KC_A_1_6_neu.png|right|frame|Code table of the&nbsp; $\text{HC (7, 4)}$]]
-In 1962,&nbsp; [https://en.wikipedia.org/wiki/Richard_Hamming Richard Wesley Hamming]&nbsp; specified a class of binary block codes that differ in the number&nbsp; $m$&nbsp; of check bits supplied. The codeword length is always&nbsp; $n = 2^m - 1$. The information word consists of&nbsp; $k = n - m$&nbsp; bits:
+In 1962,&nbsp; [https://en.wikipedia.org/wiki/Richard_Hamming Richard Wesley Hamming]&nbsp; specified a class of binary block codes that differ in the number&nbsp; $m$&nbsp; of check bits supplied. The code word length is always&nbsp; $n = 2^m - 1$. The information word consists of&nbsp; $k = n - m$&nbsp; bits:
 *$m = 2$: &nbsp; $\text{(3, 1)}$ Hamming code &nbsp; ⇒ &nbsp; identical to&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|$\text{RC (3, 1)}$]],

@@ Line 159: / Line 159: @@
 Where:
-*$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 = 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$:&nbsp;   $\rm (7, 4)$&nbsp; Hamming code,
 *$m = 4$:&nbsp;   $\rm (15, 11)$&nbsp; Hamming code,

@@ Line 94: / Line 94: @@
 ===Solution===
 {{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}.$$
-*This corresponds exactly to the definition of a [[Channel_Coding/General_Description_of_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}.$$
-'''(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:
 :$$ 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}.$$
@@ 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}.$$
 Where:
-*$m = 2$:   (3, 1) Hamming code, ⇒ identical to [[Channel_Coding/Examples_of_Binary_Block_Codes#RepetitionCodes|'''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 = 3$:&nbsp;   $\rm (7, 4)$&nbsp; Hamming code,
-*$m = 4$:   (15, 11) Hamming code,
+*$m = 4$:&nbsp;   $\rm (15, 11)$&nbsp; Hamming code,
-*$m = 5$:   (31, 26) Hamming code,
+*$m = 5$:&nbsp;   $\rm (31, 26)$&nbsp; Hamming code,
-*$m = 6$:   (63, 57) 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}.$$
-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ß}}

@@ Line 38: / Line 38: @@
 *Reference is made to the section&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|"Hamming Codes"]].
-*For this Hamming code,&nbsp; different test equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]].&nbsp; Therefore,&nbsp; the code tables also differ.
+*For this Hamming code,&nbsp; different parity-check equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]].&nbsp; Therefore,&nbsp; the code tables also differ.
-*In the&nbsp; [[Aufgaben:Exercise_1.07:_Check_and_Generator_Matrix_of_the_HC_(7,_4,_3)|Exercise 1.7]],&nbsp; where the same code is used,&nbsp; the chart of the check equations is given.
+*In the&nbsp; [[Aufgaben:Exercise_1.07:_Check_and_Generator_Matrix_of_the_HC_(7,_4,_3)|Exercise 1.7]],&nbsp; where the same code is used,&nbsp; the chart of the parity-check equations is given.

@@ 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&nbsp; $ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}|$,
-*to the code rate&nbsp; $R$, and
+*to the code rate&nbsp; $R$,&nbsp; and
 *to the minimum distance&nbsp; $d_{\rm min}$.
-Furthermore, we want to clarify whether the&nbsp; $\underline{u}_{i} ⇒ \underline{x}_{i}$&nbsp; given for this task by its code table&nbsp; $\text{(7, 4)}$ Hamming code is systematic, and whether it is a so called "perfect code". The running index can take the values&nbsp; $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$&nbsp;.
+Furthermore,&nbsp; we want to clarify whether the&nbsp; $\text{(7, 4)}$&nbsp; Hamming code   given for this task by its code table&nbsp; $\underline{u}_{i} ⇒ \underline{x}_{i}$&nbsp; is systematic,&nbsp; and whether it is a so called&nbsp; "perfect code".&nbsp; The control index can take the values&nbsp; $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$&nbsp;.
-One speaks of a&nbsp; ''perfect code'' if the following condition is satisfied:
+One speaks of a&nbsp; "perfect code"&nbsp; 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&nbsp; $t$&nbsp; denotes the number of correctable errors. For odd minimum distance&nbsp; $d_{\rm min}$&nbsp; holds:
+Here&nbsp; $t$&nbsp; denotes the number of correctable errors.&nbsp; For odd minimum distance&nbsp; $d_{\rm min}$&nbsp; holds:
 :$$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$
@@ Line 33: / Line 33: @@
+*Reference is made to the section&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|"Hamming Codes"]].
-Hints:
-*This exercise belongs to the chapter&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes|Examples of Binary Block Codes]].
+*For this Hamming code,&nbsp; different test equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]].&nbsp; Therefore,&nbsp; the code tables also differ.
-*For this Hamming code, different test equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]]. Therefore, the code tables also differ.
+*In the&nbsp; [[Aufgaben:Exercise_1.07:_Check_and_Generator_Matrix_of_the_HC_(7,_4,_3)|Exercise 1.7]],&nbsp; where the same code is used,&nbsp; the chart of the check equations is given.
@@ Line 48: / Line 48: @@
 <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="{}"}
-$ \hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 }
+$ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 }
 $ k \hspace{0.46cm} = \ $ { 4 }
 $ n \hspace{0.44cm} = \ $ { 7 }
@@ Line 56: / Line 56: @@
-{is this a systematic code?
+{Is this a systematic code?
 |type="()"}
 + Yes,
@@ Line 70: / Line 70: @@
 $t\hspace{0.28cm} = \ $ { 1 }
-{Is the hamming code considered here perfect?
+{Is the Hamming code considered here&nbsp; "perfect"?
 |type="()"}
 + Yes,
 - No.
-{Which statements are true regarding a perfect code?
+{Which statements are true regarding a&nbsp; "perfect code"?
 |type="[]"}
 - 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 distance is odd.
++ For perfect codes,&nbsp; the minimum Hamming distance is odd.
 {Which of the codes listed below are perfect?

← Older revision		Revision as of 03:46, 11 June 2022
Line 19:		Line 19:


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

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

@@ Line 39: / Line 39: @@
 *Reference is made to the chapter&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|Hamming Codes]].
-*For this Hamming code, different test equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|Theory part]]. Therefore, the code tables also differ.
+*For this Hamming code, different test equations were used than in the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|theory section]]. Therefore, the code tables also differ.
 *In the&nbsp; [[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.

← Older revision		Revision as of 09:28, 11 May 2022
Line 174:		Line 174:


−	[[Category:Channel Coding: Exercises\|^1.3 ~~Beispiele binärer Blockcodes~~	+	[[Category:Channel Coding: Exercises\|^1.3 Examples of Binary Block Codes^]]
−	^]]