CRC (Cyclic Redundancy Check, Zyklische Redundanzprüfung)

Was ist CRC (Cyclic Redundancy Check) oder zyklische Redundanzprüfung?

CRC (Cyclic Redundancy Check) oder deutsch zyklische Redundanzprüfung ist eine Methode zur Erkennung von Fehlern bei der digitalen Datenübertragung und Datenspeicherung. Es handelt sich um einen Algorithmus, der eine Prüfsumme (Checksum) für einen Datenblock berechnet. Diese Prüfsumme wird zusammen mit den Daten übertragen oder gespeichert und kann später verwendet werden, um sicherzustellen, dass die Daten während der Übertragung oder Speicherung nicht beschädigt wurden.

Wie funktioniert CRC?

Ein sendendes Gerät berechnet für einen zu übertragenden Datenblock mittels eines vordefinierten Polynoms (zum Beispiel 16, 32 oder 64 Bit) eine Prüfsumme, den sogenannten CRC-Wert. Dieser wird an die Daten angehängt und mit übertragen. Der Empfänger führt die gleiche Berechnung mit dem gleichen Polynom durch und prüft seinen berechneten CRC-Wert mit dem empfangenen Wert. Stimmen beide Werte überein, gilt die Übertragung als fehlerfrei. Bei Abweichungen kann der Sender über den Fehler informiert werden, damit er den Datenblock erneut sendet.

Wo wird CRC eingesetzt?

Der CRC wird in vielen technischen Bereichen zur Sicherung der Datenintegrität eingesetzt, zum Beispiel:

• Netzwerk: Bei Ethernet, WLAN, USB und modernen Mobilfunkstandards wie 5G dient CRC der Fehlererkennung bei der Datenübertragung.
• Speichersysteme: CRC sichert die Datenintegrität in Speichermedien wie SSDs, Festplatten und RAID-Systemen.
• Serielle Kommunikation: Kommunikationsprotokolle wie RS-232, SDLC und CAN-Bus verwenden CRC, um Übertragungsfehler zu erkennen.
• Legacy-Systeme: CRC-4, ein Standard zur Fehlererkennung auf E1-Leitungen, wird hauptsächlich in älteren Telekommunikationssystemen verwendet.

Welche CRC-Varianten gibt es?

Es gibt verschiedene CRC-Versionen für unterschiedliche Anforderungen. Die Zahl hinter CRC- gibt die Anzahl der Bits an, die für das verwendete Polynom und die daraus resultierende Prüfsumme (CRC-Wert) verwendet werden. Sie bestimmt, wie groß das mathematische Polynom ist und wie viele Bits der CRC-Wert umfasst. Beispiele für aktuell verwendete CRC-Varianten sind:

• CRC-16: Ein 16-Bit-Polynom, das häufig in älteren oder einfacheren Protokollen verwendet wird. Es eignet sich besonders für Datenblöcke bis zu 4 KByte und erkennt zuverlässig Einzel- und Doppelbitfehler.
• CRC-32: Dieses 32-Bit-Polynom wird in modernen Anwendungen wie Ethernet, ZIP-Dateien und IP-Protokollen verwendet. Es bietet eine hohe Fehlererkennungsrate und ist für größere Datenmengen geeignet.
• CRC-64: Für sehr große Datenblöcke oder hochkritische Anwendungen wie in der Blockchain-Technologie wird CRC-64 verwendet.

Einschränkungen von CRC

Die zyklische Redundanzprüfung hat einige Beschränkungen. Mit ihr können Fehler zwar erkannt, aber nicht korrigiert werden. Zur Fehlerkorrektur ist eine zusätzliche Methode wie die Forward Error Correction (FEC) erforderlich. Darüber hinaus kann die CRC bei komplexen Fehlern, wie der gleichzeitigen Änderung mehrerer Bits, Fehler möglicherweise nicht erkennen.

Mathematische Darstellung am Beispiel von CRC-4

Mathematisch ausgedrückt erkennt ein 4-Bit-CRC, der einen Datenblock beliebiger Länge angewendet wird, jeden einzelnen Fehler, der nicht länger als 4 Bit ist, und einen Bruchteil von 1 - 2-n längeren Fehlern. Vereinfacht ausgedrückt ist der Prüfwert für einen 4-Bit-CRC gleich 4. Für diesen Wert sind mehrere CRCs mit jeweils unterschiedlichen Polynomen möglich.

Um einen CRC-Code zu spezifizieren und seinen Algorithmus zu implementieren, wird ein „Generator-Polynom“ definiert. Idealerweise sollte das Polynom die Fehlererkennungsfähigkeiten des Algorithmus maximieren und die Gesamtkollisionswahrscheinlichkeiten minimieren. Seine Länge ( das ist der größte Grad [Exponent] +1 eines beliebigen Terms) ist sein wichtigstes Merkmal.

CRC-4 verwendet ein Polynom vierten Grades:

• Polynomgrad: n = 4
• Anzahl der Terme: n+1 = 5
• Für die Codierung erforderliche Bits: n+1 = 5

Es gibt drei Möglichkeiten, ein Polynom als Ganzzahl auszudrücken: 0x3, 0xC und 0x9. Die ersten beiden sind Spiegelbilder in Binärdarstellung und stellen die im Code enthaltenen Konstanten dar. Die dritte ist die Zahl, die vom Autor Philip Koopman, Professor für Elektrotechnik und Informatik an der Carnegie Mellon University und CTO von Edge Case Research, beschrieben wurde.

Für ein Polynom kann x⁴+x+1 also wie in Abbildung 1 dargestellt transkribiert werden.