CRC – Cyclic Redundancy Check
Abkürzung: CRC
Die zyklische Redundanzprüfung ist ein Verfahren, mit dem sich Übertragungsfehler erkennen lassen. Der Sender berechnet aus den Daten einen Prüfwert und hängt ihn an, der Empfänger rechnet nach und vergleicht. Weichen die Werte ab, wurde unterwegs etwas verändert.
Wie der CRC-Prüfwert entsteht
Die Daten werden als eine sehr lange Binärzahl aufgefasst und durch eine festgelegte zweite Zahl geteilt — das Generatorpolynom. Interessant ist nicht das Ergebnis der Division, sondern der Rest, und der ist der Prüfwert.
Die Rechnung ist dabei keine gewöhnliche Division: Sie arbeitet ohne Übertrag, Addition und Subtraktion sind dieselbe Operation. Das klingt umständlich, hat aber einen praktischen Grund — dieses Rechenwerk besteht aus Schieberegistern und ein paar Verknüpfungen und lässt sich in Hardware mit minimalem Aufwand bauen. Deshalb sitzt die Prüfung in jedem Netzwerkchip und kostet keine messbare Zeit.
Der Empfänger kann auf zwei Wege prüfen: nachrechnen und vergleichen, oder die empfangenen Daten samt angehängtem Prüfwert durch dasselbe Polynom teilen — bei einer fehlerfreien Übertragung bleibt dann null übrig.
Welche Fehler ein CRC erkennt
Die Stärke des Verfahrens liegt nicht in der Länge des Prüfwerts allein, sondern in der Wahl des Polynoms. Gängige Polynome sind daraufhin ausgelegt, genau die Fehlerarten zu erfassen, die auf einer Leitung tatsächlich vorkommen:
Jeder einzelne gekippte Bit wird erkannt, ohne Ausnahme.
Jede ungerade Anzahl gekippter Bits wird erkannt, wenn das Polynom entsprechend gewählt ist.
Zusammenhängende Störungen — ein kurzer Störimpuls, der mehrere aufeinanderfolgende Bits trifft — werden bis zu einer Länge erkannt, die der Länge des Prüfwerts entspricht. Das ist der wichtigste Fall, weil Störungen auf Leitungen fast immer so aussehen: nicht einzelne verstreute Bits, sondern ein kurzer Einbruch.
Längere Störungen werden mit sehr hoher Wahrscheinlichkeit erkannt. Bei einem 32 Bit langen Prüfwert bleibt rechnerisch etwa eine von vier Milliarden solcher Störungen unentdeckt.
Was ein CRC nicht leistet
Er korrigiert nicht. Das Verfahren sagt, dass ein Fehler vorliegt, nicht wo er passiert. Der fehlerhafte Rahmen wird verworfen; für die Wiederholung sind die höheren Schichten zuständig.
Er schützt nicht gegen Manipulation. Das ist der wichtigste Punkt und wird regelmäßig falsch verstanden. Die Rechnung ist öffentlich bekannt und umkehrbar: Wer Daten verändert, kann den passenden Prüfwert ohne Weiteres mitberechnen — und sogar die Änderung so wählen, dass der alte Prüfwert weiterhin stimmt. Gegen absichtliche Veränderung braucht es einen kryptografischen Nachweis, keine Prüfsumme.
Er sagt nichts über die Ursache. Ein erkannter Fehler kann von einem gestörten Kabel, einem defekten Anschluss, einer schlechten Steckverbindung oder einem fehlerhaften Chip stammen.
Was CRC-Fehler in der Praxis bedeuten
Der Fehlerzähler an einem Port ist eines der aussagekräftigsten Werkzeuge der Fehlersuche, wenn man zwei Dinge beachtet:
Die Zahl allein genügt nicht, es zählt die Rate. Ein Port mit zwanzig Fehlern seit dem letzten Neustart vor einem Jahr ist unauffällig. Zwanzig Fehler in einer Minute sind ein Befund. Der Zähler muss also zweimal gelesen und ins Verhältnis zur übertragenen Menge gesetzt werden.
Die Seite, an der gezählt wird, zeigt auf die Ursache. Fehler werden dort erkannt, wo der Frame ankommt. Steigt der Zähler nur an einem Ende, liegt die Störung auf dem Weg dorthin oder am sendenden Gerät; steigt er an beiden, spricht das für die Strecke selbst.
Typische Ursachen in der Reihenfolge ihrer Häufigkeit: eine schlechte Steckverbindung, ein zu scharf gebogenes oder gequetschtes Kabel, eine überlange Strecke, eine Einstreuung durch parallel geführte Starkstromleitungen — und bei Glasfaser verschmutzte Steckerflächen.
Ein Sonderfall ist der Duplex-Mismatch: Dort treten Prüfsummenfehler auf einer Seite auf, obwohl die Leitung in Ordnung ist.
Wo der Prüfwert gespeichert ist
Bei Ethernet steht er am Ende des Rahmens, in den letzten vier Byte, und heißt dort Rahmenprüfsumme. Diese Position hat eine Folge, die das Weiterleitungsverhalten von Switches bestimmt: Ein Gerät, das einen Rahmen weiterleitet, bevor er vollständig eingetroffen ist, hat den Prüfwert noch nicht gesehen und kann ihn nicht auswerten.
Deshalb hängt die Wahl des Weiterleitungsverfahrens unmittelbar daran: Wer prüfen will, muss warten.
Abgrenzung
Das Paritätsbit erkennt nur eine ungerade Anzahl gekippter Bits und versagt bei zwei gleichzeitigen. Es ist der einfachste Vorläufer.
Die Prüfsumme von IP, TCP und UDP ist eine Summenbildung über 16-Bit-Wörter und deutlich schwächer: Sie erkennt bestimmte Vertauschungen nicht. Sie ersetzt den CRC nicht, sondern ergänzt ihn für Fehler, die nicht auf der Leitung, sondern in Geräten entstehen.
Ein kryptografischer Hashwert ist gegen absichtliche Veränderung ausgelegt, kostet aber erheblich mehr Rechenaufwand.
Vorwärtsfehlerkorrektur geht einen Schritt weiter und fügt genug Redundanz hinzu, um Fehler zu reparieren statt sie nur zu melden — auf Funkstrecken und in Glasfasersystemen üblich, wo eine Wiederholung zu teuer wäre.
Quellen
- IEEE Std 802.3: Ethernet, Abschnitt zur Frame Check Sequence
- ITU-T V.41: Code-independent error-control system
- ISO/IEC 13239: HDLC-Prozeduren