Aufgaben:Exercise 2.12Z: Reed-Solomon Syndrome Calculation - Revision history

Hwang at 15:30, 23 January 2023

2023-01-23T15:30:49Z

Guenter at 16:18, 30 October 2022

2022-10-30T16:18:02Z

Guenter at 15:53, 30 October 2022

2022-10-30T15:53:41Z

Guenter at 15:43, 30 October 2022

2022-10-30T15:43:34Z

Guenter at 15:35, 30 October 2022

2022-10-30T15:35:50Z

Noah at 16:58, 12 September 2022

2022-09-12T16:58:54Z

Noah at 22:54, 10 September 2022

2022-09-10T22:54:47Z

Noah at 12:43, 10 September 2022

2022-09-10T12:43:13Z

Guenter at 14:23, 4 September 2022

2022-09-04T14:23:31Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.12Z: Reed–Solomon–Syndromberechnung to Aufgaben:Exercise 2.12Z: Reed-Solomon Syndrome Calculation

2022-09-04T14:19:19Z

Guenter moved page Aufgabe 2.12Z: Reed–Solomon–Syndromberechnung to Exercise 2.12Z: Reed-Solomon Syndrome Calculation

@@ Line 12: / Line 12: @@
 Given is the received word &nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$.
-*Based on the syndrome &nbsp; $\underline {s} = (s_0, s_1, s_2) = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}$ &nbsp; it is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were corrupted during transmission.
+*Based on the syndrome &nbsp; $\underline {s} = (s_0, s_1, s_2) = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}$ &nbsp; it is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were falsified during transmission.
 *Given is the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of the considered code and its transpose:

← Older revision		Revision as of 16:18, 30 October 2022
Line 113:		Line 113:

	* Since the received word can actually be decoded according to the specification   ⇒   $\underline{r = 1}$.		* Since the received word can actually be decoded according to the specification   ⇒   $\underline{r = 1}$.
		+
		+	*Without this specification  "The received word can be decoded",  this subtask would not be solvable.
	{{ML-Fuß}}		{{ML-Fuß}}

@@ Line 70: / Line 70: @@
 ===Solution===
 {{ML-Kopf}}
-[[File:P_ID2560__KC_T_2_5_Darstellung.png|right|frame|Conversion tables for the Galois field $\rm GF(2^3)$]]
+[[File:EN_KC_Z_2_5_neu.png|right|frame|Conversion tables for the Galois field&nbsp; $\rm GF(2^3)$]]
 '''(1)'''&nbsp; The corresponding equation for syndrome calculation is:
 :$$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) =
@@ Line 87: / Line 87: @@
 					 \hspace{0.05cm}.$$
-The first element results in
+*The first element results in
 :$$s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^2 + 1 \cdot \alpha^4 + \alpha \cdot \alpha^5=
 \alpha  + \alpha^5 + \alpha^4+ \alpha^6$$
 :$$\Rightarrow\hspace{0.3cm} s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  (\alpha) + (\alpha^2 + \alpha+ 1)+ (\alpha^2 + \alpha) + + (\alpha^2 +  1) = \alpha^2 + \alpha = \alpha^4\hspace{0.05cm}.$$
-Correct is the <u>proposed solution 1</u>.
+*Correct is the&nbsp; <u>proposed solution 1</u>.
-'''(2)'''&nbsp; Correspondingly, for the second syndrome element, the <u>proposed solution 2</u> applies accordingly:
+'''(2)'''&nbsp; Correspondingly,&nbsp; for the second syndrome element,&nbsp; the&nbsp; <u>proposed solution 2</u>&nbsp; applies accordingly:
 :$$s_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^4 + 1 \cdot \alpha^1 + \alpha \cdot \alpha^3=
 \alpha  + \alpha^7 + \alpha+ \alpha^4= 1 + \alpha^4 = \alpha^2 + \alpha + 1 =  \alpha^5
@@ Line 101: / Line 101: @@
-'''(3)'''&nbsp; To calculate $s_2$ must be multiplied by the last matrix column:
+'''(3)'''&nbsp; To calculate $s_2$,&nbsp; the received word must be multiplied by the last matrix column:
 :$$s_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^6 + 1 \cdot \alpha^5 + \alpha \cdot \alpha^1=
 \alpha  + \alpha^2 + \alpha^5 + \alpha^2=\alpha^5 + \alpha = (\alpha^2 + \alpha + 1) + \alpha = \alpha^2  + 1 = \alpha^5
 					 \hspace{0.05cm}.$$
