Exercise 2.12Z: Reed-Solomon Syndrome Calculation

• Return to book

$\rm GF(2^3)$ –Umrechnungstabellen

Wie in der Aufgabe A2.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$) sowie in Polynom– und Koeffizientendarstellung.

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}.$$

Hinweise:

• Die Aufgabe bezieht auf die Seite 4 des Kapitels Fehlercodierung nach Reed–Solomon–Codierung.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

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.

	$s_0 = \alpha^4$,
	$s_0 = \alpha^5$,
	$s_0 = \alpha^6$,
	$s_0 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.

2

Wie lautet bei gleichem Empfangswort das zweite Syndromelement?

	$s_1 = \alpha^4$,
	$s_1 = \alpha^5$,
	$s_1 = \alpha^6$,
	$s_1 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.

3

Wie lautet bei gleichem Empfangswort das dritte Syndromelement?

	$s_2 = \alpha^4$,
	$s_2 = \alpha^5$,
	$s_2 = \alpha^6$,
	$s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.

4

Bekannt ist, dass das vorliegende Empfangswort $\underline{y}$ decodiert werden kann. Wieviele Symbolfehler beinhaltet das Empfangswort?

$r \ = \ $

Musterlösung

Solution

(1)  [[File:P_ID2560__KC_T_2_5_Darstellung.png|right|frame|$\rm GF(2^3)–Umrechnungstabellen]] Die entsprechende Gleichung zur Syndromberechnung lautet: :'"`UNIQ-MathJax23-QINU`"' :'"`UNIQ-MathJax24-QINU`"' Das erste Element ergibt sich zu :'"`UNIQ-MathJax25-QINU`"' :'"`UNIQ-MathJax26-QINU`"' Richtig ist der <u>Lösungsvorschlag 1</u>. '''(2)'''  Entsprechend gilt für das zweite Syndromelement :'"`UNIQ-MathJax27-QINU`"' :'"`UNIQ-MathJax28-QINU`"' Richtig ist der <u>Lösungsvorschlag 2</u>. '''(3)'''  Zur Berechnung von $s_2$ muss mit der letzten Matrixspalte multipliziert werden: :'"`UNIQ-MathJax29-QINU`"' :'"`UNIQ-MathJax30-QINU`"' ⇒  <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$. Da der vorliegende Reed–Solomon–Code $(7, \, 4, \, 4)_8$ \ \Rightarrow \ d_{\rm min} = 4$ auch nicht mehr als $t = ⌊d_{\rm min}/2⌋ = 1$ Fehler korrigieren kann und das Empfangswort vereinbarungsgemäß ebenfalls decodiert werden kann, gilt $\underline{r = 1}$.