CRC-Code

Zyklische Redundanzprüfung per Polynomdivision — erkennt über 99,9 % aller Übertragungsfehler in einem Datenblock, lokalisiert sie aber nicht.

Der CRC-Code (Cyclic Redundancy Check) ist das Standardverfahren zur Fehlererkennung bei größeren Datenblöcken — von Ethernet-Frames über ZIP-Archive bis zu Speicherprotokollen. Anders als der Hamming-Code korrigiert CRC keine Fehler, sondern erkennt sie nur — dafür mit einer Zuverlässigkeit von über 99,9 %, bei vergleichsweise geringem Rechenaufwand.

1. Grundprinzip: eine Rest-beim-Teilen-Prüfziffer

Die Grundidee lässt sich ganz ohne Formeln fassen: Teilt man zwei ganze Zahlen, bleibt meist ein Rest übrig ($17 : 5 = 3$ Rest $2$). CRC nutzt genau diesen Rest als Prüfsumme — nur dass nicht mit gewöhnlichen Zahlen, sondern mit Bitfolgen "geteilt" wird. Sender und Empfänger einigen sich vorab auf eine feste Bitfolge, den Generator. Der Sender hängt an seine Nachricht so viele Bits an, dass die Nachricht exakt ohne Rest durch den Generator teilbar wird — diese angehängten Bits sind der CRC-Wert. Der Empfänger teilt das empfangene Paket erneut durch denselben Generator: Bleibt kein Rest, ist (mit sehr hoher Wahrscheinlichkeit) nichts passiert; bleibt ein Rest übrig, muss unterwegs ein Bit gekippt worden sein.

Formal wird der Bitblock dazu als Polynom über GF(2) behandelt (Koeffizienten nur 0 oder 1, Addition = XOR statt gewöhnlicher Addition) — das ist nur eine andere Schreibweise für dieselbe Bitfolge, keine inhaltlich neue Idee. Ein $k$-Bit-Nachrichtenblock $b_{k-1} \dots b_1 b_0$ entspricht dem Polynom:

$$M(x) = b_{k-1}x^{k-1} + b_{k-2}x^{k-2} + \dots + b_1 x + b_0$$

Sender und Empfänger einigen sich vorab auf ein festes Generatorpolynom $G(x)$ vom Grad $r$ — die formale Entsprechung des oben beschriebenen Generators, also einfach die feste Bitfolge (als Polynom geschrieben), durch die geteilt wird. Der Name kommt daher, dass $G(x)$ zugleich alle gültigen Codewörter erzeugt: Ein Codewort ist genau dann gültig, wenn es ein Vielfaches von $G(x)$ ist (also ohne Rest durch $G(x)$ teilbar) — $G(x)$ "erzeugt" damit die komplette Menge zulässiger Codewörter. Die Kodierung läuft in drei Schritten:

$M(x)$ mit $x^r$ multiplizieren (entspricht: $r$ Nullen anhängen) — das schafft Platz für die Prüfbits, ohne die Nachricht selbst zu verändern.
$x^r \cdot M(x)$ durch $G(x)$ dividieren (Polynomdivision über GF(2), also mit XOR statt Subtraktion). Der Quotient wird verworfen, nur der Rest $B(x)$ zählt — das ist die CRC-Prüfsumme.
$B(x)$ an $M(x)$ anhängen (die zuvor angehängten Nullen werden durch den Rest ersetzt): $T(x) = x^r \cdot M(x) + B(x)$.

Der Trick: $T(x)$ ist per Konstruktion exakt durch $G(x)$ teilbar (Rest 0) — schließlich wurde $B(x)$ genau so gewählt, dass es den ursprünglichen Rest auf 0 ergänzt. Der Empfänger muss deshalb nur eine einzige Prüfung durchführen: $T(x)$ durch $G(x)$ teilen; bleibt ein Rest ungleich 0, ist beim Transport ein Fehler passiert.

2. Kodierung: ein durchgerechnetes Beispiel

Bsp.: Für die 9-Bit-Nachricht 101001101 und das Generatorpolynom $G(x) = x^5+x^2+x+1$ (Bitfolge 100111, $r=5$) ergibt die Polynomdivision den Rest $B(x) = \texttt{11010}$. Das gesendete Codewort lautet damit $T(x) = \texttt{10100110111010}$ (14 Bit) — division durch $G(x)$ liefert für dieses $T(x)$ exakt den Rest 0.

Ausgeschrieben: $M(x) = x^8+x^6+x^3+x^2+1$ (aus den gesetzten Bits der Nachricht). Multipliziert mit $x^5$ ergibt sich $x^{13}+x^{11}+x^8+x^7+x^5$, als Bitfolge 10100110100000 — die 9 Nachrichtenbits gefolgt von 5 Nullen. Die Division dieser 14-Bit-Zahl durch 100111 liefert den Rest 11010, der die 5 angehängten Nullen ersetzt.

3. Empfangsseitige Prüfung

