Fehlerkorrektur

Um Bitfehler nicht nur erkennen, sondern auch korrigieren (d. h. lokalisieren) zu können, muß der Hammingabstand auf h >= 3 erhöht werden. Beispiel h = 3:

O: gültiges Codewort
X: ungültiges Codewort

Ein Bitfehler führt zu einem ungültigen Codewort, das sich vom verfälschten Codewort in nur einem Bit unterscheidet. Zu allen anderen gültigen Codeworten hat es mindestens zwei Bit Unter- schied. Da die Auftrittswahrscheinlichkeit des 1-Bit-Fehlers in einem Codewort wesentlich höher ist, als bei zwei oder mehr Bit- fehlern, ordnet man das fehlerhafte Codewort dem ähnlichsten gültigen Codewort zu --> Fehlerkorrektur. Allgemein gilt für die Anzahl der korrigierbaren Fehler:

k = (h - 1)/2

Es existieren eine Reihe von Verfahren zur Fehlersicherung, z. B.

• Produktcodes (Block/Kreuzsicherung)

  Beispiel: Blockübertragung mit Kreuzsicherung

  

• Hamming-Codes (systematischer Aufbau, Auswertung Prüfmatrix)

  k = (h - 1)/2 = e/2

  k = Anzahl der korrigierbaren Fehler
  e = Anzahl der erkennbaren Fehler

  Hamming-Codes haben viel mehr Bits als notwendig und sind nach einem bestimmten System aufgebaut. So benötigen z. B. Codes mit 2, 3 und 4 Nutzbits noch zusätzliche 3 Prüfbits zur Korrektur eines Fehlers.

  Ein System zum Aufbau von Haming-Codes zur Korrektur eines Fehlers verwendet 4 Nutzbits (n1 - n4) + 3 Prüfbits (p1 - p3) --> 7 Bits:

  

  Berechnung der Prüfbits (Addition modulo 2):

  

  Beispiel: 8421-Code mit Hammingzusatz (h = 3):

                                          Wert | p1 p2 n1 p3 n2 n3 n4  
                                          -----+--------------------- 
                                             0 | 0  0  0  0  0  0  0 
                                             1 | 1  1  0  1  0  0  1 
                                             2 | 0  1  0  1  0  1  0 
                                             3 | 1  0  0  0  0  1  1 
                                             4 | 1  0  0  1  1  0  0 
                                             5 | 0  1  0  0  1  0  1
                                             6 | 1  1  0  0  1  1  0
                                             7 | 0  0  0  1  1  1  1 
                                             8 | 1  1  1  0  0  0  0
                                             9 | 0  0  1  1  0  0  1
                                         

  Gesendet wird: 1 0 0 0 0 1 1
  Empfangen wird: 1 0 0 0 0 0 1
  Am Empfangsort wird berechnet:

  

  empfangene Prüfbits: 1 0 0
  berechnete Prüfbits: 1 1 1
  Daraus ergibt sich:

   
                                                       1 0 0
                                                       1 1 1
                                                      -------
                                         (Antivalenz): 0 1 1 
                                                     LSB   MSB 
                                         

  "von rückwärts" gelesen: 1 1 0 --> Stelle 6 ist zu korrigieren.

• Blockprüfung mittels zyklischer Codes (CRC = cyclic redundancy check). Der gesamte Datenblock wird als ein sehr langes Codewort aufgefaßt und durch ein Generatorpolynom dividiert. Die technische Realisierung kann durch Schieberegister erfolgen.
  • Vorteil: geringe Prüfmatrixgröße
  • Sehr "sichere" Fehlererkennung
  • In der Datenübertragung weit verbreitet

Zurück

Inhaltsverzeichnis

Nächste

Diplomarbeiten zum Runterladen: