Linearer Code

Klasse von Codes, die mit Mitteln der linearen Algebra verarbeitet werden können

Ein linearer Code ist in der Kodierungstheorie ein spezieller Blockcode, bei dem die Codewörter Elemente eines endlichdimensionalen Vektorraums über einem endlichen Körper sind. Ein Code ist genau dann linear, wenn er ein Untervektorraum von ist.

Lineare Codes haben den Vorteil, dass Methoden der Linearen Algebra verwendet werden können. Sie sind somit einfach zu kodieren und dekodieren. Die meisten wichtigen Codes sind linear: Hamming-Code, Low-Density-Parity-Check-Code, Reed-Muller-Code, Hadamard-Code, alle zyklischen Codes (damit auch BCH, Reed-Solomon-Codes, Golay-Codes und Goppa-Codes).

Ist die Vektorraumdimension des linearen Codes gleich , so nennt man einen -Code oder bei einem Hamming-Abstand von auch -Code.

Eigenschaften

Bearbeiten

Da   ein Untervektorraum von   ist, existiert eine Basis   von  . Fasst man diese Basis in einer Matrix

 

zusammen, erhält man eine Erzeugermatrix. Des Weiteren besitzt der Code eine Kontrollmatrix  . Für sie gilt   genau dann, wenn   ein Codewort ist. Der Rang von   ist  , der von   ist  . Der Hamming-Abstand von   ist die minimale Anzahl linear abhängiger Spalten der Kontrollmatrix.

Das Hamming-Gewicht eines Codewortes   ist gleich der Anzahl der  , die von Null verschieden sind. Beispielsweise hat das Codewort   über   das Hamming-Gewicht 4. Der Hamming-Abstand des Codes ist gleich dem kleinsten Hamming-Gewicht aller Codewörter außer dem Nullwort.

Permutiert man die einzelnen Koordinaten der Codewörter, erhält man einen sogenannten äquivalenten Code. Damit und mittels linearer Algebra kann man zu jedem linearen Code einen äquivalenten finden, der eine Erzeugermatrix der Form   hat. Dabei ist   die  -Einheitsmatrix, und   ist eine  -Matrix. Dann heißt   Erzeugermatrix in reduzierter Form. Die ersten   Koordinaten können als Informationssymbole und die letzten   als Kontrollsymbole interpretiert werden. Ist   eine Erzeugermatrix in reduzierter Form, kann eine Kontrollmatrix   sofort gefunden werden:  . Ein linearer Code ist bereits durch seine Erzeugermatrix oder seine Kontrollmatrix bestimmt.

Weil der lineare Code ein  -dimensionaler Untervektorraum von   ist, ist er der Kern einer linearen Abbildung  . Die Matrix einer solchen linearen Abbildung heißt Paritätsprüfungsmatrix und wird notiert als   mit  . Der lineare Code ist definiert als Kern dieser linearen Abbildung:  .

Die Informationsrate des linearen Codes   ist  .[1]

Beispiel

Bearbeiten

Der binäre  -Hamming-Code besitzt folgende Erzeugermatrix in reduzierter Form sowie die dazugehörige Kontrollmatrix:

       
       

Kodierung

Bearbeiten

Ein Wort   aus dem Raum   wird kodiert, indem das Produkt   gebildet wird. Die Kodierung des Wortes   mit dem  -Hamming-Code veranschaulicht beispielsweise die folgende Rechnung.

 

Da hier die Addition in   erfolgt, gilt  

Dekodierung

Bearbeiten

Mit Dekodierung bezeichnet man das Zuordnen eines empfangenen, möglicherweise fehlerhaften Eingabevektors   zu einem Codevektor  . Die Dekodierung ist nicht die Umkehrfunktion der Kodierung, die einem Codevektor wieder einen Vektor aus   zuordnet.

