wikiZyklische Redundanzprüfung
Die zyklische Redundanzprüfung (engl. cyclic redundancy check, CRC) ist eine Methode zur Fehlererkennung bei der digitalen Datenübertragung und -speicherung. Dabei wird eine Prüfsumme, der sogenannte CRC-Code, aus den zu übertragenden Daten berechnet und zusammen mit den Daten gesendet. Der Empfänger kann dann anhand dieser Prüfsumme überprüfen, ob die Daten während der Übertragung verändert wurden.
Funktionsweise
Der Algorithmus basiert auf Polynomdivision über einem endlichen Körper. Die Daten werden als Bitfolge einer bestimmten Länge interpretiert. Diese Bitfolge wird dann durch ein fest definiertes Generatorpolynom dividiert und der Restwert dieser Division ist die Prüfsumme, welche den Daten angehängt wird.
Das Generatorpolynom ist statisch definiert und muss sowohl Sender als auch Empfänger bekannt sein.
Binäre Polynomdivision
Sowohl Daten als auch Generator werden als Folge von Einsen und Nullen dargestellt, werden aber als Polynom behandelt:
Bitfolge: 1 1 1 0 0 0 1
Polynom: 1*x^6 + 1*x^5 + 1*x^4 + 0*x^3 + 0*x^2 + 0*x^1 + 1*x^0
Die Bits sind also die Koeffizienten eines Polynoms. Bei der Division einer Bitfolge durch das Generatorpolynom ist zu beachten, dass der Berechnung ein XOR-Gatter zugrundeliegt:
| XOR | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Beispielrechnung
Bitfolge: 1 1 1 0 0 1 0 0 0 0
Generator: 1 0 0 1
1 1 1 0 0 0 1 0 0 0 0 % 1 0 0 1
1 0 0 1 | | | | | | |
------- | | | | | | |
0 1 1 1 0 | | | | | |
1 0 0 1 | | | | | |
------- | | | | | |
0 1 1 1 0 | | | | |
1 0 0 1 | | | | |
------- | | | | |
0 1 1 1 1 | | | |
1 0 0 1 | | | |
------- | | | |
0 1 1 0 0 | | |
1 0 0 1 | | |
------- | | |
0 1 0 1 0 | |
1 0 0 1 | |
------- | |
0 0 1 1 0 |
0 0 0 0 |
------- |
0 1 1 0 0
1 0 0 1
-------
0 1 0 1
Der Rest "0 1 0 1" ist die Prüfsumme und wird nun den Daten zur Übermittlung angehängt. Der Empfänger erhält also das Datenpaket:
1 1 1 0 0 0 | 0 1 0 1
Der Empfänger prüft nun auf dieselbe Weise mithilfe des Generators auf Fehler:
Bitfolge: 1 1 1 0 0 1 0 1 0 1
Generator: 1 0 0 1
1 1 1 0 0 0 1 0 1 0 1 % 1 0 0 1
1 0 0 1 | | | | | | |
------- | | | | | | |
0 1 1 1 0 | | | | | |
1 0 0 1 | | | | | |
------- | | | | | |
0 1 1 1 0 | | | | |
1 0 0 1 | | | | |
------- | | | | |
0 1 1 1 1 | | | |
1 0 0 1 | | | |
------- | | | |
0 1 1 0 0 | | |
1 0 0 1 | | |
------- | | |
0 1 0 1 1 | |
1 0 0 1 | |
------- | |
0 0 1 0 0 |
0 0 0 0 |
------- |
0 1 0 0 1
1 0 0 1
-------
0 0 0 0
Bei einer fehlerlosen Übertragung ist der Rest der Division eine Folge aus Nullen.[1][2]
Einzelnachweise
 |
Autor: Stefan Bohn Stefan Bohn ist seit 2020 bei der Thomas-Krenn.AG beschäftigt. Ursprünglich als Berater für IT-Lösungen im PreSales beheimatet, wechselte er 2022 zum Product Management. Dort widmet er sich dem Wissenstransfer und treibt dabei auch das Thomas-Krenn Wiki voran.
|
