CRC
Cyclic Redundancy Check
Ein Verfahren um aus einem beliebig langen Datenstrom eine Prüfsumme (Schlüssel) fester Länge zu erzeugen. Das besondere ist, dass die Prüfsumme sich schon bei minimalen Veränderungen in den Daten total verändert und es sehr unwahrscheinlich ist, dass zwei verschiedene Datenströme die gleiche Prüfsumme haben.
Der häufigste Einsatzzweck von CRC16 ist die Überprüfung von Daten auf Unversehrtheit in einem Speicher oder nach einer Datenübertragung.
CRC16 ist die häufigste Form. Es gibt jedoch auch weitere Verfahren, wie z.B. CRC8 oder CRC32.
Algorithmus
Der CRC Algorithmus ist relativ einfach zu bewerkstelligen und dennoch ein Mittel, um Daten bei ihrer Speicherung und/oder Übertragung wirkungsvoll auf Korrektheit zu prüfen!
Beim CRC Verfahren gibt es ein sogenanntes Generator-Polynom, welches bei Sender und Empfänger der Daten (Sender und Empfänger können auch ein und das selbe Gerät sein) bekannt sein muss. Je nach Bezeichnung des Verfahrens handelt es sich um unterschiedliche Länge dieses Generator-Polynoms. Zum Beispiel bedeutet CRC16, dass das Generator-Polynom vom Grad 16 ist.
Zur praktischen Anwendung dieses Verfahren:
- Die zu schützenden binären Daten werden mit dem Grad des Generator-Polynoms multipliziert (einfach gesagt, an die Daten werden entsprechend dem Grad des Generator-Polynoms NULLEN angehängt; z.B. 16 Nullen bei CRC16).
- Die durch 1. entstandene neuen binäre Zeichenkette wird durch das Generator-Polynom geteilt und der Rest wird ermittelt!
- Der Rest wird zu den binären Daten hinzugezählt.
Der Empfänger kann nun die erhaltenen Daten durch das Generator-Polynom teilen. Bleibt bei dieser Division 0 Rest sind die Daten korrekt übertragen worden. Ist der Rest ungleich 0, ist ein Fehler bei der Übertragung aufgetreten. Um die ursprünglichen Daten wieder zu erhalten (natürlich nur, falls sie korrekt übertragen wurden) müssen nur die letzten Stellen entfernt werden!
Beispiel
Das Generator-Polynom sei [math]\displaystyle{ x^5+x^2+x }[/math]. Dies entspricht der binären Zahl 100110. Jetzt ist natürlich auch noch ein binäre Zeichenkette notwendig, die unsere Daten darstellt. Beispielsweise 1110100111001 (willkürlich gewählt).
Sender
- Die Daten werden mit [math]\displaystyle{ x^5 }[/math] multipliziert (5 Nullen anhängen):
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0
- Die Daten müssen jetzt durch das Generator-Polynom dividiert und somit der Rest ermittelt werden:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0
1 0 0 1 1 0
0 1 1 1 0 0 0
1 0 0 1 1 0
0 1 1 1 1 0 1
1 0 0 1 1 0
0 1 1 0 1 1 1
1 0 0 1 1 0
0 1 0 0 0 1 1
1 0 0 1 1 0
0 0 0 1 0 1 0 0 1
1 0 0 1 1 0
0 0 1 1 1 1 0 0
1 0 0 1 1 0
0 1 1 0 1 0 0
1 0 0 1 1 0
0 1 0 0 1 0 0
1 0 0 1 1 0
0 0 0 0 1 0 0
Der Rest ist also 100.
- Nun muss nur noch der Rest zu den Daten hinzugezählt werden:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0
Empfänger
ohne Fehler
Der Empfänger ermittelt seinerseits jetzt natürlich ebenfalls aus diesen empfangenen Daten den Rest:
- Rest ermitteln
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0
1 0 0 1 1 0
0 1 1 1 0 0 0
1 0 0 1 1 0
0 1 1 1 1 0 1
1 0 0 1 1 0
0 1 1 0 1 1 1
1 0 0 1 1 0
0 1 0 0 0 1 1
1 0 0 1 1 0
0 0 0 1 0 1 0 0 1
1 0 0 1 1 0
0 0 1 1 1 1 0 0
1 0 0 1 1 0
0 1 1 0 1 0 1
1 0 0 1 1 0
0 1 0 0 1 1 0
1 0 0 1 1 0
0 0 0 0 0 0 0
Der Rest ist also wirklich 0.
mit Fehler
Addieren wir beispielsweise 1100 zu den Daten hinzu bekommen wir also:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0
1 1 0 0
1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0
Jetzt führen wir die Division erneut durch und sehen uns den Rest an:
- Rest ermitteln
1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0
1 0 0 1 1 0
0 1 1 1 0 0 0
1 0 0 1 1 0
0 1 1 1 1 0 1
1 0 0 1 1 0
0 1 1 0 1 1 1
1 0 0 1 1 0
0 1 0 0 0 1 1
1 0 0 1 1 0
0 0 0 1 0 1 0 0 1
1 0 0 1 1 0
0 0 1 1 1 1 1 0
1 0 0 1 1 0
0 1 1 0 0 0 0
1 0 0 1 1 0
0 1 0 1 1 0 0
1 0 0 1 1 0
0 0 1 0 1 0 0
Somit bleibt also 10100 als Rest und dies bedeutet, dass die Daten nicht korrekt beim Empfänger angekommen sind!