-Correct is the <u>proposed solution 3</u>.
+*Correct is the&nbsp; <u>proposed solution 3</u>.
-'''(4)'''&nbsp; Due to the calculated syndrome $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) &ne; 0$ the received word contains at least one symbol error &nbsp; &#8658; &nbsp; $r > 0$.
+'''(4)'''&nbsp; Due to the calculated syndrome &nbsp; $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) &ne; 0$,&nbsp; the received word contains at least one symbol error &nbsp; &#8658; &nbsp; $r > 0$.
-*The present Reed&ndash;Solomon&ndash;code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ cannot correct more than $t = &lfloor;d_{\rm min}/2&rfloor; = 1$ errors.
+*The present Reed&ndash;Solomon&ndash;code&nbsp; $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$&nbsp; cannot correct more than&nbsp; $t = &lfloor;d_{\rm min}/2&rfloor; = 1$&nbsp; errors.
-* Since the received word can actually be decoded according to the specification,&nbsp; $\underline{r = 1}$ holds.
 {{ML-Fuß}}

@@ Line 9: / Line 9: @@
 # coefficient vector representation.
-* Given the received word &nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$.
 *Based on the syndrome &nbsp; $\underline {s} = (s_0, s_1, s_2) = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}$ &nbsp; it is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were corrupted during transmission.