Als Dekodierungsmethode wird in der Kodierungstheorie meistens die Methode der größten Wahrscheinlichkeit (englisch: maximum likelihood decoding) verwendet. Dabei wird ein empfangener Vektor   zu dem Codevektor   dekodiert, der mit der größten Wahrscheinlichkeit zum tatsächlich versandten Codevektor   identisch ist. Häufig wird der Vektor, bei dem die wenigsten Stellen (Fehler) korrigiert werden müssen, als der Wahrscheinlichste angenommen. Mathematisch gesprochen heißt das, man sucht den Codevektor   mit dem geringsten Hamming-Abstand zum empfangenen Vektor  . Dieser Fall wird auch als Methode des nächstgelegenen Nachbarn (englisch: nearest neighbor decoding) bezeichnet. Durch Kenntnis der Art der gesendeten Daten oder des verwendeten Kanals können gegebenenfalls andere Informationen verwendet werden, um die Wahrscheinlichkeit für bestimmte Codevektoren zu bestimmen.

Es sei   der tatsächlich versendete (Code-)Vektor und   der empfangene Vektor. Die Dekodierung sucht aus allen   Codevektoren den oder die Codevektoren  , die mit der größten Wahrscheinlichkeit versendet wurden.

 

Bei der Nearest-Neighbor-Dekodierung also:

 

Man sollte dabei beachten, dass diese Zuordnung bei den meisten Codes nicht für alle Fehlervektoren eindeutig ist. Es gibt dann einige Fehlervektoren, die nicht zugeordnet werden können, da sie mehr als einen nächstgelegenen Nachbarn haben. Ist für jeden Fehlervektor eine eindeutige Dekodierung möglich, so heißt der Code perfekt.

Syndromdekodierung

Bearbeiten

Eine effizientere Methode für die Dekodierung stellt die sogenannte Syndrom-Dekodierung dar. Das Syndrom   eines Vektors   erhält man durch Multiplikation der Kontrollmatrix   mit  .

 

Es sei   der Fehlervektor von  . In   sind genau die Koordinaten ungleich Null, bei denen während der Übertragung Fehler aufgetreten sind.

Für das Syndrom von   gilt wegen der Linearität des Codes:

 

Da das Syndrom von fehlerfreien Codevektoren immer Null ist, folgt:

 

Alle (fehlerhaften) Wörter mit dem gleichen Fehlervektor sind im gleichen affinen Unterraum, das heißt für solche Wörter ist das Syndrom   konstant.

Alle Vektoren, die aus einem beliebigen, festen Vektor durch Subtraktion eines beliebigen Codevektors hervorgegangen sind, bilden eine Nebenklasse der Untergruppe   von  . Der Vektor mit minimalem Gewicht in dieser Klasse heißt Führer der Nebenklasse (englisch: coset leader). Daher ist auch der Begriff „coset leader decoding“ verbreitet.

Um   zu   zu dekodieren, sucht man also den Fehlervektor  , dessen Syndrom identisch zum Syndrom von   ist und dessen Hamming-Gewicht minimal ist. Mit diesem Fehlervektor berechnet man   den nächstgelegenen Codevektor  . Man kann also eine Tabelle mit bis zu   Zeilen aufstellen, die für jedes Syndrom eines empfangenen Vektors den entsprechenden Fehlervektor mit minimalem Hamming-Gewicht beinhaltet. Ist das Syndrom gleich 0, dann muss nichts korrigiert werden ansonsten beschränkt sich Dekodierung auf das Nachschlagen des Fehlervektors in dieser Tabelle und Korrigieren der so detektierten Fehler.

Anders interpretiert sind die Nebenklassen gerade die Äquivalenzklassen der Äquivalenzrelation   Die Führer sind gerade Vertreter der Äquivalenzklassen, man wählt einen mit minimalem Hamming-Gewicht. Perfekte Codes zeichnen sich dadurch aus, dass die Führer eindeutig festgelegt sind.

Die Dekodierung von linearen Codes ist im Allgemeinen NP-vollständig, das heißt, es sind keine Algorithmen mit polynomieller Laufzeit bekannt.[2] Die bekannten linearen Codes, beispielsweise Hamming-Codes, zeichnen sich dadurch aus, dass für sie effiziente Dekodierungs-Algorithmen bekannt sind. Die Komplexität der linearen Dekodierung ist Grundlage für das McEliece-Kryptosystem, das als sicher gilt, aber aufgrund seiner vergleichsweise langen Schlüssel bisher selten eingesetzt wird.

