Hamming-Schranke

Hamming-Schranke

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-Likehood 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.

Inhaltsverzeichnis

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 ein Code also eine ungerade Hammingsdistanz haben, 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 Bt(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 An. 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 | An | = qn 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 einem der Bälle enthalten (anders ausgedrückt: Die Bälle ü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 | = 2k 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, d.h. 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 | = 2k.

Es sei noch angemerkt, dass man zwar eigentlich nur an der Korrektur der k Informationsbits interessiert ist, wofür entsprechend weniger Zusatzinformation genügte, dass diese nk Bits Zusatzinformation dann aber fehlerfrei sein müssten, was natürlich i.d.R. nicht gewährleistet werden kann. Daher ist eine Korrektur aller n Bits erforderlich.

Bekannte Perfekte Codes

Es gibt - bis auf Isomorphie – lediglich die folgenden perfekten Codes: [1][2]

  • Alle trivialen Codes beliebiger Länge: Codes die nur aus einem Codewort bestehen.
  • Binäre Wiederholungs-Codes mit ungerader Codewortlänge.
  • Alle binären Hamming-Codes. Hamming-Codes können nur Einfachfehler erkennen und korrigieren. Alle Mehrfachfehler in einem Codewort führen zu Decodierversagen.
  • Der binäre Golay-Code (23,12,7) G23.
  • Die beiden ternären Golay-Codes (11,6,5) G11 und (23,11,5) G23 über dem Galois-Körper GF(3).

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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hamming-Distanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Gewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Der Hamming Abstand zweier Blöcke mit… …   Deutsch Wikipedia

  • Singleton-Schranke — Die Singleton Schranke bezeichnet eine obere Schranke für die Mindestdistanz d eines Blockcodes der Länge n bei Informationswörtern der Länge k über einem einheitlichen Alphabet. Sie lautet: . Die Schranke kann auf folgende Art intuitiv… …   Deutsch Wikipedia

  • Hammingabstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hammingdistanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Mindestdistanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Minimalgewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Block-Code — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”