imported>Ulricus Angelus: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-05-31T12:26:36Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Ein '''perfekter Code''', oder auch '''dicht gepackter Code''', bezeichnet in der [[Codierungstheorie]] einen [[Blockcode]] <math>\mathcal C \subset \Sigma^n</math>, in dem jedes Wort <math>w \in \Sigma^n</math> nur zu genau einem [[Code]]wort <math>c \in \mathcal C</math> (und nicht zu mehreren) einen geringsten [[Hamming-Abstand]] <math>d_w</math> hat, wobei <math>d_w \leq \Delta(\mathcal C)</math> ist.

Bei der meist verwendeten [[Decodierregel#Maximum-Likelihood-Decodierung|Maximum-Likelihood-Decodierung]] bedeutet dies, dass jedes empfangene Wort <math>w</math> genau ein Codewort <math>c</math> 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 Beschreibung ==
Sei <math>\mathcal C \subset \Sigma^n </math> ein [[Blockcode]] mit <math>|\Sigma| = q</math>, wobei <math>\Sigma</math> das verwendete [[Alphabet (Mathematik)|Alphabet]] darstellt. Alle Codeworte <math>\mathcal C</math> haben untereinander einen Mindest-Hamming-Abstand von <math>d</math>. Der Blockcode kann damit

: <math>t = \left \lfloor \frac{d-1}{2} \right \rfloor</math>

Fehler korrigieren.

Um perfekt zu sein, muss der minimale Hamming-Abstand zwischen zwei Codeworten eines Codes ungerade sein, da sonst für <math>c_1,c_2 \in \mathcal C : \Delta(c_1,c_2) = d</math> mindestens ein Wort <math>w</math> mit <math>\Delta(c_1, w) = \tfrac{d}{2} = \Delta(w, c_2)</math> existiert, was im Widerspruch zur Definition perfekter Codes steht.

Da der Code <math>t</math>-fehlerkorrigierend ist, kann ein Wort <math>w \in \Sigma^n</math> einem Codewort <math>c \in C</math> eindeutig zugeordnet werden, wenn der Hamming-Abstand <math>d = \Delta(c,w) \leq t</math> ist. Umgekehrt bedeutet dies für ein bestimmtes Codewort <math>c</math>, dass alle Wörter <math>w</math> mit einem Hamming-Abstand von maximal <math>t</math> nach <math>c</math> decodiert werden. Als Menge wird dies so geschrieben:

: <math>\mathcal B_t(c) := \{ w \in \Sigma^n \mid \Delta(w,c) \leq t \}</math>

Diese Menge wird auch als Kugel (manchmal auch Hyperwürfel) mit Radius <math>t</math> um <math>c</math> bezeichnet. Die Anzahl der Elemente von <math>\mathcal B_t(c)</math> lässt sich berechnen zu:

: <math>|\mathcal B_t(c)| = { \sum_{i=0}^t (q-1)^i \binom n i }</math>

Für <math>i</math> Fehlerstellen gibt es [[Binomialkoeffizient|<math>i</math> aus <math>n</math>]] mögliche Positionen für die Fehler. Dabei stehen pro Fehlerstelle <math>q-1</math> falsche Symbolwerte zur Verfügung. Es gibt <math>|\mathcal C|</math> Kugeln. Diese sind disjunkte Teilmengen des <math>\Sigma^n</math>. Daraus ergibt sich die Ungleichung

: <math> |\Sigma^n| \geq |\mathcal C| {\sum_{i=0}^t(q-1)^i \binom n i} </math>

Aufgelöst nach <math>\mathcal C</math> und mit <math>|\Sigma^n| = q^n</math> folgt:

: <math> |\mathcal C| \leq \frac{q^n}{{\sum_{i=0}^t(q-1)^i \binom n i}} </math>

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 <math>w \in \Sigma^n</math> 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 Interpretation ==
Man kann sich diese Grenze auch wie folgt veranschaulichen (der Einfachheit halber nur anhand binärer Codes erläutert, d. h. für <math>q = 2</math>):

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

* <math>|\mathcal C| = 2^k</math> verschiedene Informationswörter und jeweils
* alle möglichen Muster von <math>0\ldots t</math> Bitfehlern der <math>n</math> Bits eines Codewortes

Da es <math>\binom n i</math> Möglichkeiten gibt, <math>i</math> [[Bitfehler]] auf
<math>n</math> Bits zu verteilen, ergeben sich insgesamt

: <math>2^k \cdot \sum_{i=0}^t \binom n i</math>

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

: <math>2^n \ge 2^k \cdot \sum_{i=0}^t \binom n i</math>.

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

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

== Bekannte Perfekte Codes ==
Falls die Alphabetgröße <math>q</math> eine [[Primzahlpotenz]] ist, so gilt:

Ist <math>\mathcal C</math> ein perfekter Code mit Parametern <math>[n,k;d,q]</math> mit <math>k = \mathrm{log}_q(|\mathcal C|)</math>, so gibt es einen Code <math>\mathcal D</math> mit denselben Parametern, so dass <math>\mathcal D</math> einer der folgenden Codes ist<ref>F.J. MacWilliams, N.J.A. Sloane: ''The Theory of Error-Correcting Codes''. North-Holland, Amsterdam 1977</ref><ref>Werner Lütkebohmert: ''Codierungstheorie''. Vieweg, Braunschweig / Wiesbaden 2003</ref>:

* Ein trivialer Code: Ein Code heißt hier ''trivial'',
** falls er entweder nur <math>q^0 = 1</math>, d. h. ein einziges Codewort enthält: <math>[m, 0; 2m+1, q]</math> oder
** falls er alle <math>q^m</math> möglichen Codewörter der gegebenen Blocklänge enthält: <math>[m, m; 1, q]</math>.
* Ein [[Dualsystem|binärer]] [[Wiederholungs-Code]] mit ungerader Codewortlänge. Die Parameter lauten <math>[2m+1, 1; 2m+1, 2]</math>.
* Ein [[Hamming-Code]] über dem [[Endlicher Körper|endlichen Körper]] <math>\mathbb{F}_q</math>, mit Parametern <math>\;\left[ \frac{q^m-1}{q-1}, \frac{q^m-1}{q-1}-m; 3, q \right]</math>.
* Der binäre [[Golay-Code]] <math>\mathcal{G}_{23}</math> mit Parametern <math>[23, 12; 7, 2]</math>.
* Der [[Ternärsystem|ternäre]] [[Golay-Code]] mit Parametern <math>\mathcal{G}_{11}</math> mit <math>[11, 6; 5, 3]</math>.

<math>m</math> steht hierbei jeweils für eine positive natürliche Zahl <math>m \in \mathbb{N}^{+}</math>.

Die Codes <math>\mathcal C</math> und <math>\mathcal D</math> haben die gleichen Parameter und können somit bei gleicher Blocklänge <math>n</math> 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]] <math>c_0 = (0,\dots,0)</math> als einziges Codewort dienen, und der entstandene Code ist linear. Der einzige verbleibende triviale Code ist derjenige, der sämtliche <math>q^n</math> 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 [[Linearer Code|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.

== Einzelnachweise ==
<references />

[[Kategorie:Kodierungstheorie]]

Perfekter Code - Versionsgeschichte

imported>Ulricus Angelus: /* growthexperiments-addlink-summary-summary:1|0|0 */