Bsp.: Division von $T(x) = \texttt{10100110111010}$ durch $G(x) = \texttt{100111}$ ergibt den Rest 00000 — kein Fehler erkannt. Wird testweise Bit 5 (0-indiziert: Index 4) von $T(x)$ gekippt, ändert sich der Rest auf 11001 — ungleich 0, ein Fehler wird zuverlässig erkannt.

Genau hier zeigt sich der zentrale Unterschied zum Hamming-Code: Welches Bit gekippt wurde, verrät der Rest nicht — nur dass überhaupt einer gekippt wurde. Der Simulator unten macht diesen Unterschied direkt erfahrbar.

Simulator: Polynomdivision, Codewort und Fehlererkennung

Nachricht und Generatorpolynom sind frei editierbar (nur 0/1). Das Codewort $T(x)$ wird automatisch berechnet. Auf ein Bit im Codewort klicken simuliert einen Übertragungsfehler — der Empfänger erkennt ihn am Rest ungleich 0, kann ihn aber (im Gegensatz zum Hamming-Simulator) nicht lokalisieren.

Nachricht $M$ (Bits):

Generatorpolynom $G$:

Rest / CRC $B(x)$:

–

Codewort $T(x)$ (auf ein Bit klicken, um einen Fehler zu simulieren):

Kein Fehler erkannt (Rest = 0).

4. Gängige Generatorpolynome

Reale CRC-Verfahren nutzen standardisierte Generatorpolynome, die für gute Fehlererkennungseigenschaften bei typischen Blockgrößen optimiert sind:

Code	Generatorpolynom $G(x)$	typischer Einsatz
CRC-12	$x^{12}+x^{11}+x^3+x^2+x+1$	Blöcke mit 6-Bit-Zeichen
CRC-16	$x^{16}+x^{15}+x^2+1$	Blöcke mit 8-Bit-Zeichen (u. a. Modbus)
CRC-CCITT	$x^{16}+x^{12}+x^5+1$	Blöcke mit 8-Bit-Zeichen (u. a. XMODEM, Bluetooth)
CRC-32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$	Ethernet-FCS, ZIP/gzip, PNG

Je höher der Grad $r$ des Generatorpolynoms, desto mehr Prüfbits werden angehängt (Overhead) — dafür sinkt die Wahrscheinlichkeit, dass ein Übertragungsfehler zufällig genau ein Vielfaches von $G(x)$ ergibt und damit unerkannt bleibt. CRC-32 erkennt praktisch alle Einzel- und Doppelfehler sowie alle Burst-Fehler bis zur Länge 32 mit Sicherheit.

5. Praktischer Einsatz

Packet Radio und APRS (AX.25): Das AX.25-Protokoll — Grundlage von Packet Radio und APRS — hängt an jeden Frame exakt die CRC-CCITT-Prüfsumme aus Abschnitt 4 an, mit dem Generatorpolynom $x^{16}+x^{12}+x^5+1$. TNCs und Software-Modems (z. B. Direwolf) verwerfen Frames mit fehlerhafter Prüfsumme automatisch, statt sie mit falschem Inhalt weiterzureichen.

Ethernet (Frame Check Sequence): Jeder Ethernet-Frame trägt am Ende eine CRC-32-Prüfsumme über den kompletten Frame-Inhalt. Schlägt die Prüfung fehl, wird der Frame stillschweigend verworfen — auf höherer Protokollebene (TCP) sorgt dann ein ARQ-Mechanismus für die Neuübertragung.

Dateiformate (ZIP, gzip, PNG): Diese Formate hängen eine CRC-32-Prüfsumme an komprimierte Datenblöcke an, um beim Entpacken stille Datenkorruption zu erkennen — etwa durch einen fehlerhaften Datenträger oder eine unterbrochene Übertragung.

Speicherprotokolle und serielle Busse (u. a. Modbus, CAN-Bus): Kurze, standardisierte CRC-Varianten (CRC-16, CRC-CCITT) prüfen einzelne Telegramme, bevor ein Steuerungssystem sie verarbeitet.

6. Grenzen

Nur Erkennung, keine Korrektur: Ein CRC-Fehlschlag sagt nichts über die Fehlerposition aus (siehe Abschnitt 3) — nutzbar nur in Systemen mit Rückkanal für eine Neuübertragung (ARQ) oder wo Datenverlust akzeptabel ist (z. B. Frame verwerfen).
Kein Schutz gegen absichtliche Manipulation: CRC ist ein linearer Code ohne kryptographischen Schlüssel — anders als eine Prüfsumme mit Geheimnis (HMAC) lässt sich ein CRC-korrekter, aber inhaltlich manipulierter Block gezielt konstruieren. Für Datenintegrität gegen einen Angreifer ist CRC ungeeignet, nur gegen zufällige Übertragungsfehler.
Erkennungsgüte hängt vom gewählten Polynom ab: Ein schlecht gewähltes $G(x)$ kann bestimmte Fehlermuster (z. B. bestimmte Burst-Längen) systematisch übersehen — die in Abschnitt 4 gelisteten Standard-Polynome sind deshalb sorgfältig für ihre jeweilige Blockgröße ausgewählt, kein beliebiges Polynom vom passenden Grad liefert dieselbe Erkennungsgüte.