Ich möchte eine Sende- und Empfangsstation bauen, mit der sich Daten mit Hilfe von Lichtsignalen („Visible Light Communication“ – VLC) übertragen lassen. Damit eine Datenübertragung stattfinden kann muss die Taktfrequenz des Senders und des Empfängers genau aufeinander abgestimmt sein. Wie man eine präzise Taktfrequenz für den Arduino und den Raspberry Pi einstellt, habe ich bereits in vorangegangenen Beiträgen erklärt, die ich nachfolgend verlinke.
Eine zyklische Redundanzprüfung ist eine simple und elegante Möglichkeit um zu überprüfen, ob die an einer Empfangsstation eintreffenden Daten korrekt sind. Wenn beispielsweise bei einem empfangenen Datenpaket Bits vertauscht wurden oder statt einer 0 eine 1 empfangen wurde, kann dies durch die zyklische Redundanzprüfung (kurz CRC: „Cyclic Redundancy Check“) nachgewiesen werden. Die CRC erkennt, dass ein Datenpaket einen Fehler hat und die Empfangsstation verwirft.
Das könnte Sie auch interessieren: Präzise Taktfrequenz für einen Arduino einstellen
Ebenfalls eng mit diesem Artikel verbunden: Präzise Taktfrequenz für den Raspberry Pi einstellen
Zyklische Redundanzprüfung – Funktionsweise:
Die CRC ist ein mathematischer Kniff. Im Prinzip handelt es sich bei der Berechnung um eine Polynomdivision. Zum Beispiel entspricht das Datenpaket 10010101 dem folgenden Polynom:
Für die Berechnung des CRC bzw. für die Polynomdivision wird auch ein sogenanntes Generatorpolynom benötigt. Dieses kann eigentlich frei gewählt werden, jedoch haben sich einige Polynome als besonders gut geeignet herausgestellt. Wichtig ist, dass das Generatorpolynom für das Senden der Daten und das Empfangen der Daten identisch ist. Ich habe der Einfachheit halber das Polynom 1011 gewählt:
Der Ablauf ist für jedes Datenpaket gleich. An jedes Datenpaket das versendet werden soll wird ein zusätzlicher CRC-Wert drangehängt. Dieser CRC Wert ist um eine Stelle kleiner als das Generatorpolynom. Im Aktuellen Fall besitzt das Generatorpolynom 1011 insgesamt 4 Stellen, daraus folgt, dass der CRC Wert 3 Stellen besitzt. Zu Beginn der Berechnung ist der CRC-Wert noch unbekannt, daher wird einfach 3 Mal (da der CRC-Wert ja hier 3 Stellen besitzt) die 0 an das Datenpaket angehängt. Somit wird aus dem Datenpaket 10010101 jetzt 10010101000.
Anschließend startet die Polynomdivision. 10010101000 wird durch 1011 geteilt. Ich habe den Schrittweisen Vorgang der Division in einer Grafik zusammengefasst. Am Ende der Polynomdivision bleibt auf der Sender (englisch: Transmitter) der Rest 110. Dieser Rest ist der gewünschte CRC-Wert. Der CRC-Wert wird an das eigentliche Datenpaket 10010101 angehängt und an den Empfänger übertragen. Bei einer korrekten Datenübertragung erhält der Empfänger das Paket 10010101110.
An dieser Stelle folgt der mathematische Kniff. An das Datenpaket wurde der berechnete CRC angehängt und an den Empfänger übertragen. Der Empfänger kann nun ebenfalls eine Polynomdivision mit dem Generatorpolynom 1011 durchführen, aber da dieses Mal an Stelle von 3 Mal 0, der CRC Wert 110 an das Datenpaket 10010101 drangehängt wurde, bleibt bei der erneuten Polynomdivision kein Rest übrig.
Wenn auf der Empfänger Seite kein Rest übrigbleibt, bedeutet, dass das Datenpaket korrekt übertragen wurde. Sollte allerdings ein Rest übrigbleiben, dann hat sich während der Übertragung ein Fehler eingeschlichen. Das fehlerhafte Datenpaket kann verworfen werden und der Empfänger kann um eine erneute Übertragung des Datenpakets bitten.
2 Gedanken zu “Zyklische Redundanzprüfung in C”