In dem Welch-Berlekamp-Algorithmus zum Decodieren von Reed-Solomon-Codes erhält man eine Liste von Punkten die eine Nachricht mit Fehlern auf dem an unbekannten Stellen darstellen (und wird dem Algorithmus gegeben). Die Ausgabe ist ein Polynom, das alle angegebenen Punkte mit Ausnahme derjenigen durchläuft, bei denen Fehler aufgetreten sind.e b i e
Das Verfahren beinhaltet das Lösen eines Systems linearer Gleichungen der Form
für alle denen den Grad und höchstens den Grad . Die Variablen sind die Koeffizienten von und .E e Q e + k E Q.
Um sicherzustellen, dass den Grad fügt man dem obigen linearen System normalerweise die Bedingung hinzu, dass der Koeffizient von 1 ist. In der Praxis kennt man jedoch nicht unbedingt . Eine ineffiziente (aber immer noch polynomielle) Methode, um damit umzugehen, besteht darin, für alle Werte zu versuchen , beginnend mit , bis eine Lösung gefunden wird.e x e E e ( n + k - 1 ) / 2 - 1
Meine Frage ist: Gibt es eine effizientere Möglichkeit, zu bestimmen ? Gibt es alternativ eine Modifikation des linearen Systems, die es ermöglicht, anstelle des exakten Werts eine Obergrenze für verwenden?
Insbesondere möchte ich diesen speziellen Decoder für Reed-Solomon-Codes verwenden und keinen völlig anderen Algorithmus, der auf anderen Techniken basiert.
Als Antwort auf die Antwort von DW ist hier mein Arbeitsbeispiel. Alles ist modulo 7 erledigt.
plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]
Der Fehler liegt also im dritten Punkt.
Wenn die fragliche Polynomgleichung
Wenn Sie das System in Matrixform:
[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
Die letzte Zeile ist die Einschränkung, dass . Wenn wir die Gaußsche Eliminierung anwenden, erhalten wir
[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]
Und wenn wir 1 für beide freien Variablen auswählen, erhalten wir einen Lösungsvektor von
[2, 2, 1, 4, 1, 0, 1, 1]
Was übersetzt bedeutet
E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4
Und teilt . Man beachte, dass Faktoren wieQ Q ( t + 6 ) ( t 3 + 2 t 2 + 2 t + 3 )
Für bekomme ich eine gute Lösung:
system is:
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0]
[0, 1, 0, 0, 0, 0, 1]
reduced system is:
[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]
solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0
Beachten Sie, dass das obige Gegenbeispiel zwar von Code generiert wurde, den ich von Grund auf neu geschrieben habe (es war im Grunde das erste, was ich versucht habe), man jedoch überprüfen kann, ob die Lösungen von Hand gültig sind. Selbst wenn mein Code fehlerhaft ist, ist er dennoch ein gültiges Gegenbeispiel für den Anspruch dass mit funktioniert.
quelle
Antworten:
Das gleiche Verfahren funktioniert tatsächlich, um eine beliebige Anzahl von Fehlern bis zu zu korrigieren .e
Voraussetzung ist, dass das Fehlerpolynom an jedem Punkt dem ein Fehler ist, Null ist . Nichts sagt, dass es nur an diesen Punkten Null sein muss; Sie können ein , das auch an anderen Punkten Null ist, und das ist in Ordnung, solange sein Grad .a i E ( x ) eE(x) ai E(x) e
Wenn also eine Obergrenze für die Anzahl der Fehler ist, existiert ein Polynom mit allen gewünschten Eigenschaften (dh es hat den Grad genau und ist an jedem Punkt, an dem ein Fehler vorliegt, Null). Wenn zum Beispiel weniger als Fehler vorliegen, gibt es ein Polynom , das bei jedem Fehler Null und an einigen weiteren Punkten Null ist, um die Anzahl der Nullen auf genau .E ( x ) e e E ( x ) ee E(x) e e E(x) e
Schließlich besagt der Korrektheitssatz, dass, wenn ein solches Polynom existiert, der Berlekamp-Welch-Algorithmus es finden kann. Selbst wenn weniger als Fehler vorliegen, funktioniert die Prozedur immer noch korrekt, um zu identifizieren . Sobald Sie , können Sie Positionen identifizieren , die fehlerfrei sind, und dann können Sie auf einfache Weise dekodieren.e E ( x ) E ( x ) n - eE(x) e E(x) E(x) n−e
Um das Ergebnis des Gesprächs über das "Gegenbeispiel" in der Frage zu dokumentieren:
Das ist eigentlich kein gültiges Gegenbeispiel. Der Fehler bestand in der Berechnung, wie viele Fehler Berlekamp-Welch korrigieren sollte. Der Abstand beträgt , daher sollten Sie erwarten, dass er bis zu Fehler korrigieren kann (wie Ran G. hervorhebt). In Ihrem Gegenbeispiel ist und , also , daher sollten Sie nur erwarten, dass diese Prozedur einen Fehler korrigieren kann, dh . Wenn Sie die Prozedur in einem Beispiel mit , besteht kein Grund zu der Annahme, dass die Prozedur ordnungsgemäß funktioniert.( n - k ) / 2 n = 5 k = 3 ( n - k ) / 2 = 1 e = 1 e = 2n−k+1 (n−k)/2 n=5 k=3 (n−k)/2=1 e=1 e=2
Das Gegenbeispiel ist also eigentlich kein Gegenbeispiel und widerspricht meiner obigen Antwort nicht.
quelle