CRC / XOR / Modulo-2 Schriftliche-Division-Rechner

So verwenden Sie den CRC / XOR / Modulo-2-Rechner

Um eine CRC per Modulo-2-Division zu berechnen, folgen Sie diesen 4 Schritten:

• Geben Sie die Binärnachricht (Datenbits) in das erste Feld ein.
• Geben Sie das Generatorpolynom als Binärbits in das zweite Feld ein.
• Der Rechner hängt (n − 1) Nullbits an, wobei n die Generatorlänge ist.
• Klicken Sie auf Berechnen, XORen Sie die Nachricht herunter und lesen Sie den Rest als CRC.

Der Quotient wird in der CRC-Arbeit meist verworfen — der Rest ist die Prüfsumme, die vor der Übertragung an die Nachricht angehängt wird.

CRC und Modulo-2-Arithmetik

Eine zyklische Redundanzprüfung erkennt Übertragungsfehler, indem sie eine Nachricht als großes Binärpolynom behandelt und durch ein vereinbartes Generatorpolynom teilt. Die Division erfolgt in Modulo-2-Arithmetik (GF(2)), wo Addition und Subtraktion identisch sind und XOR entsprechen — es gibt keine Überträge oder Entlehnungen. Der Rest dieser Division ist die CRC. Teilt der Empfänger Nachricht plus CRC durch denselben Generator und bleibt Rest 0, wurde kein Fehler erkannt. Dieser Rechner bildet genau diesen bitweisen Prozess nach.

Wie Modulo-2-CRC-Division funktioniert

Der Rechner berechnet die CRC durch fünf interne Aktionen:

• Hängt (n − 1) Nullbits an die Nachricht an, wobei n die Anzahl der Generatorbits ist.
• Richtet den Generator unter das linkeste 1-Bit des aktuellen Rests aus.
• XORt den Generator in diese Bits (Modulo-2-Subtraktion ohne Entlehnung).
• Verschiebt zum nächsten führenden 1-Bit und wiederholt die XOR-Ausrichtung.
• Stoppt, wenn weniger Bits als der Generator übrig sind; diese Bits sind die CRC.

Jedes Quotientenbit ist 1, wo der Generator per XOR eingefügt wird, sonst 0 — für CRC zählt nur der finale Rest.

Formel für CRC-Division

Der CRC / XOR / Modulo-2-Rechner berechnet CRC = (M(x) · xⁿ⁻¹) mod G(x) in GF(2), wobei M(x) die Nachricht, G(x) der Generator mit n Bits ist und alle Additionen XOR sind. Der übertragene Rahmen ist M(x)·xⁿ⁻¹ + CRC, den G(x) exakt teilt. Beim Empfang bestätigt Rest 0 die Integrität.

CRC / XOR-Beispielaufgaben

Diese Beispiele zeigen Modulo-2-Division mit XOR in jedem Schritt.

Beispiel 1 — Nachricht 1101, Generator 101

1. Generatorlänge 3, also 2 Nullen anhängen: 1101 wird 110100.
2. 101 wiederholt in die führenden Bits XORen: 110100 → 011100 → 001000 → 000010.
3. Die letzten 2 Bits, 10, sind der CRC-Rest.

Beispiel 2 — Warum Subtraktion XOR ist

1. In Modulo-2 gilt 1 + 1 = 0 und 1 − 1 = 0, Addieren und Subtrahieren sind dieselbe Operation.
2. Diese Operation ist genau bitweises XOR, ohne Übertrag oder Entlehnung.
3. Jeder Divisionsschritt ist also ein XOR des Generators in die aktuellen Bits.

Beispiel 3 — Empfängerprüfung

1. Hängen Sie die CRC an die Nachricht an und teilen Sie durch denselben Generator.
2. XORen Sie wie zuvor herunter.
3. Rest 0 bedeutet, dass kein Fehler erkannt wurde.

Generatorlänge 3, also 2 Nullen anhängen: 1101 wird 110100.
101 wiederholt in die führenden Bits XORen: 110100 → 011100 → 001000 → 000010.
Die letzten 2 Bits, 10, sind der CRC-Rest.

In Modulo-2 gilt 1 + 1 = 0 und 1 − 1 = 0, Addieren und Subtrahieren sind dieselbe Operation.
Diese Operation ist genau bitweises XOR, ohne Übertrag oder Entlehnung.
Jeder Divisionsschritt ist also ein XOR des Generators in die aktuellen Bits.

Hängen Sie die CRC an die Nachricht an und teilen Sie durch denselben Generator.
XORen Sie wie zuvor herunter.
Rest 0 bedeutet, dass kein Fehler erkannt wurde.

Durchgerechnete CRC-Aufgaben

Wie berechnet man die CRC von 10110 mit Generator 1011?

Hängen Sie 3 Nullen an (Generatorlänge 4) zu 10110000 und XORen Sie herunter. Richten Sie 1011 unter jede führende 1 aus und XORen: 10110000 → 00100000 → nach weiteren XORs bilden die finalen 3 Bits den CRC-Rest. Der Rest wird an 10110 angehängt, sodass der volle Rahmen durch 1011 ohne Rest teilbar ist.

Warum bedeutet Rest 0, dass die Daten intakt sind?

Der Sender wählte die CRC so, dass der übertragene Rahmen ein exaktes Vielfaches des Generators ist. Jedes Vielfache von G(x) geteilt durch G(x) lässt Rest 0. Kippen Bits unterwegs, ist der Rahmen meist kein Vielfaches mehr; die Empfängerdivision liefert einen von Null verschiedenen Rest und meldet einen Fehler.

Häufige CRC / Modulo-2-Fehler

Modulo-2-CRC-Division führt zu 5 häufigen Fehlern:

• Normale Binärsubtraktion mit Entlehnungen statt XOR verwenden.
• Falsche Anzahl Nullbits anhängen (es müssen Generatorlänge minus eins sein).
• Den Generator unter eine 0 statt unter die führende 1 ausrichten.
• Überträge behandeln, als gäbe es sie in GF(2)-Arithmetik.
• Den Quotienten statt des Rests als CRC angeben.

Der CRC / XOR / Modulo-2-Rechner XORt in jedem Schritt, hängt die korrekten Nullen an und liefert den Rest als Prüfsumme.

Haeufige Fragen