Frage zur Zyklischen Redundanzprüfung (CRC)

[arenas]

Hallo,
ich beschäftige mich gerade mit der Zyklischen Redundanzprüfung (CRC). Dabei arbeite ich mich gerade durch folgenden Artikel:
- https://de.wikipedia.org/wiki/Zyklische_Redundanzprüfung

Mit folgendem Absatz habe ich jedoch ein Problem:

Die Berechnung des CRC-Werts beruht auf Polynomdivision: Die Folge der zu übertragenden Bits wird als binäres Polynom betrachtet. Beispiel: Die Bitfolge 1,0,0,1,1,1,0,1 entspricht dem Polynom
$1\cdot x^7 + 0 \cdot x^6 + 0 \cdot x^5 + 1 \cdot x^4 + 1 \cdot x^3 + 1 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0 = x^7 + x^4 + x^3 + x^2 + 1$

Warum wird die Bitfolge als binäres Polynom betrachtet und warum nicht einfach als eine normale Binärzahl?

Wozu braucht man die Variablen und Exponenten?

Ich hoffe ihr könnt mir da weiterhelfen.

Vielen Dank,
MfG arenas

[SeppJ]

arenas schrieb:

Wozu braucht man die Variablen und Exponenten?

Für gar nichts. Aber Mathematiker haben das Konzept von Division und Subtraktion (und anderer Rechenoperationen) verallgemeinert gegenüber dem, was man in der Grundschule lernt, und können dies auf allerlei Arten von Objekten anwenden. Eine solche Art von Objekten sind Polynome und es gibt eine recht naheliegende Art und Weise, wie man mit diesen rechnen kann, also wie man Polynome durcheinander teilen und voneinander subtrahieren kann.

Wenn man irgendwelche Bitfolgen A und B nimmt und diese als Polynom interpretiert und dann A/B ausrechnet, kommt ein anderes Polynom heraus, das man dann umgekehrt wieder als eine gewisse Bitfolge C interpretieren kann. Interpretiert man hingegen A und B als binäre Darstellungen von Zahlen und rechnet A/B aus, kommt eine Zahl heraus, die man auch wieder binär als Bitfolge D darstellen kann. Im Allgemeinen wird dabei C ungleich D sein!

Die Eigenschaften der Rechenvorschriften für Polynome sind dabei besonders gut geeignet für den Zweck der Fehlerkorrekturcodes. Und sie sind zudem auch noch besonders gut geeignet, um in einem typischen Computerprozessor effizient umgesetzt zu werden. Eine Erklärung, warum das so ist, gibt es beispielsweise hier:
https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks

[krümelkacker]

Bei CRCs rechnet man eben mit Polynomen statt mit Ganzzahlen. Du kannst Polynome multiplizieren, die Division mit Rest bestimmen, addieren, subtrahieren. Man könnte das alles auch mit Ganzzahlen machen. Mir fallen dann aber spontan zwei Nachteile gegenüber den Polynomen ein.

In jedem Fall ist die Prüfsumme ein Divisionsrest. Bei Ganzahlen bezüglich einer Primzahl und bei Polynomen bezüglich eines "irreduziblen Polynoms" (quasi ein "Primpolynom"). Dass man hier Primzahlen oder irreduzible Polynome verwendet, hat was damit zu tun, dass dadurch "bessere" Prüfsummen rauskommen, über die man Bitfehler mit höherer Wahrscheinlichkeit detektieren kann.

Für eine 16-Bit Prüfsumme basierend auf Ganzzahlarithmetik könnte man als Primzahl 65521 nehmen. Dann ist der Divisionsrest immer zwischen 0 und 65520. Nachteil 1: Dadurch werden die 16 Bit nicht optimal ausgenutzt. Die Prüfsummen 65521-65535 werden nie auftauchen. Nachteil 2: Die Implementierung von solchen Prüfsummen in Hardware ist viel komplizierter. Man muss hier wirklich dividieren können. Division ist teuer und kostet viele Transistoren/Zeit.

Mit Polynom-Arithmetik hätte man diese Probleme nicht. Da könnte man für eine 16-Bit-Prüfsumme als irreduzibles Polynom x^16+x12+x^5+x1 nehmen. Die Berechnung des Divisionsrest bzgl dieses Polynoms ist einfach (ein paar XORs und Shifts) und der mögliche Divisionsrest als Folge von 16 Bits kodiert deckt alle 2^16 Möglichkeiten ab.

HTH.