Direkt zum Inhalt

Lexikon der Mathematik: CRC Code

ein fehlererkennender Code, bei dem eine zu übertragende n-Bit Nachricht M als Polynom M(x) vom Grad n – 1 über dem Körper ℤ2 interpretiert und in ein Polynom P(x) vom Grad n + k – 1 transformiert wird, welches teilbar durch ein Polynom C(x) vom Grad k ist. Hierbei ist C(x) ein für den Code festes Polynom über ℤ2.

Wird P(x) nun über einen Kanal übertragen, so überprüft der Empfänger, ob das empfangene Polynom durch C(x) teilbar ist. Ist dies nicht der Fall, so wurde das Signal P(x) während der Übertragung gestört. Ist das empfangene Signal durch C(x) teilbar, so geht der Empfänger davon aus, daß während der Übertragung keine Störung vorlag und decodiert das empfangene Signal. Durch geschickte Wahl des Polynoms C(x) erhält man sehr leistungsfähige fehlererkennende Codes.

Das zu einer Nachricht M(x) gehörige Polynom P(x) wird wie folgt gewählt. In einem ersten Schritt wird das Polynom M(x) mit xk multipliziert. Das so erhaltene Polynom xk · M(x) wird durch C(x) dividiert. Ist E(x) der Rest dieser Polynomdivision, so ist das Polynom

\begin{eqnarray}{x}^{k}\cdot M(x)-E(x)\end{eqnarray}

durch das Polynom C(x) teilbar und wird als das gesuchte Polynom P(x) gewählt.

Wählt man zum Beispiel k = 3 und C(x) = x3 + x2 + 1, so erhält man das zu der 8-Bit Nachricht M = 10011010, die als das Polynom M(x) = x7 + x4 + x3 + x1 interpretiert wird, gehörige Polynom P(x), indem zuerst M(x) mit x3 multipliziert wird und das so erhaltene Polynom x10 + x7 + x6 + x4 durch x3 + x2 + 1 dividiert wird.

Der Rest E(x) dieser Polynomdivision ist gleich x2 + 1, sodaß sich P(x) durch x10 + x7 + x6 + x4 + x2 + 1 ergibt.

Der CRC Code von M = 10011010 bzgl. des Polynoms C(x) = x3 + x2 + 1 ist somit gleich

\begin{eqnarray}P=10011010101.\end{eqnarray}

[1] Peterson, L.; Davie, B.: Computer Networks. Morgan Kaufmann Publishers, San Mateo, USA, 1996.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos