Aufgaben:Exercise 1.11: Syndrome Decoding - Revision history

Guenter at 12:03, 21 April 2023

2023-04-21T12:03:26Z

Guenter at 16:07, 20 April 2023

2023-04-20T16:07:49Z

Guenter at 16:09, 13 March 2023

2023-03-13T16:09:33Z

Hwang at 15:32, 23 January 2023

2023-01-23T15:32:02Z

Hwang at 16:58, 1 November 2022

2022-11-01T16:58:04Z

Guenter at 12:24, 28 September 2022

2022-09-28T12:24:40Z

Guenter at 12:23, 28 September 2022

2022-09-28T12:23:41Z

Guenter at 14:23, 17 August 2022

2022-08-17T14:23:38Z

Guenter at 12:28, 19 July 2022

2022-07-19T12:28:18Z

Guenter at 11:39, 19 July 2022

2022-07-19T11:39:36Z

← Older revision		Revision as of 12:03, 21 April 2023
Line 121:		Line 121:


−	[[File:EN_KC_A_1_11d_v2.png\|right\|frame\|All coset leaders of the  $HC (7, \, 4, \, 3)$ ]]	+	[[File:EN_KC_A_1_11d_v2.png\|right\|frame\|All coset leaders of the  $\rm HC (7, \, 4, \, 3)$ ]]
	'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:		'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:

← Older revision		Revision as of 16:07, 20 April 2023
Line 121:		Line 121:


−	[[File:~~P_ID2398__KC_A_1_11d~~.png\|right\|frame\|All coset leaders of the  $HC (7, \, 4, \, 3)$ ~~'''Korrektur'''~~ ]]	+	[[File:EN_KC_A_1_11d_v2.png\|right\|frame\|All coset leaders of the  $HC (7, \, 4, \, 3)$ ]]
	'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:		'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:

← Older revision		Revision as of 16:09, 13 March 2023
Line 121:		Line 121:


