Aufgaben:Exercise 2.16: Bounded Distance Decoding: Decision Regions - Revision history

Hwang at 15:31, 23 January 2023

2023-01-23T15:31:45Z

Guenter at 14:48, 8 November 2022

2022-11-08T14:48:13Z

Guenter at 14:26, 2 November 2022

2022-11-02T14:26:48Z

Guenter at 13:57, 2 November 2022

2022-11-02T13:57:14Z

Hwang at 19:05, 1 November 2022

2022-11-01T19:05:17Z

Noah at 16:55, 17 September 2022

2022-09-17T16:55:34Z

Noah at 16:20, 17 September 2022

2022-09-17T16:20:44Z

Noah at 16:19, 17 September 2022

2022-09-17T16:19:44Z

Show changes

Guenter at 15:58, 4 September 2022

2022-09-04T15:58:06Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.16: Entscheidungskriterien bei BDD to Aufgaben:Exercise 2.16: Bounded Distance Decoding: Decision Regions

2022-09-04T15:52:00Z

Guenter moved page Aufgabe 2.16: Entscheidungskriterien bei BDD to Exercise 2.16: Bounded Distance Decoding: Decision Regions

@@ Line 9: / Line 9: @@
 The diagram shows such spaces in  schematic two-dimensional representation.&nbsp; The illustration is to be interpreted as follows:
 # The red dot&nbsp; $\underline{c}_j$&nbsp; was sent.&nbsp; All red outlined points&nbsp; $\underline{y}_i$&nbsp; in a hypersphere around this point&nbsp; $\underline{c}_j$&nbsp; with the parameter&nbsp; $t$&nbsp; as radius can be corrected.&nbsp; Using the nomenclature according to the&nbsp; [[Channel_Coding/Error_Probability_and_Areas_of_Application#Block_error_probability_for_RSC_and_BDD|$\rm graph$]]&nbsp; in the theory section,&nbsp; then&nbsp; $\underline{z}_i = \underline{c}_j$ &nbsp; <br>&#8658; &nbsp; "Error correction is successful".
-# For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be corrupted into a blue&nbsp; $($or white-blue$)$&nbsp; dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hypersphere of another code word&nbsp; $\underline{c}_{k &ne; j}$.&nbsp; In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
+# For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be falsified into a blue&nbsp; $($or white-blue$)$&nbsp; dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hypersphere of another code word&nbsp; $\underline{c}_{k &ne; j}$.&nbsp; In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
 # Finally,&nbsp; as in the sketch below,&nbsp; there may be yellow dots that do not belong to any hypersphere &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is not decodable".

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Error_Probability_and_Areas_of_Application}}
-[[File: P_ID2583__KC_A_2_16neu.png|right|frame|Two coding space schemes]]
+[[File:EN_KC_A_2_16.png|right|frame|Two coding space schemes]]
 We assume a block code of length&nbsp; $n$&nbsp; with symbols&nbsp; $c_i &#8712; {\rm GF}(2^m)$&nbsp; that can correct up to &nbsp;$t$&nbsp; symbols.&nbsp;
 *Each possible received word&nbsp; $\underline{y}_i$&nbsp; can then be viewed as a point in a high-dimensional space.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Error_Probability_and_Areas_of_Application}}
-[[File: P_ID2583__KC_A_2_16neu.png|right|frame|Considered coding space schemes]]
+[[File: P_ID2583__KC_A_2_16neu.png|right|frame|Two coding space schemes]]
 We assume a block code of length&nbsp; $n$&nbsp; with symbols&nbsp; $c_i &#8712; {\rm GF}(2^m)$&nbsp; that can correct up to &nbsp;$t$&nbsp; symbols.&nbsp;
 *Each possible received word&nbsp; $\underline{y}_i$&nbsp; can then be viewed as a point in a high-dimensional space.
@@ Line 38: / Line 38: @@
 {Which statement is true for the probability that a received word&nbsp; $\underline{y}$&nbsp; cannot be decoded with Hamming coding?
 |type="[]"}
