close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Interesse - Volksbank Anröchte eG

EinbettenHerunterladen
Blockcodes und Hamming-Metrik
Michael Braun
12. Oktober 2014
Bei der Übertragung von Zeichenfolgen über einen störungsanfälligen Kanal können sich Fehler einschleichen, die beim
Empfänger weder erkannt noch korrigiert werden können. Ziel
der Kanalcodierung ist es, durch Hinzufügen redundanter Zeichen
an Nachrichten, Fehler zu erkennen bzw. sogar zu korrigieren.
Wir führen die grundlegenden Begriffe der Kanalcodierung ein.
Zentraler Gegenstand sind hier die Hamming-Metrik, die einen
Abstandsbegriff für Nachrichten definiert und die MinimaldistanzDecodierung, ein Verfahren zur Korrektur der durch einen störungsanfälligen Kanal hervorgerufenen Fehler bei der Nachrichtenübertragung.
Aus der Quellencodierung wissen wir, wie man Nachrichten
geschickt (mit optimaler durchschnittlicher Länge pro Zeichen)
über dem Alphabet Σ = {0, 1} codieren kann. Nachrichtenzeichen
werden also unterschiedlich lang – je nach Auftrittswahrscheinlichkeit – binär codiert und durch Konkatenation zu Nachrichten
zusammengefügt. Nachrichten sind in diesem Fall dann nichts
anderes als Bitfolgen.
Wir werden nun diesen Nachrichten Redundanz hinzufügen, so
dass im Falle von auftretenden Fehlern bei einer Übertragung der
Nachricht nach Empfang der Nachricht diese Fehler erkennt bzw.
korrigiert werden können.
Wie fügt man an eine solche Bitfolge, die eine Nachricht repräsentiert, geschickt Redundanz hinzu? Der erste Schritt zur
Beantwortung dieser Frage ist der folgende: Wir zerteilen die
Folge von Zeichen aus Σ = {0, 1} zunächst in handliche Portionen
einer festen Länge k. Die dadurch entstehenden Teilfolgen bilden
die Nachrichtenwörter.
Definition 1. Sei Σ eine endliche Menge. Die Menge der Folgen
der Länge k ∈ N, Σk = {x = [x0 , . . . , xk−1 ] | xi ∈ Σ}, bildet
den so genannten Nachrichtenraum. Die Elemente aus Σk heißen
Nachrichtenwörter und der Wert k bezeichnet die Dimension des
Nachrichtenraums.
Betrachten wir jetzt den Fall, dass ein Nachrichtenwort x ∈ Σk
über einen störungsanfälligen Kanal übermittelt werden soll.
blockcodes und hamming-metrik
Während der Übertragung können sich Fehler einschleichen
und einzelne Symbole können sich in x verändern, so dass ein
anderes Wort x ∈ Σk empfangen wird. Da x selbst ein potenziell
mögliches Nachrichtenwort aus dem Nachrichtenraum Σk ist, kann
der Empfänger an der Stelle nicht erkennen, dass x nicht die
ursprünglich beabsichtigte Nachricht ist. Das Verändern eines
Nachrichtenwortes x ∈ Σk führt also wieder zu einem gültigen
Nachrichtenwort x ∈ Σk .
Um nun aber eine Fehlererkennung bzw. -korrektur zu ermöglichen, werden die Nachrichtenwörter auf längere Wörter abgebildet,
um auf diese Weise den Nachrichtenwörtern redundante Information hinzuzufügen. Mathematisch geschieht dieses Hinzufügen von
Redundanz, indem die eigentliche Menge der Nachrichtenwörter
Σk in eine größere Menge Σn , d.h. n > k, injektiv abgebildet
wird. Jedes Element aus Σk erhält somit genau einen Partner
aus Σn und die dadurch resultierende Menge C ⊆ Σn bildet den
so genannten (Block-)Code. Die dazugehörige Vorschrift wie ein
Nachrichtenwort aus Σk auf ein Element aus C abgebildet wird,
bezeichnet man als Codierung.
Anstelle eines Nachrichtenwortes x aus Σk wird das dazugehörige Element c aus dem Code C über den störungsanfälligen Kanal
gesendet. Treten dabei Fehler auf, dann ändern sich einzelne Zeichen und anstelle des Wortes c aus dem Code C wird ein Wort y
aus dem gesamten Raum Σn empfangen.
Ist die Codierung geschickt gewählt, so dass sich die resultierenden Codewörter gut im Raum Σn verteilen und ist die Anzahl
der auftretenden Fehler nicht zu groß, dann wird der Vektor y
in der Regel kein gültiges Wort aus der Menge C mehr sein, d.h.
y ∈ Σn \ C. Fehler führen also unter gewissen Bedingungen aus
der Menge C hinaus, was zur Folge hat, dass wir erkennen können,
ob Fehler bei der Übertragung des ursprünglichen Wortes c aufgetreten sind. Es ist dann sogar möglich, diese Fehler rückgängig zu
machen, d.h. das Codewort zu korrigieren.
Im folgenden werden wir klären, was die beiden Eigenschaften „gut im Raum verteilt“ und „eine nicht zu große Anzahl an
Fehlern“ bedeuten, um eine Fehlererkennung bzw. eine Fehlerkorrektur zu ermöglichen. Dazu betrachten wir die folgenden drei
Beispiele.
2
blockcodes und hamming-metrik
Beispiel 1. Wir betrachten den Nachrichtenraum Σ2 = {0, 1}2
mit Codierung 00 → 000, 01 → 011, 10 → 101, 11 → 110. Der
resultierende Code ist C1 = {000, 011, 101, 110} ⊆ Σ3 und enthält
alle Wörter der Länge drei mit einer geraden Anzahl von Einsen.
Entsteht bei der Übertragung eines Codewortes genau ein Fehler,
so ist die Anzahl der Einsen ungerade und das fehlerhafte Wort
liegt nicht mehr in C1 . Der Fehler kann also entdeckt werden.
Eine Korrektur des fehlerhaften Wortes ist jedoch nicht möglich,
da es keinen Anhaltspunkt gibt, in welcher Koordinate der Fehler
entstanden ist. Wird z.B. 011 durch einen Fehler zu 111, dann
wären 011, 101 und 110 entsprechende Kandidaten für das richtige
Codewort. Angenommen es treten genau zwei Fehler auf, so kann
dies nicht erkannt werden, da das Verändern eines Codewortes in
zwei Koordinaten erneut ein Codewort ergeben kann. z.B. kann
man durch Abändern des Codewortes 011 an den ersten zwei
Stellen das Codewort 101 erhalten.
Beispiel 2. Wir betrachten erneut den 2-dimensionalen Nachrichtenraum Σ2 = {0, 1}2 mit einer Einbettung in den 6-dimensionalen
Raum Σ6 : 00 → 000000, 01 → 111000, 10 → 000111, 11 → 111111.
Der Code ist C2 = {000000, 111000, 000111, 111111} ⊆ Σ6 . Man
erkennt, dass sich je zwei Codewörter an mindestens drei Stellen unterscheiden. Tritt bei der Übertragung eines Codewortes
genau ein Fehler auf, dann kann dies wieder erkannt werden, da
das resultierende fehlerhafte Wort kein Wort aus der Menge C2
ist. Des weiteren haben wir hier auch die Möglichkeit den Fehler
rückgängig zu machen. Man sucht einfach dasjenige Codewort,
welches zu dem empfangenen Wort die wenigsten Unterschiede
aufweist. Beispielsweise wird 101011 zu 101010 korrigiert. Treten
zwei Fehler bei der Übertragung auf, so wird erkannt, dass Fehler
aufgetreten sind, aber das genannte Korrekturverfahren würde das
falsche Codewort liefern.
Beispiel 3. Eine weitere Einbettung von Σ2 = {0, 1}2 in Σ5
liefert die Codierung 00 → 00000, 01 → 10110, 10 → 01011, 11 →
11101. Im resultierenden Code C3 = {00000, 10110, 01011, 11101}
unterscheiden sich je zwei Codewörter auch an mindestens drei
Stellen, d.h. analog wie im Beispielcode C2 können auch hier
maximal zwei Fehler erkannt und ein Fehler korrigiert werden.
3
blockcodes und hamming-metrik
Definition 2. Sei Σ eine endliche Menge. Ein Blockcode C (oder
kurz Code genannt) der Länge n ∈ N über Σ ist eine Teilmenge
von Σn . Die Elemente aus C heißen dabei Codewörter und der
Wert log|Σ| (|C|) definiert die Dimension des Codes.
Die Dimension log|Σ| (|C|) des Codes gibt an, wieviel Information mit dem Code übertragen werden kann. Anders ausgedrückt
gibt die Dimension des Codes die Anzahl der Zeichen über dem
Alphabet Σ an, die eine zu codierende Nachricht hat. Angenommen, wir bilden den Nachrichtenraum Σk injektiv auf einen Code
C der Länge n ab, dann gilt |C| = |Σ|k und die Dimension des
Codes ist log|Σ| (|C|) = k, somit gleich der Dimension des Nachrichtenraums.
Der Quotient von Dimension des Codes – also der Länge der
eigentlichen Nachricht – und der Länge des Codes gibt an, wie
groß der Anteil an reiner Information in einem Codewort ist, er
liefert also die Informationsrate. Der restliche Anteil, die „NichtInformation“ im Codewort, wird als Redundanz bezeichnet.
Definition 3. Für einen Code C ⊆ Σn ist R = log|Σ| (|C|)/n
die Informationsrate des Codes C. Der Wert 1 − R definiert die
Redundanz des Codes C.
Beispiel 4. Die Informationsrate von C1 = {000, 011, 101, 110} ist
R = 2/3 = 66%, d.h. 2 von 3 Bit sind reine Information. Für den
Code C2 = {000000, 111000, 000111, 111111} gilt R = 1/3 = 33%
und für den Code C3 = {00000, 10110, 01011, 11101} beträgt die
Informationsrate R = 2/5 = 40%.
Wir haben den Prozessablauf der Kanalcodierung kennengelernt. Zuerst wird ein Nachrichtenwort x ∈ Σk auf ein Codewort
c ∈ Σn abgebildet, wobei k ≤ n. Die resultierende Codemenge
C ⊆ Σn erfüllt |C| = |Σ|k . Das Codewort c ∈ C wird über den
störungsanfälligen Kanal gesendet und y ∈ Σn wird empfangen.
Gilt y ∈ Σn \ C, so kann erkannt werden, dass Fehler aufgetreten
sind. Möchte man nun auch die Fehler korrigieren, so ordnen wir
das fehlerhaft empfangene Wort aus Σn \ C dem nächstgelegenen
Codewort aus C zu.
Es ist sofort einsichtig, dass diese Art der Fehlerkorrektur nur
dann funktionieren kann, wenn das gesendete Codewort c und das
4
blockcodes und hamming-metrik
5
empfangene fehlerhafte Wort y nicht zu weit von einander entfernt
liegen. Treten zu viele Fehler auf, dann kann passieren, dass y
näher an einem anderen Codewort c liegt und der Algorithmus
damit nicht das ursprüngliche richtige Codewort c liefert, sondern
das falsche Codewort c .
Im folgenden werden wir diese Überlegungen mathematisch
präzise formalisieren und untersuchen, unter welchen Bedingungen
bei der Übertragung entstandene Fehler korrigiert werden können.
Zunächst klären wir, was die Zuordnung zu dem „nächstgelegenen“
Codewort bedeutet. Dies impliziert einen Abstandsbegriff auf der
Menge Σn . Intuitiv haben wir bisher den Abstand zweier Wörter
als die Anzahl der Positionen, an denen sie sich unterscheiden,
definiert.
Definition 4. Für Vektoren y, y ∈ Σn ist der Hamming-Abstand
d(y, y ), oder auch die Hamming-Distanz genannt, definiert als die
Anzahl der Posititionen, an denen sich y und y unterscheiden:
d(y, y ) := |{i | yi = yi }|.
Desweiteren wird die Hamming-Distanz wt(y ) := d(y, 0) von y
zum Nullvektor 0 als das Hamming-Gewicht von x bezeichnet.
Beispiel 5. Für Σ = {0, 1} gelten d(1010101, 1010101) = 0 sowie
d(110, 101) = 2. Für das ternäre Alphabet gilt d(0121, 0212) = 3.
Die fundamentalen Eigenschaften eines Abstandsbegriffes,
einer so genannten Metrik, liefert das folgende Lemma. Metriken sind zweistellige Abbildungen, die positiv definit (1+2) und
symmetrisch (3) sind und die Dreiecksungleichung (4) erfüllen:
Lemma 1. Für y, y , y ∈ Σn gilt:
1. 0 ≤ d(y, y ) ≤ n,
2. d(y, y ) = 0 ⇐⇒ y = y ,
3. d(y, y ) = d(y , y ),
4. d(y, y ) ≤ d(y, y ) + d(y , y ).
Die Hamming-Distanz geht auf den Informationstheorektiker
Hamming zurück. Er führt den Begriff 1950 in seinem grundlegenden Artikel1 über die Hamming-Codes ein.
1
R. W. Hamming. Error
Detection and Error Correction Codes. The Bell
System Technical Journal,
XXIX(2):147–160, 1950
blockcodes und hamming-metrik
Eine sehr schnelle Methode den Abstand d(y, y ) zweier binärer
Vektoren y und y der Länge n zu bestimmen, ist der Ansatz nach
Wegner2 aus dem Jahre 1960. Anstatt immer die n Stellen von
y und y einzeln zu vergleichen, bestimmt man die Anzahl w der
von Null verschiedenen Stellen des XOR-verknüpften Vektors
z = y ⊕ y mittels folgenden Algorithmus, welcher eine Laufzeit
proportial zur Hamming-Distanz von y und y besitzt:
w := 0
while z > 0 do
w := w + 1
z : = z & (z − 1)
return w
Der Prozess der Fehlerkorrektur lässt sich nun mittels HammingMetrik formalisieren: Es handelt sich um die MinimaldistanzDecodierung.
1. Das ursprüngliche Codewort c ∈ C wird übermittelt.
2. Ein fehlerhaftes Wort y ∈ Σn \ C wird empfangen.
3. Ordne y einem Codewort c ∈ C zu, so dass d(c , y ) ≤ d(c , y )
für alle c ∈ C gilt.
Um der Bedingung für eine erfolgreiche Fehlerkorrektur, d.h.
dass c = c gilt, auf die Spur zu kommen, definieren wir die
Minimaldistanz eines Codes.
Definition 5. Die Minimaldistanz d(C ) eines Codes C ⊆ Σn ist
definiert durch d(C ) := min{d(c, c ) | c, c ∈ C, c = c }.
Ein erster naiver Ansatz zur Bestimmung der Minimaldistanz
eines Codes C, ist die Auswertung der Abstände aller möglichen
Zweierteilmengen von Codewörtern aus C. Der Aufwand für diese
Berechnung ist somit quadratisch O (|C|2 ).
Das folgende Theorem liefert nun die notwendigen Bedingungen für ein erfolgreiches Fehlererkennen bzw. -korrigieren.
Theorem 1. Sei C ⊆ Σn ein Code mit Minimaldistanz d = d(C ),
sei c ∈ C eine Codewort und sei y ∈ Σn ein übertragenes Wort.
Dann gilt:
2
P. Wegner. A Technique
for Counting Ones in a
Binary Computer. Communications of the ACM,
3(5):322, 1960
6
blockcodes und hamming-metrik
1. Sind in y maximal d − 1 Fehler aufgetreten, dann gilt y ∈ C und
es kann somit erkannt werden, dass Fehler aufgetreten sind.
2. Sind in y maximal t = (d − 1)/2 Fehler aufgetreten, so liefert
die Minimaldistanz-Decodierung das korrekte ursprüngliche
Codewort c.
Beweis. Wir definieren Kugeln in Σn . Für ein z ∈ Σn ist die
Kugel mit Radius t definiert als Bt (z ) := {y ∈ Σn | d(z, y ) ≤ t}.
1. Die erste Aussage lässt sich anhand der Abbildung 1 verifizieren. Innerhalb der Kugel Bd−1 (c) eines Codewortes c ∈ C
befinden sich keine weiteren Codewörter, da der minimale Abstand zum nächsten Codewort mindestens d beträgt. Wird c nun
in maximal d − 1 Zeichen verändert, so ist das resultierende y
innerhalb der Kugel Bd−1 (c), d.h. y kann kein Codewort sein, es
gilt y ∈ C. Dies kann erkannt werden.
2. Die Kugeln mit Radius t um die Codewörter sind alle disjunkt, wenn t = (d − 1)/2 gilt (siehe Abbildung 2), denn der
Radius ist dann echt kleiner als die Hälfte der Minimaldistanz.
Folglich wird ein y ∈ Bt (c) mit der Minimaldistanz-Decodierung
eindeutig dem Codewort c zugeordnet. Treten bei der Übermittlung eines Codewortes höchstens t Fehler auf, so ist die Zuordnung von y auf c korrekt.
Abbildung 1: Bis zu d − 1
Fehler können erkannt
werden.
7
blockcodes und hamming-metrik
Abbildung 2: Bis zu t =
d−1
Fehler können
2
korrigiert werden.
Beispiel 6. Sei C = {000000, 010101, 101010, 111111} ein Code.
Um die Minimaldistanz zu berechnen, müssen wir alle Distanzen
zwischen den paarweise verschiedenen Codewörter auswerten:
d(000000, 010101) = 3,
d(000000, 101010) = 3,
d(000000, 111111) = 6,
d(010101, 101010) = 6,
d(010101, 111111) = 3,
d(101010, 111111) = 3.
Der kleinste mögliche Abstand bestimmt die Minimaldistanz,
die in diesem Fall d = 3 ist. Es können bis zu zwei Fehler erkannt
und es kann ein Fehler korrigiert werden. Ist nun ein fehlerhaftes
Codewort gegeben, etwa y = 101110 ∈ Σ6 \ C, so können wir das
nächstgelegene Codewort bestimmen, indem wir die Distanz von y
zu allen Codewörtern berechnen:
d(000000, 101110) = 4,
d(010101, 101110) = 5,
d(101010, 101110) = 1,
d(111111, 101110) = 2.
Angenommen, es ist maximal ein Fehler aufgetreten, so liefert die
Fehlerkorrektur das Codewort 101010.
8
blockcodes und hamming-metrik
Um bei der Minimaldistanz-Decodierung zu einem empfangenen Wort das nächstgelegende Codewort zu bestimmen, müssen
alle Codewörter aus C ausprobiert werden, d.h. |C| Auswertungen
der Hamming-Distanz. Dieser Algorithmus stellt natürlich ein sehr
aufwändiges Verfahren zur Fehlerkorrektur dar. Im schlechtesten
Fall muss der komplette Code C durchlaufen werden. d.h. die
Zeitkomplexität ist O (|Σ|k ), wenn man annimmt, dass man mit C
den Nachrichtenraum Σk codiert. Für verschiedene Klassen von
Codes gibt es jedoch effiziente Decodierungsverfahren, bei denen
man zusätzliche Eigenschaften ausnutzen kann.
Bisher haben wir Nachrichtenwörter aus Σk einfach händisch
Codewörtern aus Σn zugeordnet – im Zweifel einfach mit einer
Tabelle. Diese Zuordnung ist natürlich sehr speicherintensiv
mit der Komplexität O (|Σ|k ). Ziel ist daher die Abbildung von
Nachrichtenwörtern auf Codewörter algorithmisch zu beschreiben.
Dabei ist zu beachten, dass die Umkehrung, d.h. die Abbildung
von Codewort auf das ursprüngliche Nachrichtenwort ebenfalls
effizient und gleichzeitig nicht speicheraufwändig implementierbar
ist. Mittels linearer Codes können diese Ziele erreicht werden.
Neben den Maximen der effizienten Codierung, Decodierung,
bzw. Fehlerkorrektur ist auch zu beachten, dass man Codes mit
möglichst großer Informationsrate und großer Minimaldistanz
erhält.
Literatur
[1] R. W. Hamming. Error Detection and Error Correction Codes.
The Bell System Technical Journal, XXIX(2):147–160, 1950.
[2] P. Wegner. A Technique for Counting Ones in a Binary
Computer. Communications of the ACM, 3(5):322, 1960.
9
Document
Kategorie
Internet
Seitenansichten
3
Dateigröße
320 KB
Tags
1/--Seiten
melden