−	[[File:P_ID2398__KC_A_1_11d.png\|right\|frame\|All coset leaders of the  $(7, \, 4, \, 3)$~~  Hamming code~~ '''Korrektur''' ]]	+	[[File:P_ID2398__KC_A_1_11d.png\|right\|frame\|All coset leaders of the  $HC (7, \, 4, \, 3)$ '''Korrektur''' ]]
	'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:		'''(5)'''  A comparison with the solution to the last subtask shows that  $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$  as a syndrome gives the second row of the transposed matrix:

← Older revision		Revision as of 15:32, 23 January 2023
Line 140:		Line 140:


−	'''(6)'''  For the  $(7, \, 4, \, 3)$  Hamming code under consideration,  the correct information word is decided if at most one bit within the code word is ~~corrupted~~ during transmission.  It follows:	+	'''(6)'''  For the  $(7, \, 4, \, 3)$  Hamming code under consideration,  the correct information word is decided if at most one bit within the code word is falsified during transmission.  It follows:

	:$${ \rm Pr(block\:errors)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} { \rm Pr(\ge 2\hspace{0.15cm}bit\hspace{0.15cm}errors\hspace{0.15cm})} =1 - { \rm Pr(0\hspace{0.15cm}bit\hspace{0.15cm}errors)} - { \rm Pr(1\hspace{0.15cm}bit\hspace{0.15cm}errors)} =1 - 0.9^7 - 7 \cdot 0.1 \cdot 0.9^7 \hspace{0.15cm} \underline{ = 0.15} \hspace{0.05cm}.$$		:$${ \rm Pr(block\:errors)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} { \rm Pr(\ge 2\hspace{0.15cm}bit\hspace{0.15cm}errors\hspace{0.15cm})} =1 - { \rm Pr(0\hspace{0.15cm}bit\hspace{0.15cm}errors)} - { \rm Pr(1\hspace{0.15cm}bit\hspace{0.15cm}errors)} =1 - 0.9^7 - 7 \cdot 0.1 \cdot 0.9^7 \hspace{0.15cm} \underline{ = 0.15} \hspace{0.05cm}.$$

@@ Line 13: / Line 13: @@
 :$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$
-*In&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"BSC channel"]]&nbsp; the received word &nbsp; $\underline{y} = \underline{x} \, ({\rm codeword}) + \underline{e} \, ({\rm error\:vector})$ &nbsp; is also an element of&nbsp; ${\rm GF}(2^n)$,&nbsp; and it holds because of&nbsp;&nbsp; $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
+*In&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"BSC channel"]]&nbsp; the received word &nbsp; $\underline{y} = \underline{x} \, ({\rm code\:word}) + \underline{e} \, ({\rm error\:vector})$ &nbsp; is also an element of&nbsp; ${\rm GF}(2^n)$,&nbsp; and it holds because of&nbsp;&nbsp; $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
   \underline{0}$:
 :$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T} \hspace{0.05cm}.$$

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
-[[File:EN_KC_A_1_11.png|right|frame|Syndrome and coset leaders <br>$($incomplete list$)&nbsp; of &nbsp;$\rm HC \ (7, \, 4, \, 3)$ ]]
+[[File:EN_KC_A_1_11.png|right|frame|Syndrome and coset leaders <br>$($incomplete list$)$&nbsp; of &nbsp;$\rm HC \ (7, \, 4, \, 3)$ ]]
 To decode a &nbsp;$(7, \, 4, \, 3)$&nbsp; Hamming code,&nbsp; which is defined by its parity-check matrix

@@ Line 84: / Line 84: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; There are a total of $2^7 = 128$ different codewords $\underline{x}$ and according to the BSC model also $2^7$ different received words $y$ and as many error vectors $\underline{e}$.
+'''(1)'''&nbsp; There are a total of&nbsp; $2^7 = 128$&nbsp; different code words&nbsp; $\underline{x}$&nbsp; and according to the BSC model also&nbsp; $2^7$&nbsp; different received words&nbsp; $y$&nbsp; and as many error vectors&nbsp; $\underline{e}$.
-*With $m = 3$ parity bits, there are $2^3 = 8$ distinct values for the syndrome,
+*With&nbsp; $m = 3$&nbsp; parity bits,&nbsp; there are&nbsp; $2^3 = 8$&nbsp; distinct values for the syndrome,
 :$$\underline{s} \hspace{0.05cm} \in \hspace{0.05cm} \{ \underline{s}_0, \underline{s}_1,\hspace{0.05cm} \text{...} \hspace{0.05cm} , \underline{s}_7\} = \{ \underline{s}_{\mu} \}\hspace{0.05cm}, \hspace{0.2cm} \mu = 0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , 7 \hspace{0.05cm},$$
-:and just as many cosets.
+:and just as many&nbsp; "cosets".
-*Since in the Hamming code, which is perfect, all error vectors belong to one of the eight cosets ${\it \Psi}_{\mu}$ and, moreover, the number of all vectors in all cosets is the same ("Why should it be different?" Is that enough proof for you?), we get
+*Since in the Hamming code,&nbsp; which is perfect,&nbsp; all error vectors belong to one of the eight cosets&nbsp; ${\it \Psi}_{\mu}$&nbsp; and,&nbsp; moreover,&nbsp; the number of all vectors in all cosets is the same&nbsp; ("Why should it be different?" Is that enough proof for you?),&nbsp; we get:
 :$$ N_0 = \frac{2^n}{2^m} = 2^k \hspace{0.15cm} \underline{= 16} \hspace{0.05cm}.$$
-*The cosets ${\it \Psi}_{0}$ include for example - see sample solution to [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|Exercise 1.11Z]] - the vectors
+*The cosets&nbsp; ${\it \Psi}_{0}$&nbsp; include for example - see sample solution to&nbsp; [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|"Exercise 1.11Z"]] - the vectors
 :$$\underline{e} = (1, 1, 0, 0, 0, 0, 1),$$
-:$$\underline{e} = (1, 1, 0, 0, 0, 0, 1).$$
+:$$\underline{e} = (1, 1, 1, 1, 1, 1, 1).$$
-'''(2)'''&nbsp; According to the comments of the last partial result, the following applies equally $N_{7} \ \underline{= 16}$.
+'''(2)'''&nbsp; According to the comments of the last partial result,&nbsp; the following applies equally:&nbsp; $N_{7} \ \underline{= 16}$.
-'''(3)'''&nbsp; Correct is <u>answer 3</u>:
+'''(3)'''&nbsp; Correct is&nbsp; <u>answer 3</u>:
-*The coset leader $\underline{e}_{\mu}$ is the error vector $\underline{e}$ with the lowest [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|Hamming weight]] $w_{\rm H}(\underline{e})$ that leads to the syndrome $\underline{s}_{\mu}$.
+*The coset leader&nbsp; $\underline{e}_{\mu}$&nbsp; is the error vector&nbsp; $\underline{e}$&nbsp; with the lowest [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"Hamming weight"]]&nbsp; $w_{\rm H}(\underline{e})$&nbsp; that leads to the syndrome&nbsp; $\underline{s}_{\mu}$.
-*The Hamming code considered here (7, 4, 3) is perfect. That is, all eight coset leaders therefore contain.
-:*either no "one" ($\underline{e}_{0}$ &nbsp; ⇒ &nbsp; no correction is required), or
+*The (7, 4, 3) Hamming code considered here is perfect.&nbsp; That is,&nbsp; all eight coset leaders therefore contain.
-:*exactly a single "one" ($\underline{e}_{1}, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \underline{e}_{7}$ &nbsp; ⇒ &nbsp; an information or parity bit must be corrected).
+:*either no&nbsp; "one"&nbsp; $(\underline{e}_{0}$ &nbsp; ⇒ &nbsp; no correction is required$)$,&nbsp; or
-'''(4)'''&nbsp;  It holds $\underline{s} = \underline{e} · \boldsymbol{\rm H}^{\rm T}$:
+'''(4)'''&nbsp;  It holds&nbsp; $\underline{s} = \underline{e} · \boldsymbol{\rm H}^{\rm T}$:
 :$$\underline{s} = \begin{pmatrix} 1 &0 &0 &0 &0 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1\\ 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} = \begin{pmatrix} 1 &0 &1 \end{pmatrix} = \underline{s}_5 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} \hspace{0.15cm} \underline{ \mu= 5} \hspace{0.05cm}.$$
-  [[File:P_ID2398__KC_A_1_11d.png|right|frame|All coset leaders of the $(7, \, 4, \, 3)$ Hamming code. ]]
+  [[File:P_ID2398__KC_A_1_11d.png|right|frame|All coset leaders of the&nbsp; $(7, \, 4, \, 3)$&nbsp; Hamming code '''Korrektur''' ]]
-'''(5)'''&nbsp; A comparison with the solution to the last subtask shows that $(0, 1, 0, 0, 0, 0) - \boldsymbol{\rm H}^{\rm T}$ as a syndrome gives the second row of the transposed matrix:
+'''(5)'''&nbsp; A comparison with the solution to the last subtask shows that&nbsp; $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$&nbsp; as a syndrome gives the second row of the transposed matrix:
 :$$\begin{pmatrix} 0 &1 &0 &0 &0 \hspace{0.2cm}\text{... }\end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 &1 &0 \end{pmatrix} = \underline{s}_6$$
-:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 6} \hspace{0.05cm}, \hspace{0.2cm} \underline{e}_6 = \begin{pmatrix} 0 &1 &0 &0 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
+:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 6} \hspace{0.05cm}, \hspace{0.5cm} \underline{e}_6 = \begin{pmatrix} 0 &1 &0 &0 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
 :$$\begin{pmatrix} 0 &0 &1 &0 &0 \hspace{0.2cm}\text{... }\end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 0 &1 &1 \end{pmatrix} = \underline{s}_3$$
-:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 3} \hspace{0.05cm}, \hspace{0.2cm} \underline{e}_3 = \begin{pmatrix} 0 &0 &1 &0 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
+:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 3} \hspace{0.05cm}, \hspace{0.5cm} \underline{e}_3 = \begin{pmatrix} 0 &0 &1 &0 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
 :$$\begin{pmatrix} 0 &0 &0 &1 &0 \hspace{0.2cm}\text{... } \end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 &1 &1 \end{pmatrix} = \underline{s}_7$$
-:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 7} \hspace{0.05cm}, \hspace{0.2cm} \underline{e}_7 = \begin{pmatrix} 0 &0 &0 &1 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
+:$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 7} \hspace{0.05cm}, \hspace{0.5cm} \underline{e}_7 = \begin{pmatrix} 0 &0 &0 &1 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$
-The adjacent graph summarizes again the results of the subtasks '''(4)''' and '''(5)'''.
+The adjacent graph summarizes again the results of the subtasks&nbsp; '''(4)'''&nbsp; and&nbsp; '''(5)'''.
-'''(6)'''&nbsp;  For the $(7, \, 4, \, 3)$ Hamming code under consideration, the correct information word is decided if at most one bit within the codeword is corrupted during transmission. It follows:
+'''(6)'''&nbsp;  For the&nbsp; $(7, \, 4, \, 3)$&nbsp; Hamming code under consideration,&nbsp; the correct information word is decided if at most one bit within the code word is corrupted during transmission.&nbsp; It follows:
 :$${ \rm Pr(block\:errors)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} { \rm Pr(\ge 2\hspace{0.15cm}bit\hspace{0.15cm}errors\hspace{0.15cm})} =1 - { \rm Pr(0\hspace{0.15cm}bit\hspace{0.15cm}errors)} - { \rm Pr(1\hspace{0.15cm}bit\hspace{0.15cm}errors)} =1 - 0.9^7 - 7 \cdot 0.1 \cdot 0.9^7 \hspace{0.15cm} \underline{ = 0.15} \hspace{0.05cm}.$$
-*Uncoded transmission of a block with $n = k = 4$ bits would result in the same BSC channel:
+*Uncoded transmission of a block with&nbsp; $n = k = 4$&nbsp; bits would result in the same BSC channel:
 :$${ \rm Pr(block\:errors)}= 1 - 0.9^4 \approx 0.344 \hspace{0.05cm}.$$
-*The comparison is not entirely fair, however, since with $n = 4$ a smaller corruption probability $\varepsilon$ would have to be applied than with $n = 7$ (smaller symbol rate &nbsp; ⇒&nbsp; smaller bandwidth &nbsp; ⇒ &nbsp; smaller noise power).
+*The comparison is not entirely fair,&nbsp; however,&nbsp; since with&nbsp; $n = 4$&nbsp; a smaller falsification probability&nbsp; $\varepsilon$&nbsp; would have to be applied than with&nbsp; $n = 7$&nbsp; $($smaller symbol rate &nbsp; ⇒ &nbsp; smaller bandwidth &nbsp; ⇒ &nbsp; smaller noise power$)$.
 {{ML-Fuß}}

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
-[[File:P_ID2397__KC_A_1_11.png|right|frame|Syndrome and coset leaders (incomplete list) of &nbsp;$\rm HC \ (7, \, 4, \, 3)$ ]]
+[[File:P_ID2397__KC_A_1_11.png|right|frame|Syndrome and coset leaders (incomplete list) of &nbsp;$\rm HC \ (7, \, 4, \, 3)$ '''Korrektur''' ]]
-To decode a &nbsp;$(7, \, 4, \, 3)$ Hamming code,&nbsp; which is defined by its parity-check matrix
+To decode a &nbsp;$(7, \, 4, \, 3)$&nbsp; Hamming code,&nbsp; which is defined by its parity-check matrix
 :$${ \boldsymbol{\rm H}}_{\rm } = \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},$$
-"syndrome decoding"&nbsp; is also suitable.&nbsp; Since all Hamming codes are perfect,&nbsp; the result is as good as with the&nbsp; (in the general case)&nbsp; more complicated maximum likelihood decoding.
+"syndrome decoding"&nbsp; is also suitable.&nbsp; Since all Hamming codes are perfect,&nbsp; the result is as good as with the&nbsp; $($in the general case$)$&nbsp; more complicated maximum likelihood decoding.
 For&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Principle_of_syndrome_decoding|"syndrome decoding"]]&nbsp; one proceeds as follows:
-*From the received vector&nbsp; $\underline{y}$&nbsp; one forms the syndrome&nbsp; $($it holds&nbsp; $m = n - k)$:
+*From the received vector&nbsp; $\underline{y}$ &nbsp; one forms the syndrome&nbsp; $($it holds&nbsp; $m = n - k)$:
 :$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$
-*In&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"BSC channel"]]&nbsp; the received word is also &nbsp; $\underline{y} = \underline{x} \, ({\rm codeword}) + \underline{e} \, ({\rm error\:vector})$ &nbsp; an element of&nbsp; ${\rm GF}(2^n)$,&nbsp; and it holds because of&nbsp;&nbsp; $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
+*In&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"BSC channel"]]&nbsp; the received word &nbsp; $\underline{y} = \underline{x} \, ({\rm codeword}) + \underline{e} \, ({\rm error\:vector})$ &nbsp; is also an element of&nbsp; ${\rm GF}(2^n)$,&nbsp; and it holds because of&nbsp;&nbsp; $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
-  \underline{0}$&nbsp; equally:
+  \underline{0}$:
 :$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T} \hspace{0.05cm}.$$
@@ Line 40: / Line 40: @@
 * This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes|"Decoding of Linear Block Codes"]].
-* Underlying is a Hamming code with parameters&nbsp; $n = 7$&nbsp; and&nbsp; $k = 4$ &nbsp; &rArr; &nbsp; $m = 3$.&nbsp; All code words have the following format:
+* Underlying is a Hamming code with parameters&nbsp; $n = 7$,&nbsp; $k = 4$ &nbsp; &rArr; &nbsp; $m = 3$.&nbsp; All code words have the following format:
 :$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$
 *The parity-check equations are illustrated on the information sheet for&nbsp; [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|"Exercise 1.11Z"]]&nbsp; which considers the same constellation as in the present exercise.
@@ Line 63: / Line 63: @@
 |type="[]"}
 - The last three bits of&nbsp; $\underline{e}_{\mu}$&nbsp; are identical to&nbsp; $\underline{s}_{\mu}$ .
-- All&nbsp; $\underline{e}_{\mu}$&nbsp; contain a single&nbsp; $1$ each.
+- All&nbsp; $\underline{e}_{\mu}$&nbsp; contain a single&nbsp; "$1$"&nbsp; each.
-+ All&nbsp; $\underline{e}_{\mu}$&nbsp; include at most one&nbsp; $1$.
++ All&nbsp; $\underline{e}_{\mu}$&nbsp; include at most one&nbsp; "$1$".
 {What syndrome&nbsp; $\underline{s}_{\mu}$&nbsp; does the error vector&nbsp; $(1, 0, 0, 0, 0, 0, 0)$&nbsp; lead to?