Fehlerkorrektur mittels Reed Solomon Code, Term evaluiert zu 0

23.07.2012, 21:27

Psi

Fehlerkorrektur mittels Reed Solomon Code, Term evaluiert zu 0

Meine Frage:
Grüße,

ich hab mich mal ein wenig mit Fehlerkorrektur mittels Reed Solomon Codes befasst und bin dabei auf ein Verständnisproblem gestoßen. Ich bin mir nicht sicher, ob das besser hier her gehört oder doch zur Zahlentheorie oder Numerik, meine Kernfrage befasst sich aber hauptsächlich mit dem algebraischen Aspekt des Codes, nämlich der Polynomdivision. Ich habe hierzu auch einen Calculator im Netz gefunden, die Seite beschreibt außerdem recht anschaulich die Systematik hinter der ganzen Geschichte: http://www.pclviewer.com/rs2/galois.html

Gegeben sei ein Galoisfeld $\begin{eqnarray*} GF(2^8) \end{eqnarray*}$ sowie ein zugehöriges Polynom $\begin{eqnarray*} pp = x^8 + x^4 + x^3 + x^2 + 1 \end{eqnarray*}$ (= 283).

Hierüber seien zwei Eingabefolgen zu codieren, die sich in genau einem Bit unterscheiden:

$\begin{eqnarray*} B_1: (64, 86, 22, 22, 22, 22, 18, 2, 251, 175, 117, 90, 2, 176, 176, 176, 1) \end{eqnarray*}$

sowie

$\begin{eqnarray*} B_2: (64, 86, 22, 22, 22, 22, 18, 2, 251, 175, 117, 90, 2, 176, 176, 177, 1) \end{eqnarray*}$

Das Ganze schreibt sich dann als Polynom in etwa so:

$\begin{eqnarray*} P_1: 64x^{26} + 86x^{25} + 22x^{24} + ... + 176x^{11} + x^{10} \end{eqnarray*}$
$\begin{eqnarray*} P_1: 64x^{26} + 86x^{25} + 22x^{24} + ... + 177x^{11} + x^{10} \end{eqnarray*}$

Für das GF wurde ein primitives Element $\begin{eqnarray*} \alpha = 2 \end{eqnarray*}$ definiert. Hierzu wurden zwei Tabellen, wie in http://www.pclviewer.com/rs2/galois.html beschrieben, angelegt: Die Logarithmus und die Antilogarithmustabelle.

Durch Substitution lässt sich jetzt jedem der Koeffizienten aus $\begin{eqnarray*} P_{1/2} \end{eqnarray*}$ ein Exponent von $\begin{eqnarray*} \alpha \end{eqnarray*}$ zuordnen.

So ist beispielsweise $\begin{eqnarray*} 64 = \alpha^6 \end{eqnarray*}$ .

Es wird ein festgelegtes Generatorpolynom verwendet, auf das ich auch keinen Einfluss habe, das da lautet:
$\begin{eqnarray*} x^{10} + \alpha^{251}x^9 + \alpha^{67}x^8 + \alpha^{46}x^7 + \alpha^{61}x^6 + \alpha^{118}x^5 + \alpha^{70}x^4 + \alpha^{64}x^3 + \alpha^{94}x^2 + \alpha^{32}x + \alpha^{45} \end{eqnarray*}$

Um jetzt nicht die riesigen Polynomketten hier hinzuschreiben, hab ich das Ganze durch den auf besagter Seite befindlichen Calculator laufen lassen, der einem auch schön die Zwischenschritte mit ausspuckt:

http://www.pclviewer.com/cgi/rtmrc.exe?g...2,176,176,176,1
und
http://www.pclviewer.com/cgi/rtmrc.exe?g...2,176,176,177,1

Vereinfacht gesagt wird die zurgrunde liegende Polynomdivision algorithmisch folgendermaßen ausgeführt:

Die Multiplikation der einzelnen Glieder wird über die Addition der Exponenten von $\begin{eqnarray*} \alpha \end{eqnarray*}$ gebildet, hierzu wird:

1. der Koeffizient des höchsten Gliedes in einen Exponenten von $\begin{eqnarray*} \alpha \end{eqnarray*}$ umgewandelt
2. die Exponenten addiert

Im zweiten Schritt wird das Ergebnis dann auf das jeweilige Glied einer Kette summiert (in Galoisfeld-Arithmetik heißt das: Verknüpfung mittels exklusivem Oder) und anschließend der Antilogarithmus des Ergebnisses als Zwischenschritt der Polynomdivision an der Stelle zurückbehalten.

Wie man in den Einzelschritten des oben verlinkten Calculator-Outputs sehen kann, funktioniert das auch immer ganz gut, bis man an die vorletzte Division gerät. Während bei $\begin{eqnarray*} B_2 \end{eqnarray*}$ alles seinen gewohnten Gang geht und die Division glatt möglich ist, trifft man bei $\begin{eqnarray*} B_1 \end{eqnarray*}$ auf eine Besonderheit: Es tritt ein Nullwert auf. Der hieraus zu ziehende Logarithmus ist in unserer Tabelle nicht definiert.

