5.5 – Codesicherung II

 

Aufgabe 5.5 – Codesicherung II

  1. Wie viele 4Bit Codewörter lassen sich mit konstanter Hamming-Distanz D = 2 kodieren?
  2. Überlegen Sie sich, warum sich bei einem Code mit Hamming-Distanz D = 3 2Bit-Fehler erkennen, aber nur 1Bit Fehler korrigieren lassen.

    Hinweis: Sie können annehmen, dass 1Bit-Fehler mit einer höheren Wahrscheinlichkeit auftreten als 2Bit-Fehler. Denken Sie an “Umgebungen” eines Codewortes mit der Hamming-Metrik.

  3. Wie viele fehlerhafte Bits lassen sich bei einem Code mit Hamming-Distanz D = 4 bzw. D = 5 korrigieren?

Lösung

a)

Um die Anzahl zu bestimmen, können wir alle Möglichkeiten von 4Bit-Kombinationen aufschreiben:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Wir markieren nun die erste Zahl und suchen die erste Zahl, die die Hemming-Distanz 2 hat:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Nun müssen wir weitere Zahlen finden, die zu beiden bereits gefundenen die Distanz 2 hat:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Dies sind alle Möglichkeiten. 1001 scheidet z.B. aus, da es zu 0110 die Distanz 4 hat und nicht 2. Die Anzahl der 4-Bit Codewörter, bei denen die Hammingdistanz konstant 2 sein soll, ist also 4. Man beachte, dass dies unabhängig davon ist, mit welchem Codewort man anfängt zu filtern.

b)

Wir stellen uns für n = 3 den Vektorraum in kartesischen Koordinaten vor.

Die einzigen beiden Vektoren mit Hemming-Distanz 3 sind 000 und 111. Die Umgebungen dieser Vektoren sind:

U\left( {000} \right) = \left\{ {v:D\left( {000,v} \right) = 1} \right\} = \left\{ {001,010,100} \right\}

U\left( {111} \right) = \left\{ {110,101,011} \right\}

codesicherung-redundanz-fehler-erkennen-korrigieren

Bei einem 1Bit Fehler landen wir also entweder in U\left( {000} \right) oder in U\left( {111} \right). Da die Schnittmenge dieser beiden Umgebungen leer ist, können wir daraus den fehlerfreien Vektor erkennen, der Fehler kann korrigiert werden.

Bei einem 2Bit Fehler ist diese Schnittmenge nicht mehr leer, es kann daher keine eindeutige Zuordnung zu dem fehlerfreien Vektor erfolgen, obwohl der Fehler erkannt wurde. Verallgemeinerung auf n-Bit Wörter:

V = {\left\{ {0,1} \right\}^n} ist der n-dim. Würfel im {\mathbb{R}^n}. Der Hamming-Abstand ist (siehe Aufgabe 3):

D\left( {x,y} \right): = \sum\limits_{i = 1}^n {\left| {{x_i}-{y_i}} \right|}

Sei G die Menge der gültigen Worte mit Hamming-Abstand D\left( {{g_1},{g_2}} \right) \geq 3\forall {g_1},{g_2} \in G. Die direkten Nachbarn von g \in G (Abstand 1) sind U\left( g \right) = \left\{ {v:D\left( {g,v} \right) = 1} \right\}.

Wegen der Dreiecksungleichung ist

{g_1},{g_2} \in G,\:\:{g_1} \ne {g_2}\:\:\: \Rightarrow \:\:\:U\left( {{g_1}} \right) \cap U\left( {{g_2}} \right) = \emptyset,

denn wäre

x \in U\left( {{g_1}} \right) \cap U\left( {{g_2}} \right),

so würde folgender Widerspruch entstehen:

3 \leq D\left( {{g_1},{g_2}} \right) \leq D\left( {{g_1},x} \right)+D\left( {x,{g_2}} \right) = 1+1

c)

Bei D = 4 sind auch nur 1Bit-Fehler korrigierbar, da es bei einem 2Bit-Fehler z.B. zu folgendem Fall kommen kann:

Zulässige Vektoren: 0000, 1111

Fehlerhafter Vektor: 0011

Der fehlerhafte Vektor kann nicht eindeutig einem der beiden zulässigen Vektoren zugeordnet werden, da er zu beiden die Distanz 2 hat. Bei D = 5 können 2Bit-Fehler korrigiert werden.

Allgemein braucht man D = 2k+1, um k-Bit Fehler korrigieren zu können.

Ähnliche Artikel

Kommentar verfassen