Reed-Solomon im GF(79)

13.07.2016, 18:48

Nenene

Reed-Solomon im GF(79)

Meine Frage:
Im Speziellen finden sich zur Kodierung von Zeichenketten mit Hilfe des Reed-Solomon Verfahrens genügend Beispiele und Algorithmen für $\begin{eqnarray*} GF(2^{8}) \end{eqnarray*}$ .

Gegeben sei aber ein Reed-Solomon Code über $\begin{eqnarray*} GF(79) \end{eqnarray*}$ , dessen Symbole sich nicht mittels 8 bit ASCII sondern über ein Alphabet von 79 Zeichen definieren.

Sei also $\begin{eqnarray*} F_{q}=GF(p^{m}) \end{eqnarray*}$ mit p=79, m=1 ein Körper mit 79 Elementen und C ein [78,52,27]-RS-Code über $\begin{eqnarray*} F_{q}=GF(p^{m}) \end{eqnarray*}$ . Der RS-Code ist also in der Lage t=13 (mit d=2t-1) Auslöschungen zu korrigieren.

Die Elemente des Körpers F seien als Untermenge des ASCII-Zeichensatzes definiert, indiziert über die Zeichenkette

code:
1:	" abcdefghijklmnopqrstuvwxyzäöüßABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ0123456789,.:-!°'()"

Das kleinste erzeugende Element von GF(79) ist $\begin{eqnarray*} \alpha=3 \end{eqnarray*}$ , daraus und mit $\begin{eqnarray*} b=1 \end{eqnarray*}$ folgt das Generatorpolynom (mod 79)

$\begin{eqnarray*} g(x) = (x-\alpha^{b})(x-\alpha^{b+1})...(x-\alpha^{b+d-2}) = \end{eqnarray*}$
$\begin{eqnarray*} (x-\alpha)(x-\alpha^{2})...(x-\alpha^{26}) = \end{eqnarray*}$
$\begin{eqnarray*} (x-3)(x-9)(x-27)(x-2)...(x-34) = \end{eqnarray*}$

$\begin{eqnarray*} x^{26} + 46x^{25} + 50x^{24} + 59x^{23} + 76x^{22} + 22x^{21} + 13x^{20} + \end{eqnarray*}$
$\begin{eqnarray*} 47x^{19} + 35x^{18} + 70x^{17} + 13x^{16} + 4x^{15} + 78x^{14} + 26x^{13} + \end{eqnarray*}$
$\begin{eqnarray*} 10x^{12} + 5x^{11} + 35x^{10} + 60x^{9} + 16x^{8} + 56x^{7} + 30x^{6} + \end{eqnarray*}$
$\begin{eqnarray*} 21x^{5} + 43x^{4} + 30x^{3} + 39x^{2} + 52x^{1} + 78 \end{eqnarray*}$

Will ich nun einen 52-Zeichen langen Klartext kodieren, multipliziere ich zunächst das Polynom N der Nachricht mit $\begin{eqnarray*} x^{26} \end{eqnarray*}$ - verschiebe also die Koeffizienten des zugehörigen Polynoms nach links, um Platz für den Code zu machen. Daraus ergibt sich N' das ich durch das Generatorpolynom dividiere. Den Rest der Division subtrahiere ich von N' und erhalte somit die zu übermittelnde Zeichenfolge der Länge 78.

Ausgehend von einer gegebenenen fehlerfreien Nachricht

code:
1:	Willkommen bei der Light-Version des unlösbaren Ib6Me)QYpMTPuuSÄ,B8Ä:qjAMc

was ohne den RS-Code über folgendes Polynom dargestellt werden kann (Koeffizienten korrelieren mit dem Index im gegebenen Alphabet):

W=53, i=9, l=12, ...

$\begin{eqnarray*} 53x^{77} + 9x^{76} + 12x^{75} + 12x^{74} + 11x^{73} + 15x^{72} + 13x^{71} + 13x^{70} + 5x^{69} +<br /> 14x^{68} + 2x^{66} + 5x^{65} + 9x^{64} + 4x^{62} + 5x^{61} + 18x^{60} + 42x^{58} + 9x^{57} +<br /> 7x^{56} + 8x^{55} + 20x^{54} + 73x^{53} + 52x^{52} + 5x^{51} + 18x^{50} + 19x^{49} + 9x^{48}+<br /> 15x^{47} + 14x^{46} + 4x^{44} + 5x^{43} + 19x^{42} + 21x^{40} + 14x^{39} + 12x^{38} + 28x^{37} +<br /> 19x^{36} + 2x^{35} + x^{34} + 18x^{33} + 5x^{32} + 14x^{31} \end{eqnarray*}$

versuche ich nun, anhand der beschriebenen Vorgehensweise zum gleichen Ergebnis zu kommen. Ich erhalte aber

code:
1:	Willkommen bei der Light-Version des unlösbaren NnqPWQaHjGCEBI51:ocl6ödRk'

Der sich ergebende RS-Code unterscheidet sich also vom vorgegebenenen Code. Was mache ich also falsch bei der Berechnung?

Meine Ideen:
Ich könnte mir vorstellen, dass ich bei der Ermittlung der Koeffizienten des Nachrichtenpolynoms einen Denkfehler habe. Das Leerzeichen steht an erster Stelle des Alphabets und erhält also 0. Andererseits habe ich genau 79 Zeichen, deren Werte mod 79 0 bis 78 sind (und nicht 1 bis 79).

Eine andere Fehlerquelle könnte im erzeugten Generatorpolynom stecken.

Vielleicht steckt der Fehler aber in der Polynomendivision (mod 79)

Zur Polynomdivision vielleicht noch auszugsweise die erste Zeile aus N'/g(x), auch wenn es ein wenig unübersichtlich sein sollte:

53x^77 + 9x^76 + 12x^75 + 12x^74 + ... + 14x^31 : x^26 + 46x^25 + 50x^24 + ... +52x^1 + 78 = 53x^51
53x^77 + 68x^76 + 43x^75 + 46x^74 + ...
-----------------------------------------
0 + 20x^76 + 48x^75 + 45x^74 + ...

9 - 68 = 20 (mod 79)
12 - 43 = 48 (mod 79)
12 - 46 = 45 (mod 79)

So lange ich in GF(79) nicht erfolgreich einen RS-Code erzeugen kann, wage ich mich erst gar nicht an die Dekodierung fehlerhaft übermittelter Nachrichten (um das es ja eigentlich geht).

14.07.2016, 17:16

Nenene

Auf diesen Beitrag antworten »

RE: Reed-Solomon im GF(79)
Mittels einer einfachen Brute-Force-Attacke auf die einzige mir sinnvoll erscheinende Ursache des Problems konnte das Problem gelöst werden:
b=1 war als Annahme nicht wirklich fixiert und bei b=52 ergab sich die gesuchte RS-Code.

Das Generatorpolynom lautet also $\begin{eqnarray*} g(x)=(x-\alpha^{52})(x-\alpha^{53})...(x-\alpha^{77}) \end{eqnarray*}$

Neue Frage »

Antworten »

Reed-Solomon im GF(79)

Verwandte Themen