Was ist CRC (zyklische Redundanzprüfung)?
Fehlererkennungsverfahren, das die Datenbits als Polynom behandelt, den Rest der Division durch ein Generatorpolynom anhängt und den Empfänger die Rechnung wiederholen lässt, um Fehler zu erkennen. Es wird in Ethernet, PCI Express, USB und Dateiformaten weit verwendet.
Japanische Bezeichnung: CRC(巡回冗長検査)
„CRC (zyklische Redundanzprüfung)“ kommt in 8 Übungsfragen aus 3 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung, Logikschaltungen, Schnittstellen und Busstandards.
Fachgebiet: Schnittstellen und Busstandards
Funktionsweise
Eine CRC behandelt die Datenbits als Koeffizienten eines Polynoms in Modulo-2-Arithmetik und berechnet den Rest nach Division durch ein Generatorpolynom. In Modulo-2-Arithmetik sind Addition und Subtraktion beide XOR, sodass die Division aus der Wiederholung von „ist das führende Bit 1, das Generatorpolynom per XOR verknüpfen und um eins verschieben“ besteht. Bei einer w-Bit-CRC wird der w-Bit-Rest, der sich nach dem Anhängen von w Nullen ergibt, mit den Daten gesendet, und der Empfänger wiederholt die Rechnung, um die Übereinstimmung zu prüfen. Reale Standards fügen Konventionen wie einen Startwert, die Bitumkehr jedes Bytes und ein abschließendes XOR hinzu.
Erkannte Fehler und Einsatzgebiete
Eine w-Bit-CRC erkennt jeden Bündelfehler der Länge w oder kürzer, und die Wahrscheinlichkeit, andere zufällige Fehler zu übersehen, beträgt etwa 2⁻ʷ. Sie erkennt Fehler jedoch nur und kann sie nicht korrigieren, sodass Systeme durch erneute Übertragung wiederherstellen. CRCs werden in der Ethernet-FCS (CRC-32), in Paketen von PCI Express, USB, CAN-Bus, Speicherbefehlen und Dateiformaten wie ZIP und PNG verwendet, und in Hardware lassen sie sich mit einem linear rückgekoppelten Schieberegister berechnen, das aus Flipflop-Stufen und XOR-Gattern besteht.
Häufige Fragen
Wie unterscheidet sich eine CRC von einer Prüfsumme?
Eine Prüfsumme nutzt eine einfache Operation wie das Addieren von Bytes und übersieht leicht vertauschte Daten oder Fehler, die sich gegenseitig aufheben, während eine CRC auf Polynomdivision beruht, Bitpositionen unterscheidet und Bündelfehler zuverlässig erkennt.
Kann eine CRC Fehler korrigieren?
Im Allgemeinen nicht. Eine CRC erkennt, ob ein Fehler aufgetreten ist, aber nicht, welches Bit falsch ist; Speicher, die eine Korrektur brauchen, nutzen daher einen ECC wie einen Hamming-Code.