Meine Frage an dieser Stelle: Wie verhält sich der Algorithmus in einem solchen Fall korrekterweise?

Offensichtlich ist auch dieser Calculator fehlerhaft, denn wenn man sich den Output des Algorithmus für die beiden Eingabeworte anschaut, so sieht man, dass beide Eingabefolgen zum gleichen Wert für die Fehlerkorrektur führen, was aber vermutlich darauf zurückzuführen ist, dass der Algorithmus auf Stabilität hin optimiert wurde und für den Logarithmus von 0 mit 0 weiterrechnet. Genaugenommen müsste der Code für die Eingabefolge $\begin{eqnarray*} B_1 \end{eqnarray*}$ versagen, aber kann das sein? Was ist für so einen Fall vorgesehen?

An der Stelle lohnt es sich vielleicht zu erwähnen, dass der generierte Korrekturcode beim Decodieren natürlich $\begin{eqnarray*} B_1 \end{eqnarray*}$ als Bitfehler erkennt und zu $\begin{eqnarray*} B_2 \end{eqnarray*}$ korrigiert.

24.07.2012, 01:27

frank09

Auf diesen Beitrag antworten »

RE: Fehlerkorrektur mittels Reed Solomon Code, Term evaluiert zu 0

Zitat:

Es tritt ein Nullwert auf. Der hieraus zu ziehende Logarithmus ist in unserer Tabelle nicht definiert.

Wenn du dir die erste rot markierte Spalte anschaust, dann gilt:
$\begin{eqnarray*} LOG(0)=0 \end{eqnarray*}$

24.07.2012, 13:21

Psi

Auf diesen Beitrag antworten »

Das stimmt, es geht hier aber um den LOGARITHMUS, und da gibt es für 0 eben keinen passenden Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ von $\begin{eqnarray*} \alpha^n \end{eqnarray*}$ .

Und ich mein, es ist doch eine Tatsache, dass bei beiden Eingabefolgen dasselbe Ergebnis rauskommt, was de facto nicht sein darf, daher ist die Rückwärtsabbildung von 0 auf 0 einfach nicht korrekt.

Verdeutlicht sieht man das in dieser Tabelle:

http://www.swetake.com/qr/qr_table4.html

Da hast Du in der Tat zwar für $\begin{eqnarray*} \alpha^0 \end{eqnarray*}$ einen entsprechenden Wert (1), aber die Rückwärtstabelle (in den Spalten rechts daneben) hat eben für 0 keinen Eintrag, da 0 in der linken Tabelle nirgendwo als Ergebnis des Antilogarithmus vorkommt.

25.07.2012, 00:45

frank09

Auf diesen Beitrag antworten »

Aus der Tabelle ergibt sich ja
$\begin{eqnarray*} LOG(4)=2 \end{eqnarray*}$
$\begin{eqnarray*} LOG(2)=1 \end{eqnarray*}$
$\begin{eqnarray*} LOG(1)=0 \end{eqnarray*}$

Der Sinn der roten Spalte liegt in folgendem
$\begin{eqnarray*} LOG(0) \end{eqnarray*}$ def $\begin{eqnarray*} =0 \end{eqnarray*}$

Um jeder Zahl zwischen 0 und 255 einen Logarithmus zuzuweisen, muss man LOG(0) auch definieren. Man kann die rote Spalte nur als Definition dafür auffassen. Ansonsten hätte man sie weglassen können.

Zitat:

Und ich mein, es ist doch eine Tatsache, dass bei beiden Eingabefolgen dasselbe Ergebnis rauskommt, was de facto nicht sein darf,

Es müssen sogar viele verschiedene Eingabefolgen mit demselben ECC versehen werden:
Anzahl verschiedener Eingaben: $\begin{eqnarray*} 256^{17} \end{eqnarray*}$
Anzahl verschiedener ECCs: $\begin{eqnarray*} 256^{10} \end{eqnarray*}$
Anzahl verschiedener Eingaben, die sich einen ECC teilen: $\begin{eqnarray*} 256^7 \end{eqnarray*}$
Dazu gehören dann wohl auch deine beiden Eingaben.

Wenn man eine eindeutige Zuweisung will, kann man das Generator-Polynom auf Grad 17 erhöhen:

$\begin{eqnarray*} B1 \end{eqnarray*}$ : ECC 228. 13. 18. 169. 183. 61. 43. 54. 24. 34. 187. 39. 227. 76. 252. 147. 109
$\begin{eqnarray*} B2 \end{eqnarray*}$ : ECC 23. 60. 92. 168. 16. 244. 71. 249. 53. 3. 255. 88. 207. 226. 95. 143. 38

25.07.2012, 10:24

Psi

Auf diesen Beitrag antworten »

Jein:

Auch wenn meinetwegen zwei vollständig verschiedene Eingabefolgen zu einem gleichen Ergebnis führen können, sollte dies doch für Eingabefolgen, die sich in nur einem Bit unterscheiden, ausgeschlossen sein. Die Eingabefolgen, die sich einen ECC teilen, sind ja dann selbst auch als Stützstellen in der Decodierung vorhanden, und einzelne Fehler im Polynom lassen sich ausbügeln.

