CRC

English: Cyclic Redundancy Check (CRC) / Español: Comprobación de Redundancia Cíclica (CRC) / Português: Verificação de Redundância Cíclica (CRC) / Français: Contrôle de Redondance Cyclique (CRC) / Italiano: Controllo a Ridondanza Ciclica (CRC)

Der Begriff **CRC** (Cyclic Redundancy Check) bezeichnet ein in der Informationstechnik weit verbreitetes Verfahren zur Erkennung von Fehlern bei der Datenübertragung oder -speicherung. Es handelt sich um eine mathematische Methode, die auf Polynomdivision basiert und eine Prüfsumme generiert, um die Integrität von Daten zu überprüfen. CRC wird insbesondere in Netzwerkprotokollen, Speichermedien und industriellen Kommunikationssystemen eingesetzt, da es eine hohe Fehlererkennungsrate bei vergleichsweise geringem Rechenaufwand bietet.

Allgemeine Beschreibung

CRC ist ein nicht-kryptografisches Verfahren zur Fehlererkennung, das auf der Berechnung einer Prüfsumme basiert. Diese Prüfsumme, auch CRC-Wert genannt, wird aus den zu übertragenden oder zu speichernden Daten abgeleitet und zusammen mit diesen übermittelt. Der Empfänger berechnet seinerseits den CRC-Wert der empfangenen Daten und vergleicht ihn mit dem übermittelten Wert. Stimmen beide Werte überein, wird davon ausgegangen, dass die Daten fehlerfrei übertragen wurden. Andernfalls liegt ein Übertragungsfehler vor, und die Daten müssen erneut gesendet oder korrigiert werden.

Die Grundlage von CRC bildet die Polynomdivision über dem Galois-Körper GF(2), bei der die Daten als Binärpolynom interpretiert werden. Dieses Polynom wird durch ein vordefiniertes Generatorpolynom dividiert, wobei der Rest der Division als CRC-Wert dient. Die Wahl des Generatorpolynoms ist entscheidend für die Fehlererkennungsfähigkeit des Verfahrens. Standardisierte Polynome, wie CRC-8, CRC-16 oder CRC-32, wurden entwickelt, um spezifische Anforderungen an die Fehlererkennung zu erfüllen, beispielsweise die Erkennung von Einzelbitfehlern, Burst-Fehlern oder bestimmten Mustern von Bitfehlern.

Im Gegensatz zu einfachen Prüfsummenverfahren, wie der Längsparität oder der Querparität, bietet CRC eine deutlich höhere Fehlererkennungsrate. Während einfache Verfahren oft nur Einzelbitfehler erkennen können, ist CRC in der Lage, auch Mehrfachfehler, insbesondere Burst-Fehler, zu detektieren. Burst-Fehler sind Fehler, bei denen mehrere aufeinanderfolgende Bits verfälscht werden, was beispielsweise durch elektromagnetische Störungen oder physikalische Defekte in Speichermedien verursacht werden kann.

CRC wird in einer Vielzahl von Anwendungen eingesetzt, da es eine gute Balance zwischen Rechenaufwand und Fehlererkennungsleistung bietet. Es ist jedoch wichtig zu beachten, dass CRC keine Fehlerkorrektur ermöglicht. Im Falle eines erkannten Fehlers müssen die Daten erneut übertragen oder durch zusätzliche Mechanismen, wie Forward Error Correction (FEC), korrigiert werden. CRC dient somit ausschließlich der Fehlererkennung und nicht der Fehlerbehebung.

Technische Details

Die Berechnung eines CRC-Werts erfolgt in mehreren Schritten, die auf der Polynomarithmetik basieren. Zunächst werden die zu überprüfenden Daten als Binärfolge interpretiert und als Polynom dargestellt. Beispielsweise entspricht die Binärfolge 1101 dem Polynom x³ + x² + 1. Das Generatorpolynom, das für die CRC-Berechnung verwendet wird, ist ebenfalls ein Binärpolynom, dessen Grad die Länge des CRC-Werts bestimmt. Ein Generatorpolynom vom Grad n erzeugt einen CRC-Wert der Länge n Bits.

