CRC
Die Abkürzung CRC wird auch für den Verlag CRC Press verwendet.
CRC (Abkürzung von englisch cyclic redundancy check, zyklischer Redundanztest) ist ein Verfahren (bzw. eine bestimmte Klasse von Verfahren) zur Bestimmung einer Prüfsumme für Daten (z. B. Netzwerkverkehr oder eine Datei), um Fehler bei der Übertragung oder Duplizierung der Daten erkennen zu können. CRC's werden vor Beginn der Übertragung bzw. Kopie der Daten und nach Abschluss der Transaktion berechnet. Anschließend werden die beiden Prüfsummen verglichen. CRC-Prüfungen sind so ausgelegt, dass vorhersehbare Fehler, wie sie z. B. durch Rauschen auf der Leitung verursacht werden könnten, fast immer entdeckt werden können. CRC's können jedoch nicht die Integrität der Daten bestätigen, d. h. es ist verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom zu erzeugen, der den gleichen CRC-Wert wie eine gegebene Nachricht hat; wenn diese Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie z. B. MD5 zum Einsatz kommen.
Das Verfahren beruht auf Polynomdivision. Der Rest dieser Division bildet die CRC-Prüfsumme. Dabei wird die Bitfolge der Coderepräsentation der Zeichen einer Datei byteweise in einer Polynomdivision verarbeitet. Endresultat ist (beim CRC-32) eine 32 Bit (4 Byte) lange Prüfsumme, welche die Datei kennzeichnet. Der relevante Teil des verwendeten Algorithmus sieht umgangssprachlich etwa so aus:
schieberegister = startwert (meist 0x0000... oder 0xFFFF...)
solange Bits im String verbleiben:
wenn das MSB von schieberegister gesetzt ist:
schieberegister = (schieberegister linksschieben um 1) xor Polynom
("linksschieben" setzt eine Big-Endian-Architektur voraus)
andernfalls:
schieberegister = schieberegister linksschieben um 1
xor nächstes Bit aus dem String in das LSB des schieberegisters
schieberegister ausgeben
Durch Verwendung einer Tabelle, die für jedes der 256 möglichen Bytes das zugehörige CRC enthält, lässt sich obiger Algorithmus um das achtfache beschleunigen.CRC-Typen werden oft anhand des als Divisor verwendeten Polynoms unterschieden (im Hexadezimal-Format). Eines der meistverwendeten CRC's (u. a. von Ethernet, FDDI, WinZip und PNG benutzt) ist das Polynom 0x04C11DB7, bekannt als CRC-32.
CRC's werden häufig als "Prüfsummen" bezeichnet, obwohl dies strenggenommen nicht ganz korrekt ist, da Prüfsummen technisch gesehen durch Addition und nicht durch Division errechnet werden.
Siehe auch: DFÜ, Hamming-Code, MD5, ECC, Parität, Prüfsumme
