Guten Tag,
ich beschäftige mich derzeit mit dem CRC-Verfahren.
Ich habe verstanden, dass die Eingangsdaten als eine 'große Zahl'
interpretiert und modulo dem Generatorpolynom gerechnet wird. Das
Ergebnis ist dann der Prüfwert.
Leider habe ich nicht verstanden, wie der Algorithmus über
Bitschiebereien, den Modulo berechnet.
Hier ist 'der Algorithmus':
1 | Schieberegister := 0000… (Startwert)
|
2 | solange Bits im Datenstrom verbleiben:
|
3 | falls das am weitesten links stehende Bit vom Schieberegister
|
4 | ungleich dem nächsten Bit (z. B. beginnend mit dem MSB, und dann jeweils eins weiter rechts pro Iteration) aus dem Datenstrom ist:
|
5 | Schieberegister := (Schieberegister linksschieben um 1, rechtes Bit 0)
|
6 | xor CRC-Polynom (ohne den Term vom Grad n+1)
|
7 | andernfalls:
|
8 | Schieberegister := Schieberegister linksschieben um 1, rechtes Bit 0
|
9 | nächstes Bit im Datenstrom
|
10 | Schieberegister enthält das Ergebnis.
|
Quelle:
https://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung#Umsetzung
Man könnte den umgangssprachlich auch folgendermaßen formulieren:
1 | (1) Schieberegister = 0
|
2 | (2) Takte ein Bit des Bitstromes (von rechts nach links) in das Schieberegister ein.
|
3 | (2a) Ist links ein '1'-Bit herausgefallen, dann XOR'e das SR mit dem Gen-Polynom
|
4 | (3) Wiederhole (2) bis keine Daten mehr vorhanden sind
|
5 | Der CRC-Wert (Ganzahldivisionsrest) steht nun im Schieberegister.
|
Nur warum führt obiger Algo dazu, den Modulo eines Bitstroms (gegen ein
Generator-Polynom) zu berechnen?