Der Algorithmus zur CRC-Berechnung läuft wie folgt ab: Die Datenbits werden um n Nullbits erweitert, wobei n der Grad des Generatorpolynoms ist. Diese erweiterte Bitfolge wird anschließend durch das Generatorpolynom dividiert, wobei die Division im Galois-Körper GF(2) durchgeführt wird. In GF(2) gelten die Regeln der Modulo-2-Arithmetik, bei der die Addition und Subtraktion identisch sind und der XOR-Operation entsprechen. Der Rest dieser Division bildet den CRC-Wert, der an die Daten angehängt wird.

Ein Beispiel für ein weit verbreitetes Generatorpolynom ist das CRC-32-Polynom, das in Ethernet-Netzwerken und vielen anderen Anwendungen verwendet wird. Es lautet:

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1.

Dieses Polynom ermöglicht die Erkennung von Fehlern in Datenblöcken mit einer Länge von bis zu 2³² − 1 Bits und bietet eine hohe Wahrscheinlichkeit für die Erkennung von Burst-Fehlern mit einer Länge von bis zu 32 Bits.

Die Implementierung von CRC kann sowohl in Hardware als auch in Software erfolgen. Hardwareimplementierungen nutzen oft Schieberegister und XOR-Gatter, um die Polynomdivision effizient durchzuführen. Diese Methode ist besonders schnell und wird häufig in Netzwerkhardware oder Speichercontrollern eingesetzt. Softwareimplementierungen hingegen verwenden Algorithmen, die auf Bitoperationen basieren, und sind flexibler, aber in der Regel langsamer als Hardwarelösungen.

Ein wichtiger Aspekt bei der Verwendung von CRC ist die Wahl des Generatorpolynoms. Unterschiedliche Polynome bieten unterschiedliche Fehlererkennungsfähigkeiten. So ist beispielsweise CRC-16 in der Lage, alle Einzelbitfehler, alle Doppelbitfehler und alle Burst-Fehler mit einer Länge von bis zu 16 Bits zu erkennen. CRC-32 bietet eine noch höhere Fehlererkennungsrate und wird daher in Anwendungen eingesetzt, bei denen eine besonders hohe Datenintegrität erforderlich ist, wie beispielsweise in der Telekommunikation oder bei der Speicherung von Daten auf Festplatten.

Normen und Standards

Die Verwendung von CRC ist in zahlreichen internationalen Normen und Standards festgelegt. Einer der bekanntesten Standards ist die ITU-T-Empfehlung V.42, die CRC-16 für die Fehlererkennung in Modemverbindungen definiert. Weitere wichtige Standards sind:

• IEEE 802.3 (Ethernet): Verwendet CRC-32 zur Fehlererkennung in Ethernet-Frames.
• ISO/IEC 13239: Definiert CRC-16 für die Verwendung in Hochgeschwindigkeits-Datenübertragungssystemen.
• USB-Spezifikation: Nutzt CRC-5 und CRC-16 zur Fehlererkennung in verschiedenen Protokollschichten.
• ZIP-Dateiformat: Verwendet CRC-32 zur Überprüfung der Integrität komprimierter Dateien.

Diese Standards legen nicht nur die Generatorpolynome fest, sondern auch die genaue Vorgehensweise bei der Berechnung und Überprüfung der CRC-Werte. Die Einhaltung dieser Standards ist entscheidend, um die Interoperabilität zwischen verschiedenen Systemen und Geräten zu gewährleisten.

Abgrenzung zu ähnlichen Begriffen

CRC wird oft mit anderen Verfahren zur Fehlererkennung oder -korrektur verwechselt. Die wichtigsten Unterschiede zu ähnlichen Begriffen sind:

• Prüfsumme (Checksum): Eine Prüfsumme ist ein allgemeiner Begriff für Verfahren zur Fehlererkennung, die auf der Summation von Datenbits basieren. Im Gegensatz zu CRC sind einfache Prüfsummenverfahren, wie die Längsparität, weniger leistungsfähig und können nur begrenzte Fehlermuster erkennen.
• Parität: Paritätsbits werden verwendet, um Einzelbitfehler zu erkennen. Sie sind jedoch nicht in der Lage, Mehrfachfehler oder Burst-Fehler zu detektieren. CRC bietet hier eine deutlich höhere Fehlererkennungsrate.
• Forward Error Correction (FEC): FEC ist ein Verfahren zur Fehlerkorrektur, das nicht nur Fehler erkennt, sondern auch korrigieren kann. Im Gegensatz zu CRC erfordert FEC jedoch einen höheren Rechenaufwand und zusätzliche Redundanzbits, um Fehler zu beheben.
• Hash-Funktionen: Hash-Funktionen, wie SHA-256, werden zur Datenintegritätsprüfung und Authentifizierung eingesetzt. Sie sind jedoch kryptografisch sicher und bieten eine deutlich höhere Komplexität als CRC. Hash-Funktionen sind nicht für die Echtzeit-Fehlererkennung in Datenübertragungssystemen geeignet.