-+ The probability&nbsp; ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is exactly zero.
++ The probability&nbsp; ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$&nbsp; is exactly zero.
-- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero,&nbsp; but negligible.
+- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$&nbsp; is nonzero,&nbsp; but negligible.
-- It holds &nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
+- It holds &nbsp; ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} decoded)$.
 {Which coding space scheme applies to the Reed&ndash;Solomon codes?
@@ Line 49: / Line 49: @@
 {Which statement applies to the probability that a received word&nbsp; $\underline{y}$&nbsp; cannot be decoded after Reed&ndash;Solomon coding?
 |type="[]"}
-- The probability &nbsp; ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$ &nbsp; is exactly zero.
+- The probability &nbsp; ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$ &nbsp; is exactly zero.
-- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero,&nbsp; but negligible.
+- ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$&nbsp; is nonzero,&nbsp; but negligible.
-+ It holds &nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
++ It holds &nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} decoded)$.
 </quiz>
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct is <u>solution 1</u>, since the coding space scheme &nbsp;$\rm A$&nbsp; describes a perfect code and each Hamming code $(n, \, k, \, 3)$ is a perfect code:
+'''(1)'''&nbsp; Correct is&nbsp; <u>solution 1</u>,&nbsp; since the coding space scheme &nbsp;$\rm A$&nbsp; describes a perfect code and each Hamming code&nbsp; $(n, \, k, \, 3)$&nbsp; is a perfect code:
-*For any Hamming code $(n, \, k, \, 3)$, there are a total of $2^n$ possible received words $\underline{y}_i$, which are assigned to one of $2^k$ possible code words $\underline{c}_j$ during syndrome decoding.
+*For any Hamming code&nbsp; $(n, \, k, \, 3)$,&nbsp; there are a total of&nbsp; $2^n$&nbsp; possible received words&nbsp; $\underline{y}_i$,&nbsp; which are assigned to one of&nbsp; $2^k$&nbsp; possible code words&nbsp; $\underline{c}_j$&nbsp; during syndrome decoding.
-*Because of the HC property $d_{\rm min} = 3$, all spheres in $n$ dimensional space have radius $t = 1$. Thus in all spheres there are $2^{n-k}$ points, for example.
-:* $\text{HC (7, 4, 3)}$: &nbsp; one point for error-free transmission and seven points for a bit error &nbsp; &#8658; &nbsp; $1 + 7 = 8 = 2^3 = 2^{7-4}$.
+*Because of the Hamming code property&nbsp; $d_{\rm min} = 3$,&nbsp; all spheres in the&nbsp; $n$&ndash;dimensional space have radius&nbsp; $t = 1$.&nbsp; Thus in all spheres there are&nbsp; $2^{n-k}$ points.
-Note: &nbsp;Since the Hamming code is a binary code, here the code space has the dimension&nbsp; $n$.
+:* $\text{HC (7, 4, 3)}$: &nbsp; One point for error-free transmission and seven points for one bit error &nbsp; &#8658; &nbsp; $1 + 7 = 8 = 2^3 = 2^{7-4}$.
 '''(3)'''&nbsp; The Reed&ndash;Solomon codes are described by the coding space scheme &nbsp;$\rm B$&nbsp; &nbsp;&#8658;&nbsp; <u>Answer 2</u>.
