CRC: Unterschied zwischen den Versionen
Falk (Diskussion | Beiträge) (→Weblinks: Tote Linke entfernt, neue Links ergänzt) |
|||
(31 dazwischenliegende Versionen von 23 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
'''C'''yclic '''R'''edundancy '''C'''heck | '''C'''yclic '''R'''edundancy '''C'''heck | ||
Ein Verfahren um aus einem beliebig langen Datenstrom eine Prüfsumme (Schlüssel) fester | Ein Verfahren, um aus einem beliebig langen Datenstrom eine Prüfsumme (Schlüssel) fester Breite zu erzeugen. Das besondere ist, dass sich die Prüfsumme schon bei minimalen Veränderungen in den Daten stark verändert und es damit sehr unwahrscheinlich ist, dass zwei verschiedene Datenströme die gleiche Prüfsumme haben. Der häufigste Einsatzzweck von CRC ist die Überprüfung von Daten auf Unversehrtheit in einem Speicher oder nach einer Datenübertragung. | ||
Der | == Algorithmus == | ||
Der CRC-Algorithmus ist relativ einfach zu realisieren und dennoch ein Mittel, um Daten bei ihrer Speicherung oder Übertragung wirkungsvoll auf Korrektheit zu prüfen. Beim CRC Verfahren gibt es ein sogenanntes Generator-Polynom, welches beim Sender und Empfänger der Daten (Sender und Empfänger können auch ein und das selbe Gerät sein) bekannt sein muss. Je nach Bezeichnung des Verfahrens handelt es sich um eine unterschiedliche Länge dieses Generator-Polynoms. Zum Beispiel bedeutet CRC-16, dass das Generator-Polynom vom Grad 16 ist, sprich es hat 17 [[Bit]]. CRC-16 ist auch die häufigste Form, es wird aber auch z. B. CRC-8 oder CRC-32 verwendet. | |||
=== Anwendung === | |||
'''Zur praktischen Anwendung dieses Verfahrens:''' | |||
# An die zu schützenden binären Daten werden N Bits mit dem Wert Null angefügt, wobei N das Grad des Generatorpolynoms ist. (CRC-16 -> 16 hinzugefügte Bits) | |||
# Die entstandene neuen binären Daten werden durch das Generator-Polynom geteilt und der Rest wird ermittelt! | |||
# Der Rest wird zu den binären Daten hinzugefügt, er stellt die Prüfsumme dar. | |||
Der Empfänger kann nun die erhaltenen Daten durch das Generator-Polynom teilen. Bleibt bei dieser Division 0 Rest sind die Daten korrekt übertragen worden. Ist der Rest ungleich 0, ist ein Fehler bei der Übertragung aufgetreten. | |||
Um die ursprünglichen Daten wieder zu erhalten (natürlich nur, falls sie korrekt übertragen wurden) müssen nur die letzten Stellen entfernt werden! | |||
=== Berechnungshinweise === | |||
'''Bei der Berechnung ist folgendes zu beachten:''' | |||
Das Bilden des Restes wird beim schriftlichen Divideren durch eine Subtraktion durchgeführt. | |||
Hier beim CRC wird es aber mit einer [[Logische Verknüpfungen#XOR|XOR]] Verknüpfung realisiert. Desweiteren entfällt auch das bilden des Quotienten, dieser wird nicht benötigt. | |||
== Beispiel == | |||
[http://www.mikrocontroller.net/forum/read-1-190635.html Forumsbeitrag]: Hilfe CCITT CRC 16 Verständnisproblem | |||
Das Generator-Polynom sei <math>x^5+x^2+x</math>. Dies entspricht der binären Zahl 100110. Das Polynom ist vom 5. Grad, weil das höchste gesetzte Bit den Wert 2^5 hat. Gerechnet wird aber immer nur mit den unteren 5 Bit, hier also 00110. Jetzt ist natürlich auch noch eine binäre Zeichenkette notwendig, die unsere Daten darstellt. Beispielsweise 1110100111001 (willkürlich gewählt). | |||
==='''Sender'''=== | |||
* An die Daten werden 5 Nullen angehängt: | |||
* | |||
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 | 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 | ||
* Die Daten müssen jetzt durch das Generator-Polynom dividiert und somit der Rest ermittelt werden: | * Die Daten müssen jetzt durch das Generator-Polynom dividiert und somit der Rest ermittelt werden: | ||
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 | 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 | ||
<u>1 0 0 1 1 0</u> | <u>1 0 0 1 1 0</u> | ||
Zeile 51: | Zeile 55: | ||
<u>1 0 0 1 1 0</u> | <u>1 0 0 1 1 0</u> | ||
0 0 0 0 1 0 0 | 0 0 0 0 1 0 0 | ||
Der Rest ist also 100. | Der Rest ist also 100. | ||
* Nun muss nur noch der Rest zu den Daten | * Nun muss nur noch der Rest zu den Daten hinzugefügt werden: | ||
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 | 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 | ||
==='''Empfänger'''=== | |||
'''ohne Fehler''' | '''ohne Fehler''' | ||
Zeile 70: | Zeile 76: | ||
0 1 0 0 0 1 1 | 0 1 0 0 0 1 1 | ||
<u>1 0 0 1 1 0</u> | <u>1 0 0 1 1 0</u> | ||
0 0 0 1 0 1 0 0 | 0 0 0 1 0 1 0 0 1 | ||
<u>1 0 0 1 1 0</u> | <u>1 0 0 1 1 0</u> | ||
0 0 1 1 1 1 0 0 | 0 0 1 1 1 1 0 0 | ||
Zeile 114: | Zeile 117: | ||
0 0 1 0 1 0 0 | 0 0 1 0 1 0 0 | ||
Somit bleibt also 10100 als Rest und dies bedeutet, dass die Daten nicht korrekt beim Empfänger angekommen sind! | Somit bleibt also 10100 als Rest und dies bedeutet, dass die Daten nicht korrekt beim Empfänger angekommen sind! | ||
== Abwandlungen == | |||
Eine Weiterentwicklung des CRC ist die forward error correction (FEC), die das entstehende Prüfsumme voraus sendet / berechnet und es so gestattet, das zu erwartende Datenwort vorauszuberechnen und direkt beim Empfang zu prüfen und ggfs zu korrigieren. | |||
== Siehe auch == | |||
* [http://www.mikrocontroller.net/topic/219468 Forumsbeitrag]: CAN-CRC berechnen | |||
* [http://www.mikrocontroller.net/topic/228553 Forumsbeitrag]: An Bit Experten: "Alles CRC oder was?" - oder so. | |||
* [http://www.mikrocontroller.net/topic/12177 Forumsbeitrag]: CRC-16 Prüfsumme (serielle Übertragung) | |||
* [http://www.mikrocontroller.net/forum/4?filter=crc* Suche] nach Implementierungen in der Codesammlung | |||
== Weblinks == | |||
* [http://www.ross.net/crc/download/crc_v3.txt A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS] | |||
* [https://pycrc.org/ C Source Generator] | |||
* [http://www.zorc.breitbandkatze.de/crc.html Online Rechner], berechnet CRC16, CRC32 und CRC-CCITT | |||
* [http://www.informatik.uni-frankfurt.de/~haase/crc.html CRC - Der Cyclic Redundancy Code] auf www.informatik.uni-frankfurt.de | |||
* [http://crc-gen-verilog.sourceforge.net/ Online CRC mit Verilog und VHDL Generator] | |||
* [http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung CRC bei Wikipedia] | |||
* [http://www.verilog.net/free.html Offline Verilog CRC] | |||
* [https://blog.mbedded.ninja/programming/general/crcs-cyclic-redundancy-checks/ Ninjacalc] - Berechnungsprogramm für verschiedene CRC-Varianten | |||
* [http://users.ece.cmu.edu/~koopman/crc/ Best CRC Polynomials], Philip Koopman, Carnegie Mellon University | |||
* [https://www.texttool.com/crc-online Online CRC Calculator] | |||
* [https://www.lddgo.net/en/encrypt/crc CRC Calculation Online] | |||
* [https://www.tahapaksu.com/crc/ Online CRC Calculation] | |||
* [http://www.sunshine2k.de/coding/javascript/crc/crc_js.html CRC Calculator] | |||
* [https://crccalc.com/ crccalc.com] | |||
[[Kategorie:Algorithmen und Arithmetik]] |
Aktuelle Version vom 23. April 2023, 18:35 Uhr
Cyclic Redundancy Check
Ein Verfahren, um aus einem beliebig langen Datenstrom eine Prüfsumme (Schlüssel) fester Breite zu erzeugen. Das besondere ist, dass sich die Prüfsumme schon bei minimalen Veränderungen in den Daten stark verändert und es damit sehr unwahrscheinlich ist, dass zwei verschiedene Datenströme die gleiche Prüfsumme haben. Der häufigste Einsatzzweck von CRC ist die Überprüfung von Daten auf Unversehrtheit in einem Speicher oder nach einer Datenübertragung.
Algorithmus
Der CRC-Algorithmus ist relativ einfach zu realisieren und dennoch ein Mittel, um Daten bei ihrer Speicherung oder Übertragung wirkungsvoll auf Korrektheit zu prüfen. Beim CRC Verfahren gibt es ein sogenanntes Generator-Polynom, welches beim Sender und Empfänger der Daten (Sender und Empfänger können auch ein und das selbe Gerät sein) bekannt sein muss. Je nach Bezeichnung des Verfahrens handelt es sich um eine unterschiedliche Länge dieses Generator-Polynoms. Zum Beispiel bedeutet CRC-16, dass das Generator-Polynom vom Grad 16 ist, sprich es hat 17 Bit. CRC-16 ist auch die häufigste Form, es wird aber auch z. B. CRC-8 oder CRC-32 verwendet.
Anwendung
Zur praktischen Anwendung dieses Verfahrens:
- An die zu schützenden binären Daten werden N Bits mit dem Wert Null angefügt, wobei N das Grad des Generatorpolynoms ist. (CRC-16 -> 16 hinzugefügte Bits)
- Die entstandene neuen binären Daten werden durch das Generator-Polynom geteilt und der Rest wird ermittelt!
- Der Rest wird zu den binären Daten hinzugefügt, er stellt die Prüfsumme dar.
Der Empfänger kann nun die erhaltenen Daten durch das Generator-Polynom teilen. Bleibt bei dieser Division 0 Rest sind die Daten korrekt übertragen worden. Ist der Rest ungleich 0, ist ein Fehler bei der Übertragung aufgetreten. Um die ursprünglichen Daten wieder zu erhalten (natürlich nur, falls sie korrekt übertragen wurden) müssen nur die letzten Stellen entfernt werden!
Berechnungshinweise
Bei der Berechnung ist folgendes zu beachten:
Das Bilden des Restes wird beim schriftlichen Divideren durch eine Subtraktion durchgeführt. Hier beim CRC wird es aber mit einer XOR Verknüpfung realisiert. Desweiteren entfällt auch das bilden des Quotienten, dieser wird nicht benötigt.
Beispiel
Forumsbeitrag: Hilfe CCITT CRC 16 Verständnisproblem
Das Generator-Polynom sei [math]\displaystyle{ x^5+x^2+x }[/math]. Dies entspricht der binären Zahl 100110. Das Polynom ist vom 5. Grad, weil das höchste gesetzte Bit den Wert 2^5 hat. Gerechnet wird aber immer nur mit den unteren 5 Bit, hier also 00110. Jetzt ist natürlich auch noch eine binäre Zeichenkette notwendig, die unsere Daten darstellt. Beispielsweise 1110100111001 (willkürlich gewählt).
Sender
- An die Daten werden 5 Nullen angehängt:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0
- Die Daten müssen jetzt durch das Generator-Polynom dividiert und somit der Rest ermittelt werden:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0
Der Rest ist also 100.
- Nun muss nur noch der Rest zu den Daten hinzugefügt werden:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0
Empfänger
ohne Fehler
Der Empfänger ermittelt seinerseits jetzt natürlich ebenfalls aus diesen empfangenen Daten den Rest:
- Rest ermitteln
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0
Der Rest ist also wirklich 0.
mit Fehler
Addieren wir beispielsweise 1100 zu den Daten hinzu bekommen wir also:
1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0
Jetzt führen wir die Division erneut durch und sehen uns den Rest an:
- Rest ermitteln
1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0
Somit bleibt also 10100 als Rest und dies bedeutet, dass die Daten nicht korrekt beim Empfänger angekommen sind!
Abwandlungen
Eine Weiterentwicklung des CRC ist die forward error correction (FEC), die das entstehende Prüfsumme voraus sendet / berechnet und es so gestattet, das zu erwartende Datenwort vorauszuberechnen und direkt beim Empfang zu prüfen und ggfs zu korrigieren.
Siehe auch
- Forumsbeitrag: CAN-CRC berechnen
- Forumsbeitrag: An Bit Experten: "Alles CRC oder was?" - oder so.
- Forumsbeitrag: CRC-16 Prüfsumme (serielle Übertragung)
- Suche nach Implementierungen in der Codesammlung
Weblinks
- A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
- C Source Generator
- Online Rechner, berechnet CRC16, CRC32 und CRC-CCITT
- CRC - Der Cyclic Redundancy Code auf www.informatik.uni-frankfurt.de
- Online CRC mit Verilog und VHDL Generator
- CRC bei Wikipedia
- Offline Verilog CRC
- Ninjacalc - Berechnungsprogramm für verschiedene CRC-Varianten
- Best CRC Polynomials, Philip Koopman, Carnegie Mellon University
- Online CRC Calculator
- CRC Calculation Online
- Online CRC Calculation
- CRC Calculator
- crccalc.com