Liebe/-r Experte/-in,
Erstmal danke für deine Zeit. Ich habe eine Frage aus der Codierungstheorie, Speziell zu Gruppencodes. Spezieller zu Hamming und Abramson-Codes. Allgemein gilt für diese codes, dass sie aus k kontrollstellen und m nachrichtenstellen eine bitfolge von n=k+m Zeichen ergeben. Für k gilt allgemein k = grad(Generatorpolynom).
Mir ist nun eine Regelmäßigkeit aufgefallen, die ich mir direkt nicht erklären kann. Ich werde diese jetzt an einem Beispiel erklären. Es geht darum ein Fehlerhaftes Codewort zu erkennen und zu korrigieren:
Betrachten wir den Hamming-Code mit dem Generatorpolynom G(u) = u^5+u^4+u^3+u^2+u+1. Das entspricht einer Bitfolge von 111101. Nach dem Satz n=k+m=(2^k)-1 folgt für k=5, n= 31, m=16.
Dazu haben wir folgendes Codewort:
110101… (gefolgt von Nullen bis zur Länge n=31)
Das Standartvorgehen wäre es jetzt, das Codewort durch das Generatorpolynom zu teilen, und das entstehende Fehlersyndrom, ein RS0 daraus zu berechnen und dieses durch ein Schieberegister zu takten. Extrem aufwändig. Mir scheint aber, dass, wenn die Anzahl der Stellen von der ersten bis zur letzten Eins im Codewort k nicht überschreitet, man sich das Leben ganz einfach machen kann:
11010100000000… /
111101
der Codewortabschnitt unterscheidet sich nur an Stelle drei vom Genratorpolynom. Vermutung: hier liegt der Fehler - und Tatsache! Das dritte Byte ist fehlerhaft.
Dieses Herangehen hat für mich bisher immer dann funktioniert wenn:
- wenn die Anzahl der Stellen von der ersten bis zur letzten Eins im Codewort kleiner oder gleich k ist
2a) Mann im Fall Hamming genau einen Bitfehler erkennt
2b) Im Falle Abramson einen ein-Bit Fehler- oder einen benachbarten 2-Bit Fehler erkennt.
Kann mir jemand erklären, warum das der Fall ist? Zur vereinfachten Berechnung der Codes kann man hier ein Tool für die Berechnung veschiedener Codes herunterladen:
www.public.kenomaerz.de/ct.exe (kein Virus, Ehrenwort)
Vielen Dank für deine Antwort auf diese sehr spezielle Frage.
Liebe Grüße,
Keno