Maikwoehl a personal blog

CRC - Cyclic Redundancy Check

Der CRC-Check ermöglicht es eine digitale/binäre Nachricht über eine Signalstrecke zu übertragen und beim Empfänger auf Fehlerfreiheit zu überprüfen. Dafür wird der Nachricht ein Prüfsumme angehängt, die beim Empfänger bei Durchführung eines CRC mit gleichem Aufbau eine binäre Null im Schieberegister zurückliefert.

Zum Konstruieren dieses Schieberegisters ist es notwendig den grundlegenden Aufbau einer CRC-Strecke zu kennen. Eine CRC-Strecke wird mit einem Polynom beschrieben. Das Polynom beschreibt die Stellen der Knoten in dem physikalischen Aufbau der Schieberegisterbank. Jeder Knoten, außer der höchstwertigste, wird mit einem XOR-Gatter verknüpft.

Ein Rückkopplungspolynom

p(x)=x^5+x^3+x^1+1

liefert die Vorschrift für die abgebildete Schieberegisterstruktur.

Wird z.B. die Nachricht

N(x) = 11011 = x^4+x^3+x^1+x^0

versendet, wird mithilfe der CRC-Schieberegisterstruktur eine Prüfsumme erstellt.

q_1(x) = R(X) = (N(x) * x^5+00000) mod p(x) = 11010 0000

Diese Prüfsumme lautet dann

R(x) = 01111 = x^3+x^2+x^1+x^0

Wird diese Nachricht dann mit dem Restpolynom bzw. der Prüfsumme versendet und beim Empfänger ebenfalls geprüft, dann erhält man folgendes Ergebnis:

q_2(x) = N(x) * x^5 + R(x) = 11011 01111 = x^9+x^8+x^6+x^5+x^3+x^2+x^1+x^0

Die Berechnung, die dann durchgeführt wird ist:

R_neu(x)= q_2(x) mod p(x) R_neu(x)= 00000

Eine Modulo-Operation im binären kann mit einer Polynomdivision gleichgesetzt werden. Das liefert für die gezeigten Polynome dann das folgende Ergebnis: