Reed-Solomon Code

Maple 7 Worksheet PostScript

---

Reed-Solomon Code

Michal Mnuk (mnuk@in.)

Parameter s=3, t=1, d.h. 2 Fehler (max. 6 bits) erkennen und 1 Fehler (max. 3 Bits) korrigieren.

> ### WARNING: persistent store makes one-argument readlib obsolete
readlib(GF):

> p := x^3+x+1: K := GF(2,3,p):

> evalGF := proc (expr)
sort(collect(expand(Rem(expr, p, x) mod 2), z), [z,x]) end:

> K[isPrimitiveElement](K[ConvertIn](x));

Nachricht: 7, 6, 1, 5, 0

> m := [[1,1,1],[1,1,0],[0,0,1],[1,0,1], [0,0,0]];

> mGF := [x^2+x+1, x^2+x, 1, x^2+1, 0];

> g := z -> Rem((z-x)*(z-x^2), p, x) mod 2;

> sort(collect(expand(g(z)),z),[z,x]);

Codierung

> c :=collect(expand(Rem(g(z)*add(mGF[i]*z^(5-i), i=1..5), p, x) mod 2), z);

> evalGF(subs(z=x, c));

> evalGF(subs(z=x^2, c));

W鋒rend der 躡ertragung sind 2 Fehler passiert (x+1 -> x bei z^6, 0 -> 1 bei z^2).

> c;

> ce := evalGF(c+(z^6+z^2));

Durch Auswertung an den Stellen x und x^2 wird der Fehler erkannt.

> evalGF(subs(z=x, ce));
evalGF(subs(z=x^2, ce));

Ein anderes Codewort, das sich an 3(!) Stellen von c unterscheidet.

> evalGF(c+g(z));

> c;

> evalGF(subs(z=x, c+g(z)));
evalGF(subs(z=x^2, c+g(z)));

Falls h鯿hstens 1 Fehler passiert ist, kann das gesendete Wort hergestellt werden.

Wort mit Fehlern empfangen.

> ce1 := evalGF(c+(x^2+x)*z^2);

> c;

Wir bestimmen zun鋍hst die Restklasse vom empfangenen Wort mod g(z)

> e := evalGF(Rem(ce1, g(z), z) mod 2);

... und bestimmen denjenigen Repr鋝entanten dieser Restklasse, der die kleinste Anzahl

der von Null verschiedenen Koeffizienten hat.

> evalGF(e);

> evalGF(e+(x^2+x)*g(z));

Dieses Element wird zum empfangenen Wort addiert. Das Ergebnis ist das gesendete Wort.

> evalGF(ce1+e+(x^2+x)*g(z));

> c;

Decodierung

Teilen durch g(z)

> evalGF(Quo(c,g(z), z) mod 2);

Die urspr黱gliche Nachricht wird aus den Koeffizienten bei Potenzen von abgelesen:

Koeffizient bei : +x+1 -> 1,1,1 (bin鋜)-> 7 (dezimal)

Koeffizient bei : +x -> 1,1,0 -> 6

Koeffizient bei : 1

Koeffizient bei : -> 1,0,1 -> 5

Koeffizient bei : 0

=> Nachricht: 7, 6, 1, 5, 0