Die Fehlerkontrolle

November 2016

Die Fehlerkontrolle


Der binäre Code ist sehr praktisch bei der Verwendung von elektronischen Geräten wie Computer, bei denen Informationen durch die An- oder Abwesenheit eines elektronischen Signals codiert werden können.

Das elektrische Signal kann allerdings gestört werden (Verzerrung, Lärm), vor allem bei der Datenübertragung über eine weite Strecke. Daher ist es bei manchen Anwendungen nötig, die Daten auf ihre Gültigkeit zu überprüfen (in professionellen und Industriebereichen wo Vertrauen und Sicherheit wichtig sind).

Deswegen gibt es Mechanismen, die dafür sorgen, dass die Daten ein bestimmtes Niveau an Integrität haben, also dem Empfänger versichern, dass die empfangenen Daten den gesendeten Daten auch entsprechen. Es gibt zwei Arten, sich vor Fehlern zu schützen :

  • entweder, indem man das Übertragungsmedium schützt, also durch physischen Schutz. Eine gewöhnliche Verbindung hat in der Regel eine Fehlerquote zwischen 10-5 und 10-7.
  • oder durch den Einsatz von logischen Mechanismen zum Suchen und zur Korrektur von Fehlern.



Die meisten logischen Fehlerkontrollsysteme basieren auf zusätzlicher Information (man spricht von « Redundanz »), durch die die Gültigkeit der Daten überprüft werden kann. Diese zusätzliche Information nennt man Prüfsumme (auf Englisch checksum).

Fehlerkorrektur


Inzwischen wurden weiter verbesserte Fehlersuchsysteme entwickelt:

  • selbstkorrigierende Codes
  • selbstüberprüfende Codes

Die Paritätskontrolle


Die Paritätskontrolle (manchmal VRC, genannt, für Vertical Redundancy Check oder Vertical Redundancy Checking) ist eins der einfachsten Kontrollsysteme. Es wird ein zusätzliches Bit (genannt Paritätsbit) zu einer bestimmten Bitanzahl hinzugefügt, die Codewort genannt wird (meist 7 Bits, die mit dem Paritätsbit ein Byte bilden). Dessen Wert (0 oder 1) wird so gewählt, dass die Gesamtanzahl der Einser-Bits gerade ist. Genauer - es wird 1 hinzugefügt, wenn die Bitanzahl des Codeworts ungerade ist, und 0 im gegenteiligen Fall.

Betrachten wir das folgende Beispiel :




In diesem Beispiel ist die Anzahl der Datenbits mit 1 gerade, daher wird das Paritätsbit auf 0 gestellt. Im nächsten Beispiel hingegen ist die Anzahl der Datenbits ungerade, daher wird das Paritätsbit auf 1 gestellt :




Stellen wir uns nun vor, dass das Bit mit schwächstem Zustand (das ganz rechte) des vorherigen Bytes beeinträchtigt wird :




Das Paritätsbit entspricht dann nicht mehr der Parität des Bytes : ein Fehler wird gefunden.

Wenn allerdings zwei Bits (oder eine gerade Anzahl an Bits) bei der Übertragung zugleich verändert werden, wird kein Fehler entdeckt.




Da das Paritäts-Kontrollsystem nur die Fehler findet, die in ungerader Zahl auftreten, werden dadurch nur 50% der Fehler entdeckt. Dazu hat dieses Fehlersuchsystem den großen Nachteil, dass die gefundenen Fehler nicht korrigiert werden können (die einzige Möglichkeit besteht darin, die erneute Übermittlung des fehlerhaften Bytes zu fordern).

Kreuzparitätskontrolle


Die Kreuzparitätskontrolle (auch mehrdimensionale Paritätskontrolle oder Longitudinal Redundancy Check genannt, und LRC geschrieben) kontrolliert nicht die Integrität der Daten eines Zeichens, sondern die Integrität der Paritäsblits eines Zeichenblocks.

