QR-Code ... zum RS-Verfahren - Beispiel C - Beweis

zur Themenübersicht

Leider funktioniert diese Seite nur(?) mit dem Firefox- und dem Safari-Browser problemlos!

Probleme bei der Darstellung? ... Darstellung als PNG-Bild


Beispiel C - Fehlerortung:

Man definiert auch hier ein Fehlerortungspolynom (die Fehlerstellen lägen bei den Stellen j,k,m und n)
σ(x) = $(1-\mathrm{x}·2^{\mathrm{j}})·(1-\mathrm{x}·2^{\mathrm{k}})·(1-\mathrm{x}·2^{\mathrm{m}})·(1-\mathrm{x}·2^{\mathrm{m}})={\sigma }_0+{\sigma }_1·x+{\sigma }_2·x^2+{\sigma }_3·x^3+{\sigma }_4·x^4$

wichtig wird weiter unten ...

$\sigma \left(2^{\mathrm{-j}}\right)=\sigma \left(2^{\mathrm{-k}}\right)=\sigma \left(2^{\mathrm{-m}}\right)=\sigma \left(2^{\mathrm{-n}}\right)=0$

komplettes Ausmultiplizieren führt dann zu (die Terme ab ${\sigma }_1$ sind hier aber nicht weiter wichtig!):

${\sigma }_0=1$
${\sigma }_1=-\left(2^j+2^k+2^m+2^n\right)$
${\sigma }_2=2^{\mathrm{j+k}}+\left(2^j+2^k\right)·\left(2^m+2^n\right)+2^{\mathrm{m+n}}$
${\sigma }_3=-2^{\mathrm{j+k}}·\left(2^m+2^n\right)-2^{\mathrm{m+n}}·\left(2^j+2^k\right)$
${\sigma }_4=2^{\mathrm{j+k+m+n}}$

Für die Syndromwerte gilt:
$s_i=f_j·{\left(2^i\right)}^j+f_k·{\left(2^i\right)}^k+f_m·{\left(2^i\right)}^m+f_n·{\left(2^i\right)}^n$

Beweis von:
$s_4={\sigma }_1·s_3+{\sigma }_2·s_2+{\sigma }_3·s_1+{\sigma }_4·s_0$

oder ... mit der Fehlerstellenmenge M = { j, k, m, n }

$$\sum _{i=1}^4({\sigma }_i·s_{\mathrm{4-i}})=\sum _{i=1}^4({\sigma }_i·\sum _{l\in M}\left(f_l·2^{\mathrm{(4-i)·l}}\right))=\sum _{i=1}^4\left(\sum _{l\in M}({\sigma }_i·f_l·2^{\mathrm{(4-i)·l}}\right))$$
Alle i,l-Kombinationen jetzt in anderer Reihenfolge:
$$=\sum _{l\in M}\left(\sum _{i=1}^4({\sigma }_i·f_l·2^{\mathrm{(4-i)·l}})\right)=\sum _{l\in M}\left(\sum _{i=1}^4(f_l·2^{\mathrm{4·l}}·{\sigma }_i·2^{\mathrm{-i·l}}\right))$$

Ausklammern der von i unabhängigen Werte:
$$=\sum _{l\in M}(f_l·2^{\mathrm{4·l}}·\sum _{i=1}^4({\sigma }_i·2^{\mathrm{-i·l}}))=\sum _{l\in M}(f_l·2^{\mathrm{4·l}}·\sum _{i=1}^4({\sigma }_i·(2^{\mathrm{-l}}{)}^i))=A$$
Teilbetrachtung der inneren Summe für i=1 bis 4 und für alle $l$ -Werte:

$${\sigma }_1·x+{\sigma }_2·x^2+{\sigma }_3·x^3+{\sigma }_4·x^{4}mitx=2^{\mathrm{-l}}==>\sigma \left(2^{\mathrm{-l}}\right)-{\sigma }_0=0-1=1$$
Damit ergibt sich für A:

$$A\; =\sum _{l\in M}(f_l·(2^4{)}^l)=s_4$$

... und das war zu zeigen!

Ich erinnere nochmals an den (allgemeineren) Beweis in dem Buch "Reed Solomon Fehlerkorrektur" von Volker Coors und Bernhard Lenk.

Themenübersicht

Daten - Verarbeitung