-*Here there are numerous yellow points in the gray area, i.e. points that cannot be assigned to any sphere in <i>Bounded Distance Decoding</i> (BDD).
-*For example, if we consider the $\rm RSC \, (7, \, 3, \, 5)_8$ with code parameters $n = 7, \, k = 3$ and $t = 2$, there are a total of $8^7 = 2097152$ points and $8^3 = 512$ hypersphere here.
+'''(3)'''&nbsp; The Reed&ndash;Solomon codes are described by the coding space scheme &nbsp;$\rm B$&nbsp; &nbsp; &#8658; &nbsp; <u>Answer 2</u>.
-*If this code were perfect, then there should be $8^4 = 4096$ points within each sphere. However, it holds:
+*Here there are numerous yellow points in the gray area,&nbsp; i.e. points that cannot be assigned to any sphere in&nbsp; "Bounded Distance Decoding".
 :$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}lies\hspace{0.1cm} within\hspace{0.1cm} the\hspace{0.1cm} red\hspace{0.1cm} sphere)}
 = {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079
 \hspace{0.05cm}.$$
-*For ${\rm Pr}(f = 1)$ it is considered that there can be "$7 \rm \ over \ 1$" $= 7$ error positions, and for each error position also seven different error values. The same is considered for ${\rm Pr}(f = 2)$.
+*For&nbsp; ${\rm Pr}(f = 1)$&nbsp; it is considered that there can be&nbsp; "$7 \rm \ over \ 1$" $= 7$&nbsp; error positions,&nbsp; and for each error position also seven different error values.&nbsp; The same is considered for&nbsp; ${\rm Pr}(f = 2)$.
-'''(4)'''&nbsp; Correct is <u>answer 3</u>:
+'''(4)'''&nbsp; Correct is&nbsp; <u>answer 3</u>:
 *A point in gray no-man's land is reached with fewer symbol errors than a point in another hypersphere.
-*For long codes, an upper bound on the corruption probability is given in the literature:
-:$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)}
+:$${\rm Pr}(\underline{y} {\rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} decoded})
 = {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!}
 \hspace{0.05cm}.$$
-*For the ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$, this upper bound yields the value $1/(16!) < 10^{-14}$.
+*For the ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$ &nbsp; &rArr; &nbsp; this upper bound yields the value&nbsp; $1/(16!) < 10^{-14}$.
 {{ML-Fuß}}

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Error_Probability_and_Areas_of_Application}}
 [[File: P_ID2583__KC_A_2_16neu.png|right|frame|Considered coding space schemes]]
-We assume a block code of length&nbsp; $n$&nbsp; with symbols&nbsp; $c_i &#8712; {\rm GF}(2^m)$&nbsp; that can correct up to &nbsp;$t$&nbsp; symbols. Each possible received word&nbsp; $\underline{y}_i$&nbsp; can then be viewed as a point in a high-dimensional space. Assuming the basis&nbsp; ${\rm GF}(2) = \{0, \, 1\}$&nbsp; the dimension&nbsp; $n is \cdot m$.
+We assume a block code of length&nbsp; $n$&nbsp; with symbols&nbsp; $c_i &#8712; {\rm GF}(2^m)$&nbsp; that can correct up to &nbsp;$t$&nbsp; symbols.&nbsp;
-The diagram shows such a space in simplified, schematic two dimensional representation.
+*Assuming the basis&nbsp; ${\rm GF}(2) = \{0, \, 1\}$&nbsp; the dimension is&nbsp; $n \cdot m$.
-* For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be corrupted into a blue (or white-blue) dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hyper-sphere of another code word&nbsp; $\underline{c}_{k &ne; j}$&nbsp;. In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
+The diagram shows such spaces in  schematic two-dimensional representation.&nbsp; The illustration is to be interpreted as follows:
+# The red dot&nbsp; $\underline{c}_j$&nbsp; was sent.&nbsp; All red outlined points&nbsp; $\underline{y}_i$&nbsp; in a hypersphere around this point&nbsp; $\underline{c}_j$&nbsp; with the parameter&nbsp; $t$&nbsp; as radius can be corrected.&nbsp; Using the nomenclature according to the&nbsp; [[Channel_Coding/Error_Probability_and_Areas_of_Application#Block_error_probability_for_RSC_and_BDD|$\rm graph$]]&nbsp; in the theory section,&nbsp; then&nbsp; $\underline{z}_i = \underline{c}_j$ &nbsp; <br>&#8658; &nbsp; "Error correction is successful".
-* Finally, as in the sketch below, there may be yellow dots that do not belong to any hypersphere &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is not decodable".
+# For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be corrupted into a blue&nbsp; $($or white-blue$)$&nbsp; dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hypersphere of another code word&nbsp; $\underline{c}_{k &ne; j}$.&nbsp; In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
 In this exercise you are to decide which of the two code space schemes is suitable for describing
-* [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|"Bounded Distance Decoding &nbsp;(BDD) of Hamming codes"]] respectively.
+* [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|"Bounded Distance Decoding  of Hamming codes"]],&nbsp; resp.
@@ Line 24: / Line 22: @@
 * It is intended to illustrate significant differences in decoding Reed&ndash;Solomon codes and Hamming codes.
