5.3 – Codesicherung

 
  1. Wie groß ist die minimale Hamming Distanz zwischen zwei aufeinander folgenden Codewörtern bei folgendem Code und was für Fehler lassen sich bei dieser Codierung erkennen, bzw. korrigieren?

    \begin{array}{*{20}{c}}{Zeichen} &\vline & {Code} \\ \hline a &\vline & {00000} \\ b &\vline & {00111} \\ c &\vline & {11001} \\ d &\vline & {11110} \\ \end{array}

  2. Berechnen Sie das Odd Paritärsbit zu folgenden Codewörtern:

    1010100
    0010101
    111
    111001

  3. Die folgenden Codewörter wurden bei einer Übertragung über ein Funknetz so empfangen. Vor dem Versenden wurde ihnen ein Even-Paritätsbit (Fett) hinzugefügt. Welche Wörter sind ungültig?

    000110110
    111111111
    010111011
    111100001
    000000000
    001100111

Lösung

a)

Wir befinden uns im Vektorraum V = {\left\{ {0,1} \right\}^n}, der aus n-Bit Wörtern besteht.

Für x,y \in V gilt:

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

Die Distanz ist also die Anzahl der unterschiedlichen Bits.

Für die Aufgabenstellung berechnen wir alle Distanzen:

D\left( {a,b} \right) = D\left( {b,a} \right) = \sum\limits_{i = 1}^n {\left| {{a_i}-{b_i}} \right|} = 0+0+1+1+1 = 3

D\left( {a,c} \right) = D\left( {c,a} \right) = 3

D\left( {a,d} \right) = D\left( {d,a} \right) = 4

D\left( {b,c} \right) = D\left( {c,b} \right) = 4

D\left( {b,d} \right) = D\left( {d,b} \right) = 3

D\left( {c,d} \right) = D\left( {d,c} \right) = 3

Es ist also {D_{\max }} = 4 und {D_{\min }} = 3

Es lassen sich 2Bit-Fehler erkennen, da der minimale Abstand zwischen sinnvollen Codes 3 ist. Allerdings können nur 1Bit-Fehler korrigiert werden.

Wenn z.B. 000000 fehlerhaft zu 10001 wird (2Bit Fehler), so kann zwar erkannt werden, dass dies ein Fehler ist, die Korrektur würde aber von 10001 nach 11001 erfolgen, da dies nur 1 Bit Unterschied ist.

b)

Wir müssen hier ein Bit anfügen, so dass die gesamte Anzahl der positiven Bits ungerade ist:

1010100-0
0010101-0
111-0
111001-1

c)

Hier müssen wir prüfen, ob die Anzahl der positiven Bits gerade ist.

000110110 ist korrekt
111111111 ist fehlerhaft
010111011 ist korrekt
111100001 ist fehlerhaft
000000000 ist korrekt
001100111 ist fehlerhaft

Ähnliche Artikel

Kommentar verfassen