Ich nehme hier an, dass man sich vorab eine Beschreibung des Verfahrens angesehen hat ...
z.B bei Wikipedia ... Reed-Solomon-Code
Wenn man also die Grundzüge kennt, kann man das Verfahren mit den folgenden Seiten spielerisch und interaktiv ausprobieren.
Die beiden Rechenarten:
zu Addition: Es gilt hier .... a - b = a + b = a XOR b
und die Multiplikation ist auch gewöhnungsbedürftig!
QR-Code Rechenarten
Das Reed-Solomon-Verfahren ... Hier kann man es ausprobieren:
Reed-Solomon ... Kodierung
Reed-Solomon ... Dekodierung
ich verwende hier: 85 108 109 224 168 88 3 ...
z. Tl. als Kurzschreibweise von 85·x^6 + 108·x^5 + 109·x^4 + 224·x^3 + 168·x^2 + 88·x + 3
mit x^n für x hoch n
Bei den Polynomen wird immer vom linearen Term aus (0. Stelle) gezählt: also von rechts!
Beispiele A + B
mit der Ursprungsnachricht: UlmUlm mit ASCII-Zeichen: 85 108 109
es sollen nun 4 ECC-Bytes (ECC: Error Correcting Code) hinzugefügt werden
k=4
t=2 (soviele Bytes können maximal repariert werden)
man verwendet das Generatorpolynom G(x) = G(x) = (x+2^0)·(x+2^1)·(x+2^2)· .... ·(x+2^(k-1))
hier: G(x) = (x+1)·(x+2)·(x+4)·(x+8)
Dazu wird das Polynom U(x) = 85·x^6 + 108·x^5 + 109·x^4 + 0·x^3 + 0·x^2 + 0·x + 0 durch G(x) geteilt und der entstandene REST 224·x^3 + 239·x^2 + 88·x + 3
wird an 85·x^6 + 108·x^5 + 109·x^4 angefügt.
--> Das Polynom P(x) = 85·x^6 + 108·x^5 + 109·x^4 + 224·x^3 + 239·x^2 + 88·x + 3
hat also sicher bei x=1, 2, 4 und 8 Nullstellen! P(1) = P(2) = P(4) = P(8) = 0
Nun haben sich Fehler eingeschlichen ...
Wir können das daran erkennen, dass P(1), P(2), P(4) und P(8) ungleich Null sind!
A) Wir nehmen an, es handelt sich um 1 Fehler:
wie bei diesem empfangenen Polynom:
E(x) = 85 108 109 224 168 88 3 ...
Kurzschreibweise von 85x^6 + 108x^5 + 109x^4 + 224x^3 + 168x^2 + 88x + 3
Syndromwerteberechnung: bei 4 ECC-Bytes
E(2^0) = E(1) = 71
E(2^1) = E(2) = 1
E(2^2) = E(4) = 4
E(2^3) = E(8) = 16
Wir können E(x) darstellen mit E(x) = P(x) + F(x);
F(x) ist das Fehlerpolynom: F(x) = f·x^k (an EINER Stelle (?k) steht ein falscher Wert (?f))
E(2^0) = E(1) = P(1) + F(1) = 0 + F(1) ... s.o.
Also ist für die Syndromwerte nur F(x) "verantwortlich"!
f·1^k = 71 --> f = 71 weil 1^k = 1 ist
f·2^k = 1 --> 71·2^k = 1 --> 2^k = 1 · 71^(-1) = 1·4 = 4; --> k = log(4) = 2
71·4^2 = 4 wird bestätigt
71·8^2 = 16 wird bestätigt
An der x^2-Stelle steht also fälschlicherweise 71 zuviel. Also muss man zu 168 noch 71 subtrahieren bzw. addieren .. mit 168 XOR 71
168 - 71 = 168 + 71 = 168 XOR 71 = 239 (der richtige Wert).
Die richtige Folge lautet also 85 108 109 224 239 88 3
B) Wir nehmen an, es handelt sich um 2 Fehler (Maximalzahl bei 4 ECC-Bytes!):
wie bei diesem empfangenen Polynom: E(x) = 85 108 211 224 168 88 3... Kurzschreibweise s.o.
Syndromwerteberechnung: bei 4 ECC-Bytes
E(2^0) = E(1) = 249 = s_0
E(2^1) = E(2) = 46 = s_1
E(2^2) = E(4) = 206 = s_2
E(2^3) = E(8) = 44 = s_3
E(x) = P(x) + F(x);
Nur F(x) sorgt für die Zahl ungleich Null!
F(x) ist das Fehlerpolynom: F(x) = f1·x^j + f2·x^k (an ZWEI Stellen (? j, k) stehen zwei "falsche" Werte (? f1, f2) - sie sollten eigentlich Null sein)
hier: wäre j=2, k=4
(wie bei Beispiel A ... Syndromwerte durch F(x) ... Gleichungssystem X)
f1·1^j + f2·1^k = 249
f1·2^j + f2·2^k = 46
f1·4^j + f2·4^k = 206
f1·8^j + f2·8^k = 44
Man definiert nun ein Fehlerortungspolynom σ(x) = (1-x·2^j)·(1-x·2^k) = 1 - x·(2^j+2^k) + (x^2)·2^(j+k)
σ0 = 1; σ1 = 2^j+2^k ; σ2 = 2^(j+k)
Von σ(x) wissen wir: σ(2^(-j)) = 0 und σ(2^(-k)) = 0
ABER: Eigentlich kennen wir j und k leider NICHT!!
Es gilt nun aber interessanterweise: (!!!)
(Ein schöner allgemeiner(!) Beweis befindet sich im Buch von Volker Coors / Bernhard Lenk, Seite 51 - siehe Impressum, Tipps)
s_2 = σ1·s_1 + σ2·s_0
s_3 = σ1·s_2 + σ2·s_1
Beweis dazu
hier:
206 = σ1·46 + σ2·249
44 = σ1·206 + σ2·46
Das Lineare Gleichungssystem (LGS) in "normaler" Schreibweise
46·σ1 + 249·σ2 = 206
206·σ1 + 46·σ2 = 44
Wir bringen das LGS auf Dreiecksform:
1·σ1 + 107·σ2 = 203
0·σ1 + 49·σ2 = 220
Hier würde man auch erkennen, ob es sich um einen oder zwei (hier das Myximum!) Fehler handelt. Wenn es NUR EIN Fehler wäre würde die 2. Gleichung 0·σ1 + 0·σ2 = 0 lauten.
Dann könnte man bei A weitermachen ...
oder siehe Beispiel C mit einem Fehler - aber dem Ansatz für 2 vermutete Fehler
Aus der unteren Gleichung ergibt sich ... σ2 = 220·49^(-1) = 64
Damit und mit der oberen Gleichung erhält man ... σ1 = 203 - 107·64 = 203 + 107·64 = 203 + 223 = 20
Jetzt müssen wir "nur" noch nachschauen, wo unser σ(x) = 1 + 20x + 64x^2 Null wird,
wenn wir die Inversen von 1, 2, 4, 8, 16, 32 , 64 (Stelle 0 bis Stelle 6) einsetzen:
σ(2^(-0)) = σ(1) = 1 + 20 + 64 = 85
σ(2^(-1)) = σ(142) = 1 + 20·142 + 64·142·142 = 1 + 10 + 16 = 27
σ(2^(-2)) = σ(71) = 1 + 20·71 + 64·71·71 = 0; NULL --------------> j = 2 gefunden !!!
σ(2^(-3)) = σ(173) = ... = 140
σ(2^(-4)) = σ(216) = ... = 0; NULL --------------> k = 4 gefunden !!!
σ(2^(-5)) = σ(108) = ... = 250
σ(2^(-6)) = σ(54) = ... = 168
Fehlerwertbestimmung: f1 und f2 (s.o.)
hier nochmals das Gleichungssystem X von oben:
f1·1^j + f2·1^k = 249
f1·2^j + f2·2^k = 46
f1·4^j + f2·4^k = 206
f1·8^j + f2·8^k = 44
Aber: j und k kennen wir schon:
f1·1^2 + f2·1^4 = 249 = 249 --> f1 + f2 = 249 --> 4f1 + 4f2 = 4·249 = 195
f1·2^2 + f2·2^4 = 46 --> 4f1 + 16f2 = 46 --> 20f2 =195 + 46 = 237 ==> f2 = 237 · 20((-1) = 190
damit ergibt sich f1 = 249 + f2 = 249 + 190 = 71
f1·4^2 + f2·4^4 = 206 ... brauchen wir nicht mehr!
f1·8^2 + f2·8^4 = 44 ... brauchen wir nicht mehr!
Die richtigen Werte wären also
an (j) 2.Stelle = 168 + 71 = 239
an (k) 4.Stelle = 211 + 190 = 109
Die richtige Folge ist also 85 108 109 224 239 88 3
Beispiel C
mit der Ursprungsnachricht: "Bahnhof""Bahnhof" mit ASCII-Zeichen: 66 97 104 110 104 111 102
es werden nun 8 ECC-Bytes hinzugefügt
Anzahl der ECC-Bytes: k=8
Maximale Anzahl an Fehlern: t=4
man verwendet das Generatorpolynom G(x) = (x+2^0)·(x+2^1)·(x+2^2)· .... ·(x+2^(k-1))
hier: (x+1)·(x+2)·(x+4)·(x+8)·(x+16)·(x+32)·(x+64)·(x+128)
Dazu wird das Polynom U(x) = 66 97 104 110 104 111 102 0 0 0 0 0 0 0 0 durch G(x) geteilt und der entstandene REST (46 48 46 199 112 192 79 76) wird an 66 97 104 110 104 111 102 angefügt.
--> 66 97 104 110 104 111 102 46 48 46 199 112 192 79 76
Das Polynom P(x) = 66x^14 + 97x^13 + 110x^12 + 104x^11 + .... 79x + 76 hat also sicher bei x=1, 2, 4, 8, 16, 32, 64 und 128 Nullstellen! P(1) = P(2) = P(4) = P(8) = P(16) = P(32) = P(64) = P(128) = 0
Nun haben sich Fehler eingeschlichen ...
Wir können das daran erkennen, dass P(1), P(2), P(4) ... bis P(128) ungleich Null sind!
Empfang von 66 97 104 110 104 111 102 46 48 146 199 112 192 79 76
Syndromberechnung: bei 8 ECC-Bytes
P(2^0) = P(1) = 188 = s_0
P(2^1) = P(2) = 30 = s_1
P(2^2) = P(4) = 231 = s_2
P(2^3) = P(8) = 177 = s_3
P(2^4) = P(16) = 163 = s_4
P(2^5) = P(32) = 217 = s_5
P(2^6) = P(64) = 34 = s_6
P(2^7) = P(128) = 52 = s_7
Alle ungleich NULL: Es gibt Fehler! Man weiß noch nicht wieviele Fehler es sind!
Man definiert auch hier ein Fehlerortungspolynom (die Fehlerstellen lägen bei j,k,m und n)
σ(x) = (1-x·2^j)·(1-x·2^k)·(1-x·2^m)·(1-x·2^n) =
(1 - x·(2^j+2^k) + (x^2)·2^(j+k))·(1 - x·(2^m+2^n) + (x^2)·2^(m+n)) =
1 - x·(2^j+2^k) + (x^2)·2^(j+k) - x·(2^m+2^n) + (x^2)·(2^j+2^k)·(2^m+2^n) - (x^3)·2^(j+k)·(2^m+2^n)+ (x^2)·2^(m+n) - (x^3)·2^(m+n)·(2^j+2^k) + (x^4)·2^(j+k)·2^(m+n) =
1 - x·(2^j+2^k+2^m+2^n) + (x^2)·(2^(j+k)+(2^j+2^k)·(2^m+2^n)+2^(m+n)) - (x^3)·(2^(j+k)·(2^m+2^n) + 2^(m+n)·(2^j+2^k)) + (x^4)·2^(j+k)·2^(m+n)
mit
σ0 = 1
σ1 = 2^j+2^k+2^m+2^n
σ2 = 2^(j+k)+(2^j+2^k)·(2^m+2^n)+2^(m+n)
σ3 = 2^(j+k)·(2^m+2^n) + 2^(m+n)·(2^j+2^k)
σ4 = 2^(j+k+m+n)
Auch hier gilt:
s_4 = σ1·s_3 + σ2·s_2 + σ3·s_1 + σ4·s_0;
s_5 = σ1·s_4 + σ2·s_3 + σ3·s_2 + σ4·s_1;
s_6 = σ1·s_5 + σ2·s_4 + σ3·s_3 + σ4·s_2;
s_7 = σ1·s_6 + σ2·s_5 + σ3·s_4 + σ4·s_3;
Beweis zu s_4 = .... für BenutzerInnen des Firefox-Browsers und Safari-Browsers (MathML-Verwendung!)
(Einen allgemeinen(!) Beweis findet Ihr im Buch von Volker Coors / Bernhard Lenk, Seite 51 - siehe Impressum, Tipps)
163 = 177σ1 + 231σ2 + 30σ3 + 188σ4
217 = 163σ1 + 177σ2 + 231σ3 + 30σ4
34 = 217σ1 + 163σ2 + 177σ3 + 231σ4
52 = 34σ1 + 217σ2 + 163σ3 + 177σ4
"normal" schreiben; auf Dreiecksform bringen ...
177 213 30 188 163
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Das heißt, die Gleichungen sind voneinander abhängig .. es gibt nur EINE Fehlerstelle!
Das heißt aber man benötigt auch nur das Fehlerortungspolynom (1-x·2^j) !!
mit der Beziehung:
s_1 = σ1·s_0
30 = σ1 · 188; ---> σ1 = 32; ---> 2^j=32 --> j=5;
oder:
mit dem Fehlerortungspolynom σ(x) = 1 + 32x;
und dem Test mit allen Stellen:
σ(2^(-0)) = σ(1) = 1 + 32 = 33 <> 0
σ(2^(-1)) = σ(142) = 1 + 32·142 = 1 + 16 = 17 <> 0
σ(2^(-2)) = σ(71) = 1 + 32·71 = 1 + 8 = 9 <> 0
σ(2^(-3)) = σ(173) = 1 + 32·173 = 1 + 4 = 5 <> 0
σ(2^(-4)) = σ(216) = 1 + 32·216 = 1 + 2 = 3 <> 0
σ(2^(-5)) = σ(108) = 1 + 32·108 = 1 + 1 = 0 -------------> Stelle 5 gefunden
σ(2^(-6)) = σ(54) = 1 + 32·54 = 1 + 142 = 143 <> 0
.. <> 0
.. <> 0
σ(2^(-14)) = σ(88) = 1 + 32·88 = 1 + 207 = 206 <> 0
Fehlerwert betimmen:
f1·1^5 = 188 --> f1 = 188 --> korrigierte Stelle 5: 188 + 146 = 46
richtig ist also 66 97 104 110 104 111 102 46 48 46 199 112 192 79 76