WikiDer > Zyklische Redundanzprüfung

Cyclic redundancy check

EIN zyklische Redundanzprüfung (CRC) ist ein Fehlererkennungscode, der häufig in digitalen Netzwerken und Speichermedien verwendet wird, um Bitfehler zu erkennen. Datenblöcke, die in diese Systeme eingehen, erhalten einen kurzen Prüfwert oder "Prüfsumme" basierend auf dem Rest bei einer "Division mit Rest" der Daten. Beim Herunterladen oder Lesen der Daten wird die "Division mit Rest" erneut durchgeführt, ist das Ergebnis der gleiche Rest, sind die Daten höchstwahrscheinlich korrekt. Wenn sie nicht korrekt ist, können die Daten über eine Fehlerkorrektur wiederhergestellt werden.

CRC verdankt seinen Namen der Tatsache, dass der Algorithmus auf zyklischen Codes basiert, dass die Prüfsumme ist redundant (er vergrößert die Nachricht, ohne notwendige Informationen hinzuzufügen) und kontrolliert die Daten. CRCs werden sehr häufig verwendet, da sie einfach in zu implementieren sind binär Hardware, sind mathematisch leicht zu analysieren und können häufige Fehler, die durch Rauschen in einem Übertragungskanal entstehen, gut erkennen. CRC wurde erfunden von W. Wesley Peterson 1961.

Operation

Der CRC-Algorithmus wird immer auf Daten ausgeführt, die gespeichert oder gesendet werden. Jeder Teil der Daten wird als Binärzahl betrachtet. Der CRC-Algorithmus wird dies tun binär dividiere die Zahl durch den CRCPolynom. Dies ist immer ein fester Binärwert, der spezifisch für die Algorithmus. Wird der Binärwert der Daten durch das CRC-Polynom dividiert, wird eine Prüfsumme gebildet. Diese Prüfsumme wird nach den Daten platziert. Die Daten und die Prüfsumme können nun gemeinsam gespeichert oder versendet werden.

Später, wenn die Daten gelesen oder empfangen werden, findet eine weitere CRC-Unterteilung statt. Die Division teilt die Binärzahl gefolgt von der Prüfsumme durch das gleiche CRC-Polynom. Die Division darf keinen Rest ergeben. Ist beim Speichern oder Senden der Daten ein Fehler aufgetreten, ist der Rest in der Regel ungleich 0. Die Division kann auch nur auf die Binärzahl erfolgen; wenn der erhaltene Restwert gleich der Prüfsumme ist, wurde kein Fehler in den Daten festgestellt.

Die meisten Anwendungen, die (nur) CRC verwenden, versuchen nicht, den Fehler zu lokalisieren und zu beheben (Fehlerkorrektur). Sie sorgen jedoch dafür, dass die Daten gespeichert oder erneut gesendet werden, bis keine Fehler mehr festgestellt werden.

Datenintegrität

CRCs werden hauptsächlich verwendet, um häufige Fehler bei der Signalübertragung zu erkennen. Sie stellen eine schnelle Möglichkeit dar, die Integrität der übertragenen Daten sicherzustellen. Dies gilt jedoch nur, wenn davon ausgegangen wird, dass Daten nicht abgefangen und verändert werden.

Da keine Authentifizierung erforderlich ist, kann ein Hacker die Daten ändern und den CRC neu berechnen, sodass die Änderung nicht erkannt werden kann. Da CRC eine leicht umkehrbare Funktion ist, kann sie nicht in digitalen Signaturen verwendet werden.

Größe der CRC-Prüfsumme

Ein CRC heißt a nein-bit CRC, wenn die Prüfsumme die Größe von hat nein bisschen. Für ein gegebenes nein mehrere CRCs sind möglich, jede mit einem anderen CRC-Polynom.

Längere CRC-Polynome bieten eine größere Sicherheit der Korrektheit der Daten, bieten aber mehr Überkopf.

Berechnung

In diesem Beispiel werden binäre Daten mit einer Länge von 6 Bit durch einen 2-Bit-CRC codiert. Das CRC-Polynom ist gleich x² 1, also mit den Koeffizienten 1, 0 und 1. Das Ergebnis, die Prüfsumme, ist der Rest der Division und ist 2 Bit lang. Der Quotient wird nicht verwendet.

Generieren der Prüfsumme

Die gesendeten oder gespeicherten Daten:

110101

Das CRC-Polynom:

101

Die Daten werden modulo-2 (XOR) durch das Polynom dividiert und mit einem 2-Bit-Suffix (00) versehen, um sicherzustellen, dass das Ergebnis ein Quotient mit einem Restwert von 2 Bit ist:

110101 00 / 101 = 111011 <-- Quotient101--- 111 101 --- 100 101 --- 11 0 10 1 -- - 1 10 1 01 - -- 11 <-- Rest = CRC-PrüfsummeDaten zusammen mit CRC-Prüfsumme = 11010111

Daten auf Fehler prüfen mit CRC

Die Daten können auf 2 Arten überprüft werden:

1) Die Daten 110101 werden vom CRC-Polynom 101 zurückgesendet und der Rest mit der Prüfsumme 11 verglichen. Dies ist genau die gleiche Operation wie beim Senden/Speichern von Daten.

2) Die Daten 11010111 werden durch 101 geteilt und der Restwert wird mit 0 verglichen.


Termine mit Prüfsumme:

11010111

Polynom:

101

Die Daten werden wiederum modulo-2 (XOR) durch das Polynom geteilt:

11010111 / 101 = 11101 <-- Quotient101--- 111 101 --- 100 101 --- 111 101 --- 101 101 -- 00 <-- Restwert ist Null, also kein Fehler erkannt.

Siehe auch

Verweise