Perfekter Code

Ein perfekter Code, oder auch dicht gepackter Code, bezeichnet in der Codierungstheorie einen Blockcode $C \subset A^n$, bei dem jedes Wort $x\in A^n$ nur zu genau einem Codewort $c \in C$ eine minimale Hamming-Distanz hat.

Bei der für gewöhnlich verwendeten Maximum-Likelihood Decodierung bedeutet dies, dass jedem empfangenen Wort ein Codewort eindeutig zugeordnet werden kann. Daraus leitet sich die Bezeichnung perfekt ab, denn es gibt keine mehrdeutigen Decodiermöglichkeiten.

Mathematische Beschreibung

Sei $C \subset A^n$ ein Blockcode mit | A | = q, wobei A das verwendete Alphabet darstellt. C habe eine Hammingdistanz von d. Er kann damit

$t= \left \lfloor \frac{d-1}{2} \right \rfloor$

Fehler korrigieren.

Um perfekt zu sein muss die minimale Hammingdistanz zwischen zwei Wörtern eines Codes ungerade sein, da es sonst für $c_1,c_2 \in C : d_H(c_1,c_2)=d$ ein Wort x mit $d_H(x,c_1)=\frac{d}{2}=d_H(x,c_2)$ gibt, was im Widerspruch zur Definition eines perfekten Codes steht.

Da der Code t fehlerkorrigierend ist, kann ein Wort $x \in A^n$ einem Codewort $c \in C$ eindeutig zugeordnet werden, wenn die Hammingdistanz $d_H(c,x) \leq t$ ist. Umgekehrt bedeutet dies für ein bestimmtes Codewort c, dass alle Wörter x mit einer Hammingdistanz von höchstens t nach c decodiert werden. Als Menge wird dies so geschrieben:

$B_t(c):=\{x\in A^n | d_h(x,c) \leq t \}$

Diese Menge wird auch als Kugel (manchmal auch Hyperwürfel) mit Radius t um c bezeichnet. Die Anzahl der Elemente von B_t(c) ist dabei:

$|B_t(c)|={\sum_{i=0}^t (q-1)^i \binom n i}$

Für i Fehlerstellen gibt es i aus n mögliche Positionen für die Fehler. Dabei stehen pro Fehlerstelle q − 1 falsche Symbole zur Verfügung. Es gibt | C | Kugeln. Diese sind disjunkte Teilmengen des Aⁿ. Daraus ergibt sich die Ungleichung

$|A^n| \geq |C| {\sum_{i=0}^t(q-1)^i \binom n i}$

Aufgelöst nach C und mit | Aⁿ | = qⁿ folgt:

$|C| \leq \frac{q^n}{{\sum_{i=0}^t(q-1)^i \binom n i}}$

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

Bei einem perfekten Code sind alle Wörter $x \in A^n$ in einer der Kugeln enthalten (anders ausgedrückt: Die Kugeln überdecken den Raum). Deshalb gilt bei der Hammingschranke für diesen Code dann die Gleichheit.

Alternative Interpretation

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

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

• | C | = 2^k verschiedene Informationswörter und jeweils
• alle möglichen Muster von $0\ldots t$ Bitfehlern der n Bits eines Codewortes

Da es $\binom n i$ Möglichkeiten gibt, i Bitfehler auf n Bits zu verteilen, ergeben sich insgesamt

$2^k \cdot \sum_{i=0}^t \binom n i$

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

$2^n \ge 2^k \cdot \sum_{i=0}^t \binom n i$.

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

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

Bekannte Perfekte Codes

Falls die Alphabetgröße q eine Primzahlpotenz ist, so gilt: Ist C ein perfekter Code mit Parametern (n, | C | ,d), so gibt es einen Code D mit denselben Parametern, so dass D einer der folgenden Codes ist^[1] [2]:

• Ein trivialer Code. Ein Code heißt hier trivial, falls er entweder nur ein einziges Codewort enthält, oder falls er sämtliche qⁿ möglichen Wörter der gegebenen Blocklänge enthält.
• Ein binärer Wiederholungs-Code mit ungerader Codewortlänge. Die Parameter lauten (2m + 1,2,2m + 1), für ein $m\in \mathbb{N}$.
• Ein Hamming-Code über dem endlichen Körper $\mathbb{F}_q$, mit Parametern $\;\left( \frac{q^k-1}{q-1}, q^{n-k} , 3 \right)$
• Der binäre Golay-Code $\mathcal{G}_{23}$ mit Parametern (23,2¹²,7)
• Der ternäre Golay-Code mit Parametern $\mathcal{G}_{11}$ mit (11,3⁶,5)

Die Codes C und D haben die gleichen Parameter und können somit bei gleicher Blocklänge n 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 statt dessen auch der Nullvektor $(0,\dots,0)$ als einziges Codewort dienen, und der entstandene Code ist linear. Der einzige verbleibende triviale Code ist derjenige, der sämtliche qⁿ 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 also für jeden perfekten Code, der im Allgemeinen kein linearer Code sein muss, 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 korrigiert werden können.

Einzelnachweise

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