Anwendungsbereiche

• Netzwerktechnik: CRC wird in nahezu allen Netzwerkprotokollen eingesetzt, um die Integrität von Datenpaketen zu überprüfen. Beispiele hierfür sind Ethernet (IEEE 802.3), Wi-Fi (IEEE 802.11) und das Internet Protocol (IP). In diesen Protokollen wird CRC verwendet, um Übertragungsfehler zu erkennen und sicherzustellen, dass die Daten korrekt empfangen wurden.
• Speichermedien: In Festplatten, SSDs und anderen Speichermedien wird CRC eingesetzt, um die Integrität der gespeicherten Daten zu überprüfen. Beispielsweise nutzen Festplattencontroller CRC, um Lesefehler zu erkennen und gegebenenfalls eine erneute Datenübertragung zu initiieren.
• Industrielle Kommunikation: In industriellen Steuerungssystemen, wie PROFIBUS oder CAN (Controller Area Network), wird CRC verwendet, um die Zuverlässigkeit der Datenübertragung zu gewährleisten. Diese Systeme sind oft in rauen Umgebungen im Einsatz, in denen elektromagnetische Störungen zu Datenfehlern führen können.
• Datenkompression: In Kompressionsformaten, wie ZIP oder PNG, wird CRC eingesetzt, um die Integrität der komprimierten Daten zu überprüfen. Nach der Dekompression kann der CRC-Wert verwendet werden, um sicherzustellen, dass die Daten nicht durch Übertragungs- oder Speicherfehler verfälscht wurden.
• Softwareentwicklung: CRC wird in Softwarebibliotheken und -tools verwendet, um die Integrität von Dateien oder Datenströmen zu überprüfen. Beispielsweise nutzen Versionskontrollsysteme, wie Git, CRC-32, um die Konsistenz von Repository-Daten zu gewährleisten.

Bekannte Beispiele

• Ethernet (IEEE 802.3): Ethernet verwendet CRC-32 zur Fehlererkennung in Datenframes. Jeder Ethernet-Frame enthält ein 32-Bit-CRC-Feld, das vom Sender berechnet und vom Empfänger überprüft wird. Dies stellt sicher, dass die Daten während der Übertragung nicht verfälscht wurden.
• USB (Universal Serial Bus): USB nutzt CRC-5 und CRC-16 in verschiedenen Protokollschichten, um die Integrität von Datenpaketen zu überprüfen. Beispielsweise wird CRC-5 in den Token-Paketen verwendet, während CRC-16 in den Datenpaketen zum Einsatz kommt.
• ZIP-Dateiformat: Das ZIP-Dateiformat verwendet CRC-32, um die Integrität der komprimierten Dateien zu überprüfen. Jede Datei in einem ZIP-Archiv enthält einen CRC-32-Wert, der nach der Dekompression überprüft wird, um sicherzustellen, dass die Datei nicht beschädigt wurde.
• CAN (Controller Area Network): CAN, ein weit verbreitetes Bussystem in der Automobil- und Industrieautomation, verwendet CRC-15 zur Fehlererkennung. Dies stellt sicher, dass die Daten zwischen Steuergeräten zuverlässig übertragen werden, selbst in Umgebungen mit starken elektromagnetischen Störungen.
• PNG-Bildformat: Das PNG-Dateiformat nutzt CRC-32, um die Integrität der Bilddaten und Metadaten zu überprüfen. Jeder Datenblock in einer PNG-Datei enthält einen CRC-32-Wert, der nach dem Laden des Bildes überprüft wird.

Risiken und Herausforderungen

