Aufgaben:Exercise 1.09: Extended Hamming Code - Revision history

Hwang at 16:01, 23 January 2023

2023-01-23T16:01:27Z

Guenter at 14:13, 8 October 2022

2022-10-08T14:13:48Z

Guenter at 12:56, 11 July 2022

2022-07-11T12:56:19Z

Guenter at 12:34, 11 July 2022

2022-07-11T12:34:00Z

Noah at 15:06, 6 July 2022

2022-07-06T15:06:36Z

Show changes

Noah at 13:19, 6 July 2022

2022-07-06T13:19:01Z

Guenter at 14:45, 14 June 2022

2022-06-14T14:45:52Z

Guenter at 09:49, 11 May 2022

2022-05-11T09:49:29Z

Guenter: Guenter moved page Aufgaben:Aufgabe 1.09: Erweiterter Hamming–Code to Aufgaben:Exercise 1.09: Extended Hamming Code

2022-05-11T09:41:26Z

Guenter moved page Aufgabe 1.09: Erweiterter Hamming–Code to Exercise 1.09: Extended Hamming Code

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:51:03Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 105: / Line 105: @@
 '''(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 on the information page,&nbsp; it can be seen that for the extended Hamming code&nbsp; $d_{\rm min} \underline{= 4}$&nbsp; holds.
+*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.
@@ Line 119: / Line 119: @@
-'''(4)'''&nbsp; From the code table on the information page you can see that only&nbsp; <u>answer 3</u>&nbsp; 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&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$.

@@ Line 3: / Line 3: @@
 }}
-[[File:EN_KC_A_1_9.png|right|frame|$\text{HC (7, 4)}$&nbsp; (yellow background)  and&nbsp; $\text{(8, 4)}$&nbsp; extension&nbsp; (green background).]]
+[[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,&nbsp; whose code tables are given on the right.

@@ Line 96: / Line 96: @@
 ===Solution===
 {{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}_{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 on the information page, it can be seen that for the extended Hamming code $d_{\rm min} \underline{= 4}$ holds.
+*From the table on the information page,&nbsp; it can be seen that for the extended Hamming code&nbsp; $d_{\rm min} \underline{= 4}$&nbsp; holds.
 '''(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.
 *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 <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},$$
@@ Line 133: / Line 137: @@
+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$$
-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}.$$
-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}.$$
+'''(7)'''&nbsp;  After this matrix manipulation,&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; 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:
+*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}.$$
-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.
 {{ML-Fuß}}

@@ 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.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).
 *Then follow&nbsp; $m = n- k$&nbsp; parity bit (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 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&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.
+*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.
@@ Line 44: / Line 43: @@
 <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="{}"}
 $\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="{}"}
 $\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}$?
 |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="()"}
@@ Line 68: / Line 67: @@
 + $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="[]"}
@@ Line 82: / Line 81: @@
 - $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="[]"}
-- ${ \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}$ .

← Older revision		Revision as of 13:19, 6 July 2022
Line 1:		Line 1:
−	{{quiz-Header\|Buchseite=~~Kanalcodierung~~/~~Allgemeine Beschreibung linearer Blockcodes~~	+	{{quiz-Header\|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes

	}}		}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2396__KC_A_1_9.png|right|frame|$\text{(7, 4)}$&ndash;Hamming–Code (gelb hinterlegt) <br>und&nbsp; $\text{(8, 4)}$&ndash;Erweiterung  (grün)]]
+[[File:EN_KC_A_1_9.png|right|frame|$\text{(7, 4)}$&ndash;Hamming–Code (gelb hinterlegt) <br>und&nbsp; $\text{(8, 4)}$&ndash;Erweiterung  (grün)]]
 Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind.

← Older revision		Revision as of 09:49, 11 May 2022
Line 164:		Line 164:


−	[[Category:Channel Coding: Exercises\|^1.4 ~~Beschreibung linearer Blockcodes~~	+	[[Category:Channel Coding: Exercises\|^1.4 Linear Block Code Description

	^]]		^]]

← Older revision		Revision as of 12:51, 23 March 2021
Line 164:		Line 164:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^1.4 Beschreibung linearer Blockcodes	+	[[Category:Channel Coding: Exercises\|^1.4 Beschreibung linearer Blockcodes

	^]]		^]]