@@ Line 33: / Line 34: @@
-Hints:&nbsp; This exercise refers to the section&nbsp; [[Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding#Step_.28A.29:_Evaluation_of_the_syndrome_in_BDD| "Step (A): Evaluation of the syndrome in BDD"]]&nbsp; of the chapter&nbsp; "Error coding according to Reed&ndash;Solomon coding".
+Hints:&nbsp; This exercise refers to the section&nbsp; [[Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding#Step_.28A.29:_Evaluation_of_the_syndrome_in_BDD| "Step (A): Evaluation of the syndrome in BDD"]]&nbsp; of the chapter&nbsp; "Error Correction according to Reed&ndash;Solomon Coding".
@@ Line 41: / Line 42: @@
 ===Questions===
 <quiz display=simple>
-{Received was&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Specify the first element of the syndrome&nbsp; $\underline{s} = (s_0, \, s_1, \, s_2)$&nbsp;.
+{It holds for the weceived word: &nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Specify the first element of the syndrome&nbsp; $\underline{s} = (s_0, \, s_1, \, s_2)$.
 |type="()"}
 + $s_0 = \alpha^4$,
@@ Line 62: / Line 63: @@
 - $s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.
-{Know that the received word at hand&nbsp; $\underline{y}$&nbsp; can be decoded correctly. How many symbol errors does the received word contain?
+{Known is that the received word &nbsp; $\underline{y}$ &nbsp; can be decoded correctly.&nbsp; How many symbol errors does the received word contain?
 |type="{}"}
 $r \ = \ ${ 1 3% }

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding}}
-[[File:P_ID2559__KC_T_2_5_Darstellung.png|right|frame|Conversion table for the Galois field&nbsp; $\rm GF(2^3)$]]
+[[File:EN_KC_Z_2_5_neu.png|right|frame|$\rm GF(2^3)$&nbsp; representation as powers, polynomials, vectors]]
-As in the&nbsp; [[Aufgaben:Exercise_2.12:_Decoding_at_RSC_(7,_4,_4)_to_Base_8|"Exercise 2. 12"]]&nbsp; we consider the Reed&ndash;Solomon code&nbsp; $(7, \, 4, \, 4)_8$ based on the Galois field&nbsp; ${\rm GF}(q)$&nbsp; with&nbsp; $q = 8 = 2^3$&nbsp;. The graph shows the corresponding conversion table.
+As in the&nbsp; [[Aufgaben:Exercise_2.12:_Decoding_at_RSC_(7,_4,_4)_to_Base_8|"Exercise 2. 12"]]&nbsp; we consider the Reed&ndash;Solomon code&nbsp; $(7, \, 4, \, 4)_8$&nbsp; based on the Galois field&nbsp; ${\rm GF}(q)$&nbsp; with &nbsp; $q = 8 = 2^3$. &nbsp; The graph shows the corresponding conversion table.
-Given are the possible code symbols in exponent representation $($potencies of&nbsp; $\alpha)$&nbsp; and in polynomial&ndash; and coefficient vector representation.
+Given are the possible code symbols in
-Given the received word&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Based on the syndrome
+* Given the received word &nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$.
-is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were corrupted during transmission. Given is the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of the considered code and its transpose:
+*Based on the syndrome &nbsp; $\underline {s} = (s_0, s_1, s_2) = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}$ &nbsp; it is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were corrupted during transmission.
 :$${ \boldsymbol{\rm H}} =
 \begin{pmatrix}
@@ Line 29: / Line 33: @@
+Hints:&nbsp; This exercise refers to the section&nbsp; [[Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding#Step_.28A.29:_Evaluation_of_the_syndrome_in_BDD| "Step (A): Evaluation of the syndrome in BDD"]]&nbsp; of the chapter&nbsp; "Error coding according to Reed&ndash;Solomon coding".

@@ Line 1: / Line 1: @@
-{{quiz-Header|Buchseite=Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung}}
+{{quiz-Header|Buchseite=Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding}}
 [[File:P_ID2559__KC_T_2_5_Darstellung.png|right|frame|Conversion table for the Galois field&nbsp; $\rm GF(2^3)$]]
-Wie in der&nbsp; [[Aufgaben:Exercise_2.12:_Decoding_at_RSC_(7,_4,_4)_to_Base_8|"Aufgabe 2.12"]]&nbsp; betrachten wir den Reed&ndash;Solomon&ndash;Code&nbsp; $(7, \, 4, \, 4)_8$, der auf dem Galoisfeld&nbsp; ${\rm GF}(q)$&nbsp; mit&nbsp; $q = 8 = 2^3$&nbsp; basiert. Die Grafik zeigt die zugehörige Umrechnungstabelle.
+As in the&nbsp; [[Aufgaben:Exercise_2.12:_Decoding_at_RSC_(7,_4,_4)_to_Base_8|"Exercise 2. 12"]]&nbsp; we consider the Reed&ndash;Solomon code&nbsp; $(7, \, 4, \, 4)_8$ based on the Galois field&nbsp; ${\rm GF}(q)$&nbsp; with&nbsp; $q = 8 = 2^3$&nbsp;. The graph shows the corresponding conversion table.
-Gegeben sind die möglichen Codesymbole in Exponentendarstellung $($Potenzen von&nbsp; $\alpha)$&nbsp; sowie in Polynom&ndash; und Koeffizientenvektordarstellung.
+Given are the possible code symbols in exponent representation $($potencies of&nbsp; $\alpha)$&nbsp; and in polynomial&ndash; and coefficient vector representation.
-Vorgegeben ist das Empfangswort&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Anhand des Syndroms
+Given the received word&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Based on the syndrome
 :$$\underline {s} = (s_0, s_1, s_2) = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}$$
-soll überprüft werden, ob einzelne Symbole des Empfangsvektors&nbsp; $\underline{y}$&nbsp; bei der Übertragung verfälscht wurden. Gegeben ist hierzu die Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; des betrachteten Codes und deren Transponierte:
+is to check whether individual symbols of the received vector&nbsp; $\underline{y}$&nbsp; were corrupted during transmission. Given is the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of the considered code and its transpose:
 :$${ \boldsymbol{\rm H}} =
 \begin{pmatrix}
@@ Line 34: / Line 34: @@
-''Hinweis:''
+Hints:
-* Die Aufgabe bezieht sich auf die Seite&nbsp;  [[Channel_Coding/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Schritt&nbsp; $\rm (A)$: Auswertung des Syndroms beim BDD]]&nbsp; des Kapitels "Fehlercodierung nach Reed&ndash;Solomon&ndash;Codierung".
+* This exercise refers to the page&nbsp; [[Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding#Step_.28A.29:_Evaluation_of_the_syndrome_in_BDD| "Step (A): Evaluation of the syndrome in BDD"]]&nbsp; of the chapter "Error coding according to Reed&ndash;Solomon coding".
@@ Line 41: / Line 41: @@
-===Fragebogen===
+===Questions===
 <quiz display=simple>
-{Empfangen wurde&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Geben Sie das erste Element des Syndroms&nbsp; $\underline{s} = (s_0, \, s_1, \, s_2)$&nbsp; an.
+{Received was&nbsp; $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Specify the first element of the syndrome&nbsp; $\underline{s} = (s_0, \, s_1, \, s_2)$&nbsp;.
 |type="()"}
 + $s_0 = \alpha^4$,
 - $s_0 = \alpha^5$,
 - $s_0 = \alpha^6$,
-- $s_0 = 0, \, 1, \, \alpha, \, \alpha^2$&nbsp; oder&nbsp; $\alpha^3$.
+- $s_0 = 0, \, 1, \, \alpha, \, \alpha^2$&nbsp; or&nbsp; $\alpha^3$.
-{Wie lautet bei gleichem Empfangswort das zweite Syndromelement?
+{What is the second syndrome element for the same received word?
 |type="()"}
 - $s_1 = \alpha^4$,
 + $s_1 = \alpha^5$,
 - $s_1 = \alpha^6$,
-- $s_1 = 0, \, 1, \, \alpha, \, \alpha^2$&nbsp; oder&nbsp; $\alpha^3$.
+- $s_1 = 0, \, 1, \, \alpha, \, \alpha^2$&nbsp; or&nbsp; $\alpha^3$.
-{Wie lautet bei gleichem Empfangswort das dritte Syndromelement?
+{What is the third syndrome element for the same received word?
 |type="()"}
 - $s_2 = \alpha^4$,
@@ Line 64: / Line 64: @@
 - $s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.
-{Bekannt ist, dass das vorliegende Empfangswort&nbsp; $\underline{y}$&nbsp; richtig decodiert werden kann. Wieviele Symbolfehler beinhaltet das Empfangswort?
+{Know that the received word at hand&nbsp; $\underline{y}$&nbsp; can be decoded correctly. How many symbol errors does the received word contain?
 |type="{}"}
 $r \ = \ ${ 1 3% }
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-[[File:P_ID2560__KC_T_2_5_Darstellung.png|right|frame|Umrechnungstabellen für das Galoisfeld $\rm GF(2^3)$]]
+[[File:P_ID2560__KC_T_2_5_Darstellung.png|right|frame|Conversion tables for the Galois field $\rm GF(2^3)$]]
-'''(1)'''&nbsp; Die entsprechende Gleichung zur Syndromberechnung lautet:
+'''(1)'''&nbsp; The corresponding equation for syndrome calculation is:
 :$$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) =
 \begin{pmatrix}
@@ Line 88: / Line 88: @@
 					 \hspace{0.05cm}.$$
-Das erste Element ergibt sich zu
+The first element results in
 :$$s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^2 + 1 \cdot \alpha^4 + \alpha \cdot \alpha^5=
 \alpha  + \alpha^5 + \alpha^4+ \alpha^6$$
 :$$\Rightarrow\hspace{0.3cm} s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  (\alpha) + (\alpha^2 + \alpha+ 1)+ (\alpha^2 + \alpha) + + (\alpha^2 +  1) = \alpha^2 + \alpha = \alpha^4\hspace{0.05cm}.$$
-Richtig ist der <u>Lösungsvorschlag 1</u>.
+Correct is the <u>proposed solution 1</u>.
-'''(2)'''&nbsp; Entsprechend gilt für das zweite Syndromelement entsprechend dem der <u>Lösungsvorschlag 2</u>:
+'''(2)'''&nbsp; Correspondingly, for the second syndrome element, the <u>proposed solution 2</u> applies accordingly:
 :$$s_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^4 + 1 \cdot \alpha^1 + \alpha \cdot \alpha^3=
 \alpha  + \alpha^7 + \alpha+ \alpha^4= 1 + \alpha^4 = \alpha^2 + \alpha + 1 =  \alpha^5
@@ Line 102: / Line 102: @@
-'''(3)'''&nbsp; Zur Berechnung von $s_2$ muss mit der letzten Matrixspalte multipliziert werden:
+'''(3)'''&nbsp; To calculate $s_2$ must be multiplied by the last matrix column:
 :$$s_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  \alpha \cdot 1 + \alpha^3 \cdot \alpha^6 + 1 \cdot \alpha^5 + \alpha \cdot \alpha^1=
 \alpha  + \alpha^2 + \alpha^5 + \alpha^2=\alpha^5 + \alpha = (\alpha^2 + \alpha + 1) + \alpha = \alpha^2  + 1 = \alpha^5
 					 \hspace{0.05cm}.$$
-Richtig ist der  <u>Lösungsvorschlag 3</u>.
+Correct is the <u>proposed solution 3</u>.
-'''(4)'''&nbsp; Aufgrund des errechneten Syndroms $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) &ne; 0$ beinhaltet das Empfangswort mindestens einen Symbolfehler &nbsp; &#8658; &nbsp; $r > 0$.
+'''(4)'''&nbsp; Due to the calculated syndrome $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) &ne; 0$ the received word contains at least one symbol error &nbsp; &#8658; &nbsp; $r > 0$.
-*Der vorliegende Reed&ndash;Solomon&ndash;Code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ kann nicht mehr als $t = &lfloor;d_{\rm min}/2&rfloor; = 1$ Fehler korrigieren.
+*The present Reed&ndash;Solomon&ndash;code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ cannot correct more than $t = &lfloor;d_{\rm min}/2&rfloor; = 1$ errors.
-* Da das Empfangswort gemäß der Angabe tatsächlich decodiert werden kann, gilt&nbsp; $\underline{r = 1}$.
+* Since the received word can actually be decoded according to the specification,&nbsp; $\underline{r = 1}$ holds.
 {{ML-Fuß}}

← Older revision		Revision as of 14:23, 4 September 2022
Line 117:		Line 117:


−	[[Category:Channel Coding: Exercises\|^2.5 ~~Fehlerkorrektur nach RSC~~^]]	+	[[Category:Channel Coding: Exercises\|^2.5 Reed-Solomon Error Correction^]]