• Begrenzte Fehlererkennungsfähigkeit: Obwohl CRC eine hohe Fehlererkennungsrate bietet, ist es nicht in der Lage, alle möglichen Fehlermuster zu erkennen. Insbesondere bei gezielten Angriffen oder bestimmten Fehlermustern kann CRC versagen. Beispielsweise können bestimmte Burst-Fehler, deren Länge größer ist als der Grad des Generatorpolynoms, unter Umständen nicht erkannt werden.
• Keine Fehlerkorrektur: CRC dient ausschließlich der Fehlererkennung und bietet keine Möglichkeit zur Fehlerkorrektur. Im Falle eines erkannten Fehlers müssen die Daten erneut übertragen oder durch zusätzliche Mechanismen, wie FEC, korrigiert werden. Dies kann in Echtzeitanwendungen zu Verzögerungen führen.
• Rechenaufwand: Obwohl CRC im Vergleich zu kryptografischen Verfahren einen geringen Rechenaufwand erfordert, kann die Berechnung in Echtzeitanwendungen mit hohen Datenraten eine Herausforderung darstellen. Insbesondere in Softwareimplementierungen kann der Rechenaufwand zu Leistungsengpässen führen.
• Wahl des Generatorpolynoms: Die Wahl des Generatorpolynoms ist entscheidend für die Fehlererkennungsfähigkeit von CRC. Ein ungeeignetes Polynom kann die Fehlererkennungsrate erheblich reduzieren. Die Auswahl eines geeigneten Polynoms erfordert daher eine sorgfältige Analyse der spezifischen Anforderungen der Anwendung.
• Kollisionen: Obwohl CRC nicht für kryptografische Anwendungen geeignet ist, können in seltenen Fällen Kollisionen auftreten, bei denen unterschiedliche Daten den gleichen CRC-Wert erzeugen. Dies kann zu falsch-negativen Ergebnissen führen, bei denen ein Fehler nicht erkannt wird.

Ähnliche Begriffe

• Längsparität: Ein einfaches Verfahren zur Fehlererkennung, bei dem ein Paritätsbit an die Daten angehängt wird, um die Anzahl der Einsen in der Bitfolge zu überprüfen. Längsparität kann nur Einzelbitfehler erkennen und ist daher weniger leistungsfähig als CRC.
• Querparität: Ein Verfahren, bei dem Paritätsbits für jede Spalte einer Datenmatrix berechnet werden. Querparität kann sowohl Einzelbitfehler als auch bestimmte Mehrfachfehler erkennen, ist jedoch weniger effizient als CRC.
• Hamming-Code: Ein Verfahren zur Fehlererkennung und -korrektur, das auf der Verwendung von Paritätsbits basiert. Hamming-Codes können Einzelbitfehler nicht nur erkennen, sondern auch korrigieren, erfordern jedoch einen höheren Rechenaufwand als CRC.
• Reed-Solomon-Code: Ein leistungsfähiges Verfahren zur Fehlererkennung und -korrektur, das insbesondere in der digitalen Kommunikation und Speichertechnik eingesetzt wird. Reed-Solomon-Codes können sowohl Burst-Fehler als auch zufällige Fehler korrigieren, erfordern jedoch einen deutlich höheren Rechenaufwand als CRC.
• MD5 (Message-Digest Algorithm 5): Eine kryptografische Hash-Funktion, die zur Datenintegritätsprüfung eingesetzt wird. MD5 erzeugt einen 128-Bit-Hash-Wert und bietet eine höhere Sicherheit als CRC, ist jedoch aufgrund von Kollisionen nicht mehr für sicherheitskritische Anwendungen geeignet.

Zusammenfassung

CRC ist ein weit verbreitetes Verfahren zur Fehlererkennung, das auf der Polynomdivision basiert und eine hohe Fehlererkennungsrate bei vergleichsweise geringem Rechenaufwand bietet. Es wird in einer Vielzahl von Anwendungen eingesetzt, darunter Netzwerktechnik, Speichermedien, industrielle Kommunikation und Datenkompression. CRC ermöglicht die Erkennung von Einzelbitfehlern, Mehrfachfehlern und Burst-Fehlern, bietet jedoch keine Fehlerkorrektur. Die Wahl des Generatorpolynoms ist entscheidend für die Leistungsfähigkeit des Verfahrens, und standardisierte Polynome, wie CRC-16 oder CRC-32, werden in verschiedenen Normen und Protokollen definiert. Trotz seiner hohen Fehlererkennungsrate ist CRC nicht für alle Anwendungen geeignet, insbesondere wenn eine Fehlerkorrektur oder kryptografische Sicherheit erforderlich ist.

--