Aufgaben:Aufgabe 2.12Z: Reed–Solomon–Syndromberechnung: Unterschied zwischen den Versionen
(8 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung}} | {{quiz-Header|Buchseite=Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung}} | ||
− | [[Datei:P_ID2559__KC_T_2_5_Darstellung.png|right|frame|$\rm GF(2^3)$ | + | [[Datei:P_ID2559__KC_T_2_5_Darstellung.png|right|frame|Umrechnungstabelle für das Galoisfeld $\rm GF(2^3)$]] |
− | Wie in der [[Aufgaben: | + | Wie in der [[Aufgaben:Aufgabe_2.12:_Decodierung_beim_RSC_(7,_4,_4)_zur_Basis_8|"Aufgabe 2.12"]] betrachten wir den Reed–Solomon–Code $(7, \, 4, \, 4)_8$, der auf dem Galoisfeld ${\rm GF}(q)$ mit $q = 8 = 2^3$ basiert. Die Grafik zeigt die zugehörige Umrechnungstabelle. |
− | Gegeben sind die möglichen Codesymbole in Exponentendarstellung (Potenzen von $\alpha$ | + | Gegeben sind die möglichen Codesymbole in |
+ | # Exponentendarstellung $($Potenzen von $\alpha)$ | ||
+ | # Polynomdarstellung | ||
+ | # Koeffizientenvektordarstellung. | ||
− | |||
− | |||
− | soll überprüft werden, ob einzelne Symbole des Empfangsvektors $\underline{y}$ bei der Übertragung verfälscht wurden. Gegeben ist hierzu die Prüfmatrix $\mathbf{H}$ des betrachteten Codes und deren Transponierte: | + | Vorgegeben ist das Empfangswort $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. |
+ | *Anhand des Syndroms $\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 $\underline{y}$ bei der Übertragung verfälscht wurden. | ||
+ | |||
+ | *Gegeben ist hierzu die Prüfmatrix $\mathbf{H}$ des betrachteten Codes und deren Transponierte: | ||
:$${ \boldsymbol{\rm H}} = | :$${ \boldsymbol{\rm H}} = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Zeile 27: | Zeile 31: | ||
\end{pmatrix} \hspace{0.05cm}.$$ | \end{pmatrix} \hspace{0.05cm}.$$ | ||
− | + | ||
− | + | ||
− | + | ||
+ | Hinweis: Die Aufgabe bezieht sich auf die Seite [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| "Schritt $\rm (A)$: Auswertung des Syndroms beim BDD"]] des Kapitels "Fehlerdeccodierung nach Reed–Solomon–Codierung". | ||
+ | |||
Zeile 36: | Zeile 42: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Empfangen wurde $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Geben Sie das erste Element des Syndroms $\underline{s} = (s_0, \, s_1, \, s_2)$ an. | + | {Empfangen wurde das Wort $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Geben Sie das erste Element des Syndroms $\underline{s} = (s_0, \, s_1, \, s_2)$ an. |
|type="()"} | |type="()"} | ||
+ $s_0 = \alpha^4$, | + $s_0 = \alpha^4$, | ||
- $s_0 = \alpha^5$, | - $s_0 = \alpha^5$, | ||
- $s_0 = \alpha^6$, | - $s_0 = \alpha^6$, | ||
− | - $s_0 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. | + | - $s_0 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. |
{Wie lautet bei gleichem Empfangswort das zweite Syndromelement? | {Wie lautet bei gleichem Empfangswort das zweite Syndromelement? | ||
Zeile 48: | Zeile 54: | ||
+ $s_1 = \alpha^5$, | + $s_1 = \alpha^5$, | ||
- $s_1 = \alpha^6$, | - $s_1 = \alpha^6$, | ||
− | - $s_1 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. | + | - $s_1 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. |
{Wie lautet bei gleichem Empfangswort das dritte Syndromelement? | {Wie lautet bei gleichem Empfangswort das dritte Syndromelement? | ||
Zeile 57: | Zeile 63: | ||
- $s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. | - $s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$. | ||
− | {Bekannt ist, dass das vorliegende Empfangswort $\underline{y}$ decodiert werden kann. Wieviele Symbolfehler beinhaltet | + | {Bekannt ist, dass das vorliegende Empfangswort $\underline{y}$ richtig decodiert werden kann. Wieviele Symbolfehler beinhaltet dieses Empfangswort? |
|type="{}"} | |type="{}"} | ||
$r \ = \ ${ 1 3% } | $r \ = \ ${ 1 3% } | ||
Zeile 64: | Zeile 70: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | + | [[Datei:P_ID2560__KC_T_2_5_Darstellung.png|right|frame|Umrechnungstabellen für das Galoisfeld $\rm GF(2^3)$]] | |
− | :$$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) = | + | '''(1)''' Die entsprechende Gleichung zur Syndromberechnung lautet: |
− | + | :$$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) = | |
\begin{pmatrix} | \begin{pmatrix} | ||
\alpha,0, \alpha^3,0, 1, \alpha,0 | \alpha,0, \alpha^3,0, 1, \alpha,0 | ||
Zeile 81: | Zeile 87: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | Das erste Element ergibt sich zu | + | *Das erste Element ergibt sich zu |
:$$s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^2 + 1 \cdot \alpha^4 + \alpha \cdot \alpha^5= | :$$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 | + | \alpha + \alpha^5 + \alpha^4+ \alpha^6$$ |
− | :$$\ = \ \hspace{-0.15cm} (\alpha) + (\alpha^2 + \alpha+ 1)+ (\alpha^2 + \alpha) + + (\alpha^2 + 1) = \alpha^2 + \alpha = \alpha^4 | + | :$$\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>. | + | *Richtig ist der <u>Lösungsvorschlag 1</u>. |
− | '''(2)''' Entsprechend gilt für das zweite Syndromelement | + | '''(2)''' Entsprechend gilt für das zweite Syndromelement entsprechend dem <u>Lösungsvorschlag 2</u>: |
:$$s_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^4 + 1 \cdot \alpha^1 + \alpha \cdot \alpha^3= | :$$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= | + | \alpha + \alpha^7 + \alpha+ \alpha^4= 1 + \alpha^4 = \alpha^2 + \alpha + 1 = \alpha^5 |
− | |||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | |||
− | |||
− | '''(3)''' Zur Berechnung von $s_2$ muss mit der letzten Matrixspalte multipliziert werden: | + | '''(3)''' Zur Berechnung von $s_2$ muss das Empfangswort mit der letzten Matrixspalte multipliziert werden: |
:$$s_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^6 + 1 \cdot \alpha^5 + \alpha \cdot \alpha^1= | :$$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 + \alpha^2 + \alpha^5 + \alpha^2=\alpha^5 + \alpha = (\alpha^2 + \alpha + 1) + \alpha = \alpha^2 + 1 = \alpha^5 |
− | |||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | + | *Richtig ist der <u>Lösungsvorschlag 3</u>. | |
+ | |||
+ | |||
+ | '''(4)''' Aufgrund des errechneten Syndroms $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) ≠ 0$ beinhaltet das Empfangswort mindestens einen Symbolfehler ⇒ $r > 0$. | ||
+ | *Der vorliegende Reed–Solomon–Code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ kann nicht mehr als $t = ⌊d_{\rm min}/2⌋ = 1$ Fehler korrigieren. | ||
+ | * Da das Empfangswort gemäß Angabe tatsächlich decodiert werden kann, gilt $\underline{r = 1}$. | ||
− | + | *Ohne diese Angabe "das Empfangswort kann decodiert werden" wäre diese Teilaufgabe nicht lösbar. | |
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category:Aufgaben zu Kanalcodierung|^2.5 Fehlerkorrektur nach | + | [[Category:Aufgaben zu Kanalcodierung|^2.5 Fehlerkorrektur nach RSC^]] |
Aktuelle Version vom 30. Oktober 2022, 17:16 Uhr
Wie in der "Aufgabe 2.12" betrachten wir den Reed–Solomon–Code $(7, \, 4, \, 4)_8$, der auf dem Galoisfeld ${\rm GF}(q)$ mit $q = 8 = 2^3$ basiert. Die Grafik zeigt die zugehörige Umrechnungstabelle.
Gegeben sind die möglichen Codesymbole in
- Exponentendarstellung $($Potenzen von $\alpha)$
- Polynomdarstellung
- Koeffizientenvektordarstellung.
Vorgegeben ist das Empfangswort $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$.
- Anhand des Syndroms $\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 $\underline{y}$ bei der Übertragung verfälscht wurden.
- Gegeben ist hierzu die Prüfmatrix $\mathbf{H}$ des betrachteten Codes und deren Transponierte:
- $${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 & \alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ 1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4} \end{pmatrix} \hspace{0.05cm},\hspace{0.4cm} { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 & 1 & 1 \\ \alpha^1 & \alpha^2 & \alpha^3 \\ \alpha^2 & \alpha^4 & \alpha^6 \\ \alpha^3 & \alpha^6 & \alpha^2 \\ \alpha^4 & \alpha^1 & \alpha^{5} \\ \alpha^5 & \alpha^{3} & \alpha^{1} \\ \alpha^6 & \alpha^{5} & \alpha^{4} \end{pmatrix} \hspace{0.05cm}.$$
Hinweis: Die Aufgabe bezieht sich auf die Seite "Schritt $\rm (A)$: Auswertung des Syndroms beim BDD" des Kapitels "Fehlerdeccodierung nach Reed–Solomon–Codierung".
Fragebogen
Musterlösung
(1) Die entsprechende Gleichung zur Syndromberechnung lautet:
- $$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) = \begin{pmatrix} \alpha,0, \alpha^3,0, 1, \alpha,0 \end{pmatrix}\cdot \begin{pmatrix} 1 & 1 & 1 \\ \alpha^1 & \alpha^2 & \alpha^3 \\ \alpha^2 & \alpha^4 & \alpha^6 \\ \alpha^3 & \alpha^6 & \alpha^2 \\ \alpha^4 & \alpha^1 & \alpha^{5} \\ \alpha^5 & \alpha^{3} & \alpha^{1} \\ \alpha^6 & \alpha^{5} & \alpha^{4} \end{pmatrix} \hspace{0.05cm}.$$
- Das erste Element ergibt sich zu
- $$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 Lösungsvorschlag 1.
(2) Entsprechend gilt für das zweite Syndromelement entsprechend dem Lösungsvorschlag 2:
- $$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 \hspace{0.05cm}.$$
(3) Zur Berechnung von $s_2$ muss das Empfangswort mit der letzten Matrixspalte multipliziert werden:
- $$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 Lösungsvorschlag 3.
(4) Aufgrund des errechneten Syndroms $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) ≠ 0$ beinhaltet das Empfangswort mindestens einen Symbolfehler ⇒ $r > 0$.
- Der vorliegende Reed–Solomon–Code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ kann nicht mehr als $t = ⌊d_{\rm min}/2⌋ = 1$ Fehler korrigieren.
- Da das Empfangswort gemäß Angabe tatsächlich decodiert werden kann, gilt $\underline{r = 1}$.
- Ohne diese Angabe "das Empfangswort kann decodiert werden" wäre diese Teilaufgabe nicht lösbar.