Beispiel

Bearbeiten

Will man den  -Hamming-Code (von oben) dekodieren, trifft man zuerst die Annahme, dass nur  -Bit Fehler auftreten. Die möglichen Fehlervektoren   sind dann

 
 
 
 
 
 
 

Für jeden dieser Fehlervektoren wird nun das Syndrom   berechnet. Damit ergibt sich

   
   
   
   
   
   
   
   

Wird dann das fehlerhafte Wort   empfangen, ergibt dann  . Damit ergibt sich der Fehlervektor  , und   wird somit nach   dekodiert. Das Klartextwort ist dann  .

Beispiel mit unvollständiger Dekodierung

Bearbeiten

Gegeben sei der ternäre ( ) Wiederholungscode der Länge 3:

       

Jeweils zwei Spalten von   sind linear unabhängig, alle drei dagegen linear abhängig. Der minimale Hamming-Abstand des Codes berechnet sich als minimale Anzahl linear abhängiger Spalten in   also zu 3. Es kann damit höchstens ein Zeichenfehler korrigiert werden. Die Syndromtabelle sieht folgendermaßen aus:

   
   
   
   
   
   
   

Durch Ausnützen von Linearitäten könnte die Anzahl der Zeilen halbiert werden, man muss dann aber testen, ob ein linear abhängiges Syndrom in der Tabelle ist.

Man betrachte nun  ,  . Bei   ist das Syndrom  , die Korrektur lautet:  . Die Berechnung des Syndroms von   ergibt:  . Dieser Wert ist nicht in der Syndromtabelle enthalten, das Wort kann also nicht korrigiert werden.

Anwendung

Bearbeiten

Die Kodierung und Dekodierung ist, so wie sie oben beschrieben ist, relativ aufwendig. Bei der Kodierung muss die Erzeugermatrix im Speicher gehalten werden, was bei Systemen mit begrenzten Ressourcen (zum Beispiel mobile Endgeräte oder Weltraumsonden) problematisch ist. Bei der Dekodierung wird eine – je nach Korrekturrate – große Tabelle benötigt; der Speicherverbrauch ist dementsprechend groß. Aus diesem Grund werden in der Regel zusätzliche Eigenschaften der Codes benutzt, um diese effizient zu kodieren und dekodieren. Binäre zyklische Codes lassen sich beispielsweise sehr einfach mittels Schieberegister und Exklusiv-Oder-Gatter realisieren.

Dualer Code

Bearbeiten

Zu jedem (linearen) Code   gibt es einen dualen Code (oder auch Dualcode)  , der selbst ein linearer Code ist. Die Codewörter des dualen Codes sind alle Wörter aus  , die zu den Codewörtern aus   dual sind:

Man definiert hierzu ein inneres Produkt:

 

das die Vektoren   folgendermaßen abbildet:

 

Trotz der ähnlichen Definition handelt es sich hierbei nicht um ein Skalarprodukt, da diese Bilinearform nicht positiv definit ist. Es gibt nämlich aufgrund der Eigenschaften von Endlichen Körpern meistens Vektoren, die ungleich dem Nullvektor sind und bei denen das innere Produkt 0 ergibt. Man denke beispielsweise an den binären Vektor  .

Mit Hilfe dieser Definition ergibt sich der Duale Code als:

 

Eine Erzeugermatrix des dualen Codes ist eine Kontrollmatrix des Ursprungscodes und umgekehrt.

Der duale Code spielt bei der Analyse der Eigenschaften von Codes eine wichtige Rolle.

Ein Spezialfall sind die sogenannten selbstdualen Codes. Dies sind Codes, die mit ihrem Dualcode identisch sind. Aus Dimensiongründen haben diese immer die Dimension  . Das wichtigste Beispiel für einen selbstdualen Code ist der erweiterte Hamming-Code, bei dem der binäre [7,4,3]-Hamming-Code um ein Paritätsbit auf gerade Parität erweitert wird:

 

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Technische Universität Berlin: Linear Codes
  2. E. R. Berlekamp, R. J. McEliece, H. C. A. von Tilburg: On the inherent intractability of certain coding problems. In: IEEE Transactions on Information Theory 24. 1978.