Perfekter Code

Code mit eindeutiger Decodierung

Ein perfekter Code, oder auch dicht gepackter Code, bezeichnet in der Codierungstheorie einen Blockcode , in dem jedes Wort nur zu genau einem Codewort (und nicht zu mehreren) einen geringsten Hamming-Abstand hat, wobei ist.

Bei der meist verwendeten Maximum-Likelihood-Decodierung bedeutet dies, dass jedes empfangene Wort genau ein Codewort hat, zu dem es den geringsten Hamming-Abstand hat und zu dem es eindeutig zugeordnet werden kann. Daraus leitet sich die Bezeichnung perfekt ab, denn es gibt keine mehrdeutigen Decodiermöglichkeiten.

Mathematische BeschreibungBearbeiten

Sei   ein Blockcode mit  , wobei   das verwendete Alphabet darstellt. Alle Codeworte   haben untereinander einen Mindest-Hamming-Abstand von  . Er kann damit

 

Fehler korrigieren.

Um perfekt zu sein, muss der minimale Hamming-Abstand zwischen zwei Codeworten eines Codes ungerade sein, da sonst für   mindestens ein Wort   mit   existiert, was im Widerspruch zur Definition perfekter Codes steht.

Da der Code  -fehlerkorrigierend ist, kann ein Wort   einem Codewort   eindeutig zugeordnet werden, wenn der Hamming-Abstand   ist. Umgekehrt bedeutet dies für ein bestimmtes Codewort  , dass alle Wörter   mit einem Hamming-Abstand von maximal   nach   decodiert werden. Als Menge wird dies so geschrieben:

 

Diese Menge wird auch als Kugel (manchmal auch Hyperwürfel) mit Radius   um   bezeichnet. Die Anzahl der Elemente von   lässt sich berechnen zu:

 

Für   Fehlerstellen gibt es   aus   mögliche Positionen für die Fehler. Dabei stehen pro Fehlerstelle   falsche Symbolwerte zur Verfügung. Es gibt   Kugeln. Diese sind disjunkte Teilmengen des  . Daraus ergibt sich die Ungleichung

 

Aufgelöst nach   und mit   folgt:

 

Diese Ungleichung für die Anzahl der Codewörter wird Hamming-Schranke oder auch Kugelpackungsschranke genannt.

Ein perfekter Code zeichnet sich dadurch aus, dass alle Wörter   in genau einer der Kugeln enthalten sind (anders ausgedrückt: Die Kugeln überdecken den Raum). Deshalb gilt für die Hamming-Schranke selbst die Gleichheit.

Alternative InterpretationBearbeiten

Man kann sich diese Grenze auch wie folgt veranschaulichen (der Einfachheit halber nur anhand binärer Codes erläutert, d. h. für  ):

Für einen   Fehler korrigierenden Code muss der Decoder genug Information erhalten, um alle folgenden Fälle unterscheiden zu können:

  •   verschiedene Informationswörter und jeweils
  • alle möglichen Muster von   Bitfehlern der   Bits eines Codewortes

Da es   Möglichkeiten gibt,   Bitfehler auf   Bits zu verteilen, ergeben sich insgesamt

 

Fälle, die mit den zur Verfügung stehenden   Bits unterschieden werden müssen, also

 .

Bei einem perfekten Code gilt Gleichheit, das heißt die   Bits tragen exakt die minimal benötigte Information. Diese (Un-)Gleichung entspricht der obigen allgemeinen Definition für den Fall   und  .

Man ist zwar eigentlich nur an der Korrektur der   Informationsbits interessiert, wofür entsprechend weniger Zusatzinformation genügen würde – diese   Bits Zusatzinformation müssten dann aber fehlerfrei sein, was natürlich in der Regel nicht gewährleistet ist. Daher ist eine Korrektur aller   Bits erforderlich.

Bekannte Perfekte CodesBearbeiten

Falls die Alphabetgröße   eine Primzahlpotenz ist, so gilt:

Ist   ein perfekter Code mit Parametern   mit  , so gibt es einen Code   mit denselben Parametern, so dass   einer der folgenden Codes ist[1] [2]:

  • Ein trivialer Code: Ein Code heißt hier trivial,
    • falls er entweder nur  , d. h. ein einziges Codewort enthält:   oder
    • falls er alle   möglichen Codewörter der gegebenen Blocklänge enthält:  .
  • Ein binärer Wiederholungs-Code mit ungerader Codewortlänge. Die Parameter lauten  .
  • Ein Hamming-Code über dem endlichen Körper  , mit Parametern  .
  • Der binäre Golay-Code   mit Parametern  .
  • Der ternäre Golay-Code mit Parametern   mit  .

  steht hierbei jeweils für eine positive natürliche Zahl  .

Die Codes   und   haben die gleichen Parameter und können somit bei gleicher Blocklänge   gleich viele Fehler korrigieren. Die Umwandlung eines trivialen Codes in einen linearen Code mit denselben Parametern ist einfach: Falls der Code ein einziges Codewort enthält, so kann stattdessen auch der Nullvektor   als einziges Codewort dienen, und der entstandene Code ist linear. Der einzige verbleibende triviale Code ist derjenige, der sämtliche   möglichen Wörter der gegebenen Blocklänge enthält. Dieser ist aber bereits linear. Bei den restlichen Codes aus der Liste handelt es sich bereits um lineare Codes. Es gibt für jeden perfekten Code, der im Allgemeinen kein linearer Code ist, einen linearen Code mit den gleichen Parametern – sofern die Größe des Alphabetes eine Primzahlpotenz ist.

Es ist offen, ob, und für welche Parameter es nicht triviale perfekte Codes gibt, falls die Alphabetgröße keine Primzahlpotenz ist.

Für praktische Zwecke sind die trivialen Codes uninteressant, da entweder

  • keine Information übertragen werden kann oder
  • keine Fehler erkannt oder korrigiert werden können.

EinzelnachweiseBearbeiten

  1. F.J. MacWilliams, N.J.A. Sloane: The Theory of Error-Correcting Codes, Amsterdam, North-Holland, 1977
  2. Werner Lütkebohmert: Codierungstheorie, Braunschweig/Wiesbaden, Vieweg, 2003