Nehmen wir an, « HELLO » ist die zu übertragende Botschaft im Standard ASCII-Code. So werden die Daten mit den Kreuzparitäts-Kontrollcodes übertragen :


BuchstabeASCII-Code
(auf 7 Bits)
Paritätsbit
(LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

Die zyklische Redundanzkontrolle


Die zyklische Redundanzkontrolle (geschrieben CRC, oder auf Englisch Cyclic Redundancy Check) ist ein Verfahren zur Integritätskontrolle der Daten, das wirksam und leicht durchzuführen ist. Es ist die am häufigsten in der Telekommunikation eingesetzte Fehlersuchmethode .

Prinzip


Die zyklische Redundanzkontrolle ,schützt Datenblocks, genannt Frames Jedem Frame ist ein Datenblock zugeordnet, der Kontrollcode heißt (manchmal fälschlicherweise CRC genannt oder FCS für Frame Check Sequence bei Codes mit 32 bits). Der CRC Code enthält redundante Elemente gegenüber dem Frame, dadurch können Fehler entdeckt, und repariert werden.

Contrôle de redondance cyclique (CRC)



Das Prinzip des CRC besteht darin, binäre Sequenzen wie binäre Polynome zu behandeln, also Polynome, deren Koeffizienten der binären Sequenz entsprechen. So kann die binäre Sequenz 110101001 in Polynom-Form folgendermaßen dargestellt werden :

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
das ist 
X8 + X7 + X5 + X3 + X0
oder auch 
X8 + X7 + X5 + X31



Auf diese Weise stellt der schwächste Zustand der Sequenz (das Bit ganz rechts) den 0-ten Grad des Polynoms dar (X0 = 1), das 4te Bit von rechts stellt den Grad 3 des Polynoms dar (X3)... Eine Sequenz von n Bits bildet also ein Polynom mit dem höchsten Grad n-1. Alle polynomen Ausdrücke werden dann mit modulo 2 verändert.

Bei diesem Fehlersuchmechanismus gibt es ein vorher festgelegtes Polynom (genannt Generator-Polynom und abgekürzt als G(X)), das dem Sender und Empfänger bekannt ist. Die Fehlersuche besteht für den Sender darin, einen Algorithmus auf den Bits des Frames auszuführen, um ein CRC zu erzeugen und diese zwei Element dem Empfänger zu übermitteln. Der Empfänger muss dann nur den selben Rechenvorgang durchführen, um zu überprüfen, ob der CRC gültig ist.

Praktische Anwendung


Nehmen wir an, M sei die Nachricht, die den Bits des zu versendenden Frames entspricht, und M(X) das zugehörige Polynom. Nennen wir die übertragene Nachricht M', also die ursprüngliche Nachricht, die mit einem CRC von n bits verbunden wurde. Der CRC ist M'(X)/G(X)=0. Der CRD Code gleicht also dem Rest der Polynom-Division von M(X) (dem zuvor n Null-Bits angefügt wurden, entsprechend der Länge des CRC) von G(X).

Am einfachsten lässt es sich an einem Beispiel darstellen : nehmen wir die folgende Nachricht M von 16 Bits : 1011 0001 0010 1010 (geschrieben B1 im Hexadezimalcode). Nehmen wir G(X) = X3 + 1 (im Binärcode dargestellt von 1001). Da G(X) von 3 Grad ist, fügt man 4 Null-Bits an M : 1,01100010010101E+19 an. Der CRC entspricht dem Rest der Division von M durch G :

10110001001010100000 
1001...,..,.,.,..... 
----...,..,.,.,..... 
 0100..,..,.,.,..... 
 0000..,..,.,.,..... 
 ----..,..,.,.,..... 
  1000.,..,.,.,..... 
  0000.,..,.,.,..... 
  ----.,..,.,.,..... 
  1000.,..,.,.,..... 
   1001,..,.,.,..... 
   ----,..,.,.,..... 
 1111..,.,.,..... 
 1001..,.,.,..... 
 ----..,.,.,..... 
  1100.,.,.,..... 
  1001.,.,.,..... 
  ----.,.,.,..... 
   1101,.,.,..... 
   1001,.,.,..... 
   ----,.,.,..... 
    1000.,.,..... 
    0000.,.,..... 
    ----.,.,..... 
    10001,..... 
  1001,.,..... 
  ----,.,..... 
  10000.,..... 
   1001.,..... 
   ---- 
    1111,..... 
    1001,..... 
    ----,..... 
     1100..... 
     1001..... 
     ----..... 
   1100.... 
   1001.... 
   ----.... 
    1010... 
    1001... 
    ----... 
     0110.. 
     0000.. 
     ----.. 
      1100. 
      1001. 
      ----. 
    1010 
    1001 
    ---- 
    0011



Um M' zu bilden, muss man lediglich den so erhaltenen CRC an die Bits des zu übertragenden Frames anhängen :

M' = 1011000100101010 + 0011 
M' = 10110001001010100011



Wenn der Empfänger nun die Division von M' durch G durchführt, erhält er Null als Rest, wenn die Übertragung fehlerfrei abgelaufen ist :

10110001001010100011 
1001...,..,.,.,...,, 
----...,..,.,.,...,, 
 0100..,..,.,.,...,, 
 0000..,..,.,.,...,, 
 ----..,..,.,.,...,, 
  1000.,..,.,.,..... 
  1001.,..,.,.,..... 
  ----.,..,.,.,..... 
   0010,..,.,.,..... 
   0000,..,.,.,..... 
   ----,..,.,.,..... 
 0101..,.,.,..... 
 0000..,.,.,..... 
 ----..,.,.,..... 
  1010.,.,.,..... 
  1001.,.,.,..... 
  ----.,.,.,..... 
   0110,.,.,..... 
   0000,.,.,..... 
   ----,.,.,..... 
    1101.,.,..... 
    1001.,.,..... 
    ----.,.,..... 
  1010,.,..... 
  1001,.,..... 
  ----,.,..... 
   0111.,..... 
   0000.,..... 
   ---- 
    1110,..... 
    1001,..... 
    ----,..... 
     1111..... 
     1001..... 
     ----..... 
   1100.... 
   1001.... 
   ----.... 
    1010... 
    1001... 
    ----... 
     0110.. 
     0000.. 
     ----,, 
      1101, 
      1001, 
      ----, 
    1001 
    1001 
    ---- 
       0

Generator-Polynome


Die am häufigsten verwendeten Generator-Polynome sind :

  • CRC-12 : X12 + X11 + X3 + X2 + X + 1
  • CRC-16 : X16 + X15 + X21
  • CRC CCITT V41 : X16 + X12 + X5 + 1

(Dieser Code wird vor allem in der Prozedur HDLC verwendet.)
  • CRC-32 (Ethernet) : = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1
  • CRC ARPA : X24 + X23 + X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1

Lesen Sie auch :


Error checking
Error checking
Verificación de errores
Verificación de errores
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
Il controllo degli errori
Il controllo degli errori
O controlo de erros
O controlo de erros
Das Dokument mit dem Titel « Die Fehlerkontrolle » aus CCM (de.ccm.net) wird zur Verfügung gestellt unter den Bedingungen der Creative Commons Lizenz. Sie dürfen das Dokument verwenden, verändern sowie Vervielfältigungen dieser Seite erstellen, unter den Bedingungen, die in der vorgenannten Lizenz erwähnt sind und unter der gleichzeitigen Bedingung, dass Sie im Rahmen Ihrer Verwendung, Veränderung oder Vervielfältigung nach außen hin klar und deutlich auf den Urheber (= de.ccm.net) des Dokuments hinweisen.