Aufgaben:Exercise 1.13: Binary Erasure Channel Decoding - Revision history

Hwang at 16:02, 23 January 2023

2023-01-23T16:02:49Z

Hwang at 16:59, 1 November 2022

2022-11-01T16:59:37Z

Guenter at 12:26, 28 September 2022

2022-09-28T12:26:58Z

Guenter at 14:28, 17 August 2022

2022-08-17T14:28:54Z

Guenter at 15:47, 21 July 2022

2022-07-21T15:47:27Z

Guenter at 14:53, 21 July 2022

2022-07-21T14:53:07Z

Show changes

Guenter at 13:05, 21 July 2022

2022-07-21T13:05:18Z

Noah at 21:14, 16 July 2022

2022-07-16T21:14:28Z

Show changes

Noah at 21:05, 16 July 2022

2022-07-16T21:05:53Z

Show changes

Guenter at 10:01, 11 May 2022

2022-05-11T10:01:21Z

@@ Line 47: / Line 47: @@
 - $\underline{z} = (1, 0, 0, 1, 0, 0, 1).$
-{What are the consequences of the red entries for&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; and&nbsp; $z_{\rm K}$&nbsp; (see graphic on the information page)?
+{What are the consequences of the red entries for&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; and&nbsp; $z_{\rm K}$&nbsp; (see graphic in the information section)?
 |type="[]"}
 + The erasure vector is&nbsp; $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7}).$
@@ Line 61: / Line 61: @@
 - For the present&nbsp; $\underline{y}$ &nbsp; no unique decoding is possible.
-{What are the consequences of the green entries for&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; and&nbsp; $z_{\rm K}$&nbsp; (see graphic on the information page)?
+{What are the consequences of the green entries for&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; and&nbsp; $z_{\rm K}$&nbsp; (see graphic in the information section)?
 |type="[]"}
 + The received word is&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$

@@ Line 30: / Line 30: @@
 * This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes|"Decoding of Linear Block Codes"]].
-* The algorithm for mapping the received word&nbsp; $\underline{y}$&nbsp; to the correct codeword&nbsp; $\underline{z} = \underline{x}$ &nbsp; is described in detail in the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"theory section"]]&nbsp;.
+* The algorithm for mapping the received word&nbsp; $\underline{y}$&nbsp; to the correct code word&nbsp; $\underline{z} = \underline{x}$ &nbsp; is described in detail in the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"theory section"]]&nbsp;.
 * We would like to remind again that in BEC decoding we use the first decoder block&nbsp; $\underline{y} → \underline{z}$&nbsp; as&nbsp; "code word finder"&nbsp; since wrong decisions are excluded here.&nbsp; Each received word is decoded correctly,&nbsp; or it may not be decoded at all.
@@ Line 158: / Line 158: @@
 *In contrast &nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$&nbsp; according to subtask&nbsp; '''(4)'''&nbsp; could not be decoded. In the code table, besides&nbsp; $(1, 1, 0, 1, 0, 0, 1)$&nbsp; with&nbsp; $(1, 1, 0, 0, 0, 1, 0)$&nbsp; one can recognize another code word&nbsp; (highlighted in green),&nbsp; which becomes the received word&nbsp; $\underline{y}$&nbsp; due to the&nbsp; $n_{\rm E} = 3$&nbsp; erasures concerning bit 4, 6 and 7.
-*This case,&nbsp; when the&nbsp; $n_{\rm E} = d_{\rm min}$&nbsp; extinctions affect exactly the&nbsp; $d_{\rm min}$&nbsp; different bits of two codewords, leads to a matrix&nbsp; $\mathbf{H}_{\rm E}$&nbsp; with rank smaller&nbsp; $d_{\rm min}$.
+*This case,&nbsp; when the&nbsp; $n_{\rm E} = d_{\rm min}$&nbsp; extinctions affect exactly the&nbsp; $d_{\rm min}$&nbsp; different bits of two code words, leads to a matrix&nbsp; $\mathbf{H}_{\rm E}$&nbsp; with rank smaller&nbsp; $d_{\rm min}$.
 *If&nbsp; $n_{\rm E} > d_{\rm min}$, the number&nbsp; $n - n_{\rm E}$&nbsp; of bits not erased is smaller than the number&nbsp; $k$&nbsp; of information bits.&nbsp; In this case,&nbsp; of course,&nbsp; the code word cannot be decoded.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
-[[File:EN_KC_A_1_13.png|right|frame|Decoding at the BEC]
+[[File:EN_KC_A_1_13.png|right|frame|Decoding at the BEC]]
 We assume here the model in section&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Decoding at the Binary Erasure Channel"]]&nbsp; (BEC configuration highlighted in green):

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
-[[File:KC_A_1_13_neu.png|right|frame|Decoding at the BEC '''Korrektur''']]
+[[File:EN_KC_A_1_13.png|right|frame|Decoding at the BEC]
 We assume here the model in section&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Decoding at the Binary Erasure Channel"]]&nbsp; (BEC configuration highlighted in green):

← Older revision		Revision as of 15:47, 21 July 2022
Line 160:		Line 160:
	*This case,  when the  $n_{\rm E} = d_{\rm min}$  extinctions affect exactly the  $d_{\rm min}$  different bits of two codewords, leads to a matrix  $\mathbf{H}_{\rm E}$  with rank smaller  $d_{\rm min}$.		*This case,  when the  $n_{\rm E} = d_{\rm min}$  extinctions affect exactly the  $d_{\rm min}$  different bits of two codewords, leads to a matrix  $\mathbf{H}_{\rm E}$  with rank smaller  $d_{\rm min}$.

−	*If  $~~\boldsymbol{\rm H}_~~{\rm E} > d_{\rm min}$, the number  $n - n_{\rm E}$  of bits not erased is smaller than the number  $k$  of information bits.  In this case,  of course,  the code word cannot be decoded.	+	*If  $n_{\rm E} > d_{\rm min}$, the number  $n - n_{\rm E}$  of bits not erased is smaller than the number  $k$  of information bits.  In this case,  of course,  the code word cannot be decoded.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
-[[File:KC_A_1_13_neu.png|right|frame|Decoding at the BEC]]
+[[File:KC_A_1_13_neu.png|right|frame|Decoding at the BEC '''Korrektur''']]
 We assume here the model in section&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Decoding at the Binary Erasure Channel"]]&nbsp; (BEC configuration highlighted in green):
-*Each information word&nbsp; $\underline{u}$&nbsp; is encoded blockwise and yields the codeword&nbsp; $\underline{x}$. Let the block code be linear and completely given by its parity-check matrix&nbsp; $\boldsymbol{\rm H}$.
+*Each information word&nbsp; $\underline{u}$&nbsp; is encoded blockwise and yields the code word&nbsp; $\underline{x}$.&nbsp; Let the block code be linear and completely given by its parity-check matrix&nbsp; $\boldsymbol{\rm H}$.
-*During transmission&nbsp; $n_{\rm E}$&nbsp; bits of the codeword are erased &nbsp; ⇒ &nbsp;[[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|"Binary Erasure Channel"]]&nbsp; (BEC). The codeword&nbsp; $\underline{x}$&nbsp; thus becomes the received word&nbsp; $\underline{y}$.
+*During transmission&nbsp; $n_{\rm E}$&nbsp; bits of the code word are erased &nbsp; ⇒ &nbsp;[[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|"Binary Erasure Channel"]]&nbsp; $\rm (BEC)$.&nbsp; The code word&nbsp; $\underline{x}$&nbsp; thus becomes the received word&nbsp; $\underline{y}$.
-*If the number&nbsp; $n_{\rm E}$&nbsp; of erasures is less than the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"minimum distance"]]&nbsp; $d_{\rm min}$&nbsp; of the code, it is possible to reconstruct from&nbsp; $\underline{y}$&nbsp; the codeword&nbsp; $\underline{z} = \underline{x}$&nbsp; without error, and thus the correct information word&nbsp; $\underline{v} = \underline{u}$ is also obtained.
+*If the number&nbsp; $n_{\rm E}$&nbsp; of erasures is less than the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"minimum distance"]]&nbsp; $d_{\rm min}$&nbsp; of the code,&nbsp; it is possible to reconstruct from&nbsp; $\underline{y}$&nbsp; the code word&nbsp; $\underline{z} = \underline{x}$&nbsp; without error,&nbsp; and thus the correct information word&nbsp; $\underline{v} = \underline{u}$&nbsp; is also obtained.
-For exercise description, let us now consider the Hamming codeword&nbsp; $\underline{x} = (0, 1, 0, 1, 1, 0, 0)$&nbsp; and the received word&nbsp; $\underline{y} = (0, 1, {\rm E} , {\rm E}, 1, 0, 0).$
+For exercise description,&nbsp; let us now consider the Hamming code word&nbsp; $\underline{x} = (0, 1, 0, 1, 1, 0, 0)$&nbsp; and the received word&nbsp; $\underline{y} = (0, 1, {\rm E} , {\rm E}, 1, 0, 0).$
-*The third and fourth bit were thus erased by the channel.
+*The third and fourth bit were thus erased by the channel.&nbsp; The&nbsp; "code word finder"&nbsp; thus has the task to determine the vector&nbsp; $z_{\rm E} = (z_{3}, z_{4})$&nbsp; with&nbsp; $z_{3}, \ z_{4} \in \{0, 1\}$&nbsp; to be determined.&nbsp; This is done according to the equation
 :$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.05cm}.$$