@@ Line 38: / Line 36: @@
 - Coding space scheme &nbsp;$\rm B$.
-{Which statement is true for the probability that a received word&nbsp; $\underline{y}$&nbsp; cannot be decoded when Hamming coding?
+{Which statement is true for the probability that a received word&nbsp; $\underline{y}$&nbsp; cannot be decoded with Hamming coding?
 |type="[]"}
-+ The probability ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is exactly zero.
++ The probability&nbsp; ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is exactly zero.
-- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero, but negligible.
+- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero,&nbsp; but negligible.
-- It holds&nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
+- It holds &nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
 {Which coding space scheme applies to the Reed&ndash;Solomon codes?
@@ Line 51: / Line 49: @@
 {Which statement applies to the probability that a received word&nbsp; $\underline{y}$&nbsp; cannot be decoded after Reed&ndash;Solomon coding?
 |type="[]"}
-- The probability ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is exactly zero.
+- The probability &nbsp; ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$ &nbsp; is exactly zero.
-- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero, but negligible.
+- ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$&nbsp; is nonzero,&nbsp; but negligible.
-+ It holds&nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
++ It holds &nbsp; ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.
 </quiz>

@@ Line 9: / Line 9: @@
 * The red dot&nbsp; $\underline{c}_j$ was sent. All red outlined points&nbsp; $\underline{y}_i$&nbsp; in a hypersphere around this point&nbsp; $\underline{c}_j$&nbsp; with the parameter&nbsp; $t$&nbsp; as radius can be corrected. Using the nomenclature according to the&nbsp; [[Channel_Coding/Error_Probability_and_Areas_of_Application#Block_error_probability_for_RSC_and_BDD|"graph"]]&nbsp; in the theory section, then&nbsp; $\underline{z}_i = \underline{c}_j$ &nbsp; <br>&#8658; &nbsp; "Error correction is successful".
-* For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be corrupted into a blue (or white-blue) dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hyper-sphere of another codeword&nbsp; $\underline{c}_{k &ne; j}$&nbsp;. In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
+* For very many symbol errors,&nbsp; $\underline{c}_j$&nbsp; may be corrupted into a blue (or white-blue) dot&nbsp; $\underline{y}_j$&nbsp; belonging to the hyper-sphere of another code word&nbsp; $\underline{c}_{k &ne; j}$&nbsp;. In this case the decoder makes a wrong decision &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is decoded incorrectly".
 * Finally, as in the sketch below, there may be yellow dots that do not belong to any hypersphere &nbsp; <br>&#8658; &nbsp; "The received word&nbsp; $\underline{y}_j$&nbsp; is not decodable".
@@ Line 59: / Line 59: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp; Correct is <u>solution 1</u>, since the coding space scheme &nbsp;$\rm A$&nbsp; describes a perfect code and each Hamming code $(n, \, k, \, 3)$ is a perfect code:
-*For any Hamming code $(n, \, k, \, 3)$, there are a total of $2^n$ possible received words $\underline{y}_i$, which are assigned to one of $2^k$ possible codewords $\underline{c}_j$ during syndrome decoding.
+*For any Hamming code $(n, \, k, \, 3)$, there are a total of $2^n$ possible received words $\underline{y}_i$, which are assigned to one of $2^k$ possible code words $\underline{c}_j$ during syndrome decoding.
 *Because of the HC property $d_{\rm min} = 3$, all spheres in $n$ dimensional space have radius $t = 1$. Thus in all spheres there are $2^{n-k}$ points, for example.
 :* $\text{HC (7, 4, 3)}$: &nbsp; one point for error-free transmission and seven points for a bit error &nbsp; &#8658; &nbsp; $1 + 7 = 8 = 2^3 = 2^{7-4}$.

← Older revision		Revision as of 15:58, 4 September 2022
Line 98:		Line 98:


−	[[Category:Channel Coding: Exercises\|^2.6 ~~RSC–Fehlerwahrscheinlichkeit~~^]]	+	[[Category:Channel Coding: Exercises\|^2.6 Block Error Probability of RS Codes^]]

← Older revision	Revision as of 15:52, 4 September 2022
(No difference)