| |
Für einen beliebigen Vektor a nennt man die Menge a+C={a+x : x ist
Codewort} die Nebenklasse (engl. coset) des Codes. Jeder Vektor u
gehört offensichtlich zu irgendeiner Nebenklasse. Zwei Vektoren a und
b sind genau dann in derselben Nebenklasse, wenn ihre Differenz ein
Codewort ist. Da zwei Nebenklassen entweder disjunkt oder identisch
sind, kann man die Menge aller Wörter der Länge n über dem Alphabet A
als Disjunktion verschiedener Nebenklassen auffassen, wobei eine
Nebenklasse genau die Menge aller Codewörter darstellt.
Aufteilung des Feldes in Nebenklassen
Nehmen wir nun an, der Dekoder empfängt den Vektor y. Dieser ist
bestimmt in einer Nebenklasse enthalten, also y=al+C. Wie
können wir nun den Fehlervektor ermitteln? Wenn wir annehmen, dass das
Codewort x' gesendet wurde, so gilt:
e=y-x'=al+x-x'=al+x'' aus a1+C. Also
befindet sich der Fehlervektor in der selben Nebenklasse wie das
empfangene Wort. Von allen möglichen Fehlervektoren nimmt der Dekoder
natürlich den mit minimalem Gewicht (s.o.). Diesen nennen wir
Klassenanführer (engl. coset leader). Gibt es mehrere Fehlervektoren
minimalen Gewichts, so entscheidet man sich für einen. Wir können nun
eine Tabelle erstellen, die die Aufteilung des Feldes in die
Nebenklassen sowie die Klassenanführer aufzeigt - das Standardfeld.
Bsp.2:
Für den Code mit der Generatormatrix
|1 0 1 1|
G = | |
|0 1 0 1|
und den Codewörtern 0000, 1011, 0101, 1110 ergibt sich folgende Tabelle:
Ein Standardfeld
Es erscheinen alle 16 Vektoren der Länge 4, aufgeteilt in ihre
Nebenklassen. Und so benutzt der Dekoder das Standardfeld: Sobald er
den Vektor y empfängt (z.B. 1111), schaut er nach dessen Position in
der Tabelle. Dann entscheidet er sich für den Klassenanführer als den
wahrscheinlichsten Fehlervektor e, welcher ganz links im Feld steht
(0100), und dekodiert y als das Codewort welches ganz oben in der
Tabelle steht (1011), also x=y-e=1011. Für das Auffinden des
empfangenen Wortes im Standardfeld spielt das sogenannte Syndrom eine
zentrale Rolle. Dieses ist ein Spaltenvektor der Länge (n-k) definiert
als S=H*y. Ist y ein Codewort, so gilt S=0 nach Definition. Im
allgemeinen Fall, wenn y=x+e (x aus C), so gilt:
S=H*y=H*x+H*e=H*e. Das Syndrom hängt also lediglich vom Fehlervektor e
ab. Da in einer bestimmten Zeile des Standardfeldes immer ein
bestimmter Fehlervektor zugrunde gelegt wird (nämlich der
Klassenanführer), genügt es, das Syndrom von diesem zu berechnen. Eine
Nebenklasse ist also durch das Syndrom ihres Klassenanführers
eindeutig bestimmt. Alle Wörter in einer Nebenklasse haben das gleiche
Syndrom. Für den Dekoder bedeutet das, dass er nicht das Wort an sich
im Standardfeld suchen muss, sondern lediglich die Nebenklasse, welche
das selbe Syndrom aufweist. Das erleichtert die Suche in einem
überproportional großen Feld erheblich.
Standardfeld erweitert um das Syndrom
Das Syndrom ist sozusagen das Symptom eines Fehlervektors. Es enthält
alle Informationen, die der Empfänger über die möglichen Fehler
hat. Die Aufgabe eines Dekoders, der nur Fehlererkennung betreibt,
besteht also lediglich darin zu prüfen, ob das Syndrom gleich 0 ist.
Bei unvollständiger Dekodierung wird das Standardfeld in zwei Teile
unterteilt, wobei das Gewicht der Klassenanführer nach unten hin
zunimmt. Liegt der empfangene Vektor im oberen Teil, so wird er ganz
normal korrigiert (s.o.), liegt er jedoch im unteren Teil, so wird nur
festgestellt, dass mehr als c Fehler aufgetreten sind.
Standardfeld bei unvollständiger Dekodierung
|
| |
|
|