@@ Line 23: / Line 22: @@
 :$$\underline{z}_{\rm K} = (0, 1, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &1 &0 &0\\ 0 &1 &0 &1 &0\\ 1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &1\\ 0 &1 \end{pmatrix} \hspace{0.05cm}.$$
-*This equation gives two equations of determination for the bits to be determined, whose solution leads to the result&nbsp; $z_{3} = 0$&nbsp; and&nbsp; $z_{4} = 1$&nbsp;.
+*This equation gives two equations for the bits to be determined,&nbsp; whose solution leads to the result&nbsp; $z_{3} = 0$&nbsp; and&nbsp; $z_{4} = 1$.
@@ Line 33: / Line 29: @@
 Hints:
 * This exercise belongs to the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes|"Decoding of Linear Block Codes"]].
-* The algorithm for mapping the received word&nbsp; $\underline{y}$&nbsp; to the correct codeword&nbsp; $\underline{z} = \underline{x}$&nbsp; is described in detail in the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Theory section"]]&nbsp;.
-* We would like to remind again that in BEC decoding we use the first decoder block&nbsp; $\underline{y} → \underline{z}$&nbsp; as&nbsp; ''codeword finder''&nbsp; since wrong decisions are excluded here. Each received word is decoded correctly, or it may not be decoded at all.
+* The algorithm for mapping the received word&nbsp; $\underline{y}$&nbsp; to the correct codeword&nbsp; $\underline{z} = \underline{x}$ &nbsp; is described in detail in the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"theory section"]]&nbsp;.
-*In the BSC model, on the other hand, decoding errors cannot be avoided. Accordingly, we refer to the corresponding block there as&nbsp; ''code word estimator''.
@@ Line 42: / Line 41: @@
 ===Questions===
 <quiz display=simple>
-{&nbsp; $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$ was received. Which sequence does the codeword finder decide to use?
+{&nbsp; $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$&nbsp; was received.&nbsp; Which sequence does the code word finder decide to use?
 |type="()"}
 - $\underline{z} = (1, 0, 0, 1, 0, 0, 0),$
@@ Line 52: / Line 51: @@
 + The erasure vector is&nbsp; $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7}).$
 + The received word is&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$
-- $\boldsymbol{\rm H}_{\rm E}$&nbsp; is a&nbsp; $2 \times 3$ matrix.
+- $\boldsymbol{\rm H}_{\rm E}$&nbsp; is a&nbsp; $2 \times 3$&nbsp; matrix.
-+ $\boldsymbol{\rm H}_{\rm E}$&nbsp; is a&nbsp; $3 \times 3$ matrix.
++ $\boldsymbol{\rm H}_{\rm E}$&nbsp; is a&nbsp; $3 \times 3$&nbsp; matrix.
-{Now apply&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$ Which codeword is selected?
+{Now apply&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$&nbsp; Which code word is selected?
 |type="()"}
 - $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 + $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 - $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
-- For the present&nbsp; $\underline{y}$&nbsp; no unique decoding is possible.
+- For the present&nbsp; $\underline{y}$ &nbsp; no unique decoding is possible.
 {What are the consequences of the green entries for&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; and&nbsp; $z_{\rm K}$&nbsp; (see graphic on the information page)?
 |type="[]"}
 + The received word is&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$
-- $\boldsymbol{\rm H}_{\rm K}$&nbsp; differs from subquestion '''(2)''' in the last row.
+- $\boldsymbol{\rm H}_{\rm K}$&nbsp; differs from subtask&nbsp; '''(2)'''&nbsp; in the last row.
-+ $\boldsymbol{\rm H}_{\rm K}$&nbsp; differs from subquestion '''(2)''' in the last column.
++ $\boldsymbol{\rm H}_{\rm K}$&nbsp; differs from subtask&nbsp; '''(2)'''&nbsp; in the last column.
-{Now apply&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$ Which codeword is selected?
+{Now apply&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$&nbsp; Which code word is selected?
 |type="()"}
 - $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 - $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 - $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
-+ For the present&nbsp; $\underline{y}$&nbsp; no unique decoding is possible.
++ For the present&nbsp; $\underline{y}$ &nbsp; no unique decoding is possible.
-{Which statements result for the correction capability at the BEC? $n_{\rm E}$&nbsp; indicates in the following the number of erasures.
+{Which statements result for the correction capability at the BEC?&nbsp; $n_{\rm E}$&nbsp; indicates in the following the number of erasures.
 |type="[]"}
 + For&nbsp; $n_{\rm E} < d_{\rm min}$&nbsp; unique decoding is always possible.

← Older revision		Revision as of 10:01, 11 May 2022
Line 172:		Line 172:


−	[[Category:Channel Coding: Exercises\|^1.5 ~~Decodierung linearer Blockcodes~~^]]	+	[[Category:Channel Coding: Exercises\|^1.5 Linear Block Code Decoding^]]