Auf die Auswahl des Generatorpolynoms hab ich keinen Einfluss, denn der Standard gibt genau dieses Polynom für den entsprechenden ECC-Level vor.

Ich möchte nur gern wissen, was der Code für den Fall vorsieht, dass sich die Antilogarithmen der beiden Polynome zu 255 (und somit zu 0, weil modulo 255) addieren. Denn das scheint in der Realität durchaus vorzukommen.

25.07.2012, 11:24

Mystic

Auf diesen Beitrag antworten »

Ich habe mir jetzt nicht alles durchgelesen, aber gelegentlich braucht man eine Bijektion auf einem endlichem Körper, wo die 0 eine Sonderrolle spielt und man als Zusatzdefinition dann die 0 auf die 0 abbildet... Ein schönes Beispiel in dieser Hinsicht ist die Routine SubBytes() im AES, wo im Wesentlichen eine Invertierung im Körper mit 256 Elementen vorgenommen wird und wo man dann auch für die 0 diese "Sonderregelung" benötigt...

25.07.2012, 13:38

Psi

Auf diesen Beitrag antworten »

Genau das ist das Problem: Wenn die 0 auf die 0 abgebildet wird, wobei zusätzlich die 1 ebenfalls auf die 0 abgebildet wird, dann kommt es zu besagtem Phänomen, dass zwei Eingabefolgen, die sich nur im letzten Bit unterscheiden, auf denselben Code hinauslaufen.

Das Problem hier ist, dass die berechnete Fehlerkorrektur schlichtweg falsch ist. Sie korrigiert einen für $\begin{eqnarray*} B_1 \end{eqnarray*}$ berechneten Wert einfach zu $\begin{eqnarray*} B_2 \end{eqnarray*}$ . Die Eingabefolge $\begin{eqnarray*} B_1 \end{eqnarray*}$ lässt sich mit den mir bekannten Mitteln de facto nicht kodieren. Das kann aber nicht Sinn und zweck einer funktionierenden Fehlerkorrektur sein, daher lautet meine Frage nach wie vor, wie in diesem Fall zu verfahren ist, um einen gültigen Fehlerkorrekturwert zu erhalten, der dann auch wieder korrekt auf die Ursprungseingabefolge zurückgeführt werden kann.

25.07.2012, 16:09

Psi

Auf diesen Beitrag antworten »

Sorry für den Doppelpost, brauch noch nen Nachtrag:

Zitat:

Original von frank09
Um jeder Zahl zwischen 0 und 255 einen Logarithmus zuzuweisen, muss man LOG(0) auch definieren. Man kann die rote Spalte nur als Definition dafür auffassen. Ansonsten hätte man sie weglassen können.

Sagen wir so:
Dem Wert $\begin{eqnarray*} \alpha^0 \end{eqnarray*}$ ist der Wert 1 zugeordnet ( $\begin{eqnarray*} 2^1 = 1 \end{eqnarray*}$
Dem Wert $\begin{eqnarray*} \alpha^1 \end{eqnarray*}$ ist der Wert 2 zugeordnet ( $\begin{eqnarray*} 2^2 = 2 \end{eqnarray*}$
Dem Wert $\begin{eqnarray*} \alpha^2 \end{eqnarray*}$ ist der Wert 4 zugeordnet ( $\begin{eqnarray*} 2^2 = 4 \end{eqnarray*}$
etc...

Dem Wert $\begin{eqnarray*} 0 \end{eqnarray*}$ ist der Wert 0 zugeordnet ( $\begin{eqnarray*} 0 = 0 \end{eqnarray*}$

Jetzt geht es aber an die RÜCKÜBERSETZUNG:
Es werden zwei Koeffizienten multipliziert (also zwei Exponenten von $\begin{eqnarray*} \alpha \end{eqnarray*}$ addiert). Dabei kann auch der Wert 255 = 0 rauskommen. Eben nicht $\begin{eqnarray*} \alpha^0 \end{eqnarray*}$ , sondern 0. Demnach müsste ja bei der weiteren Multiplikation überall eine 0 rauskommen, das wär aber leicht quatsch...

28.07.2012, 23:25

Psi

Auf diesen Beitrag antworten »

Ok, ich hab das Thema jetzt mal ein paar Tage ruhen lassen und dann nochmal angegangen, das hat offenbar geholfen.

Die Lösung des Problems ist recht einfach, sogar so einfach, dass ich es für zu einfach hielt:

Evaluiert die Polynomdivision an einer Stelle der Berechnung zu Null, muss der nächste Schritt in der Division einfach übersprungen werden. Die unfedinierte Stelle im Code wird einfach weggelassen!

Ich bedanke mich bei Mystic und frank09 für die Stupser in die richtige Richtung smile

Neue Frage »

Antworten »

Fehlerkorrektur mittels Reed Solomon Code, Term evaluiert zu 0

Verwandte Themen