Der binäre Code ist sehr praktisch bei der Verwendung von elektronischen Geräten wie dem 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 Übertragung von Daten über eine weite Strecke. Daher ist bei manchen Anwendungen nötig, die Daten auf ihre Gültigkeit zu überprüfen (im professionellen, Bank-, und Industriebereichen, wenn Vertrauen oder Sicherheit wichtig sind,...).
Deswegen gibt es Mechanismen, die dafür sorgen, dass die Daten ein bestimmtes Niveau anIntegritä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 :
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).
Inzwischen wurden weiter verbesserte Fehlersuchsysteme entwickelt, diese Codes heißen :
Die Paritätskontrolle (manchmal VRC, genannt, für Vertical Redundancy Check oder Vertical Redundancy Checking) ist eines der einfachsten Kontrollsystemen. 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...).
Die Kreuzparitätskontrolle (auch genannt mehrdimensionale Paritätskontrolle oder Longitudinal Redundancy Check, geschrieben LRC) 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 :
| Buchstabe | ASCII-Code (auf 7 Bits) | Paritätsbit (LRC) |
|---|---|---|
| H | 1001000 | 0 |
| E | 1000101 | 1 |
| L | 1001100 | 1 |
| L | 1001100 | 1 |
| 0 | 1001111 | 1 |
| VRC | 1000010 | 0 |
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 eingesetzte Methode zur Fehlersuche in der Telekommunikation.
Die zyklische Redundanzkontrolle ,schützt Datenblocks, genannt Frames ( Jedem Frame ist ein Datenblock zugeordnet, der Kontrollcode heißt (manchmal fälschlicherweiseCRC genannt oderFCS fürFrame Check Sequence bei Codes mit 32 bits). DerCRC Code enthält redundante Elemente vis-à-vis des Frames, dadurch können Fehler entdeckt, aber auch repariert werden.
Das Prinzip desCRC 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 vonn 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 (genanntGenerator-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.
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 Poynom-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 NachrichtM von 16 Bits : 1011 0001 0010 1010 (geschriebenB1 im Hexadezimalcode). Nehmen wir G(X) = X3 + 1 (im Binärcode dargestellt von1001). Da G(X) von3 Grad ist, fügt man4 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
Die am häufigsten verwendeten Generator-Polynome sind :
