Erkannte Fehler

wie das CRC-Polynom zu wählen ist, folgt aus den kommenden Überlegungen.) erkannt, deren Polynomdarstellung einen kleineren Grad als das CRC-Polynom hat.s. Zusätzlich werden alle Fehler (also auch unabhängige Vierbit-, Sechsbit-, Achtbitfehler, u.Ist das CRC-Polynom gut gewählt, können mit dem oben beschriebenen Verfahren alle Einbit- und Zweibitfehler, jede ungerade Anzahl von verfälschten Bits, sowie alle Bündelfehler der Länge erkannt werden, wobei r der Grad des CRC-Polynoms ist.w. Warum das so ist bzw.

Da T(x) / G(x) = 0 (per Definition von T(x)), ist das Ergebnis E(x) / G(x). Wenn der Empfänger die um den CRC-Wert erweiterten Bitfolge erhält, berechnet er (T(x) + E(x)) / G(x). Wenn ein Fehler bei der Übertragung auftritt, kommt (in Polynomdarstellung) beim Empfänger nicht T(x), sondern T(x) + E(x) an.Sei G(x) das CRC-Polynom (Generatorpolynom) und T(x) die Polynomdarstellung der um den CRC-Wert erweiterten zu übertragenden Bitfolge. Die zu E(x) gehörende Bitfolge hat an jeder Bitposition, die bei der zu übertragenden Bitfolge invertiert bzw. verfälscht wurde, eine 1.

Wenn ein Einbitfehler aufgetreten ist, gilt E(x) = xⁱ, wobei i bestimmt welches Bit invertiert ist. Wenn nun G(x) zwei oder mehr Terme enthält, wird G(x) niemals E(x) teilen.

Zum Beispiel teilt x¹⁵ + x¹⁴ + 1 den Term x^k + 1 nicht für jedes k kleiner 32768. einfache Polynome geringen Grades, die eine sichere Übertragung für lange Rahmen ermöglichen, sind bekannt.B. Angenommen, G(x) ist nicht durch x teilbar (z.Sind zwei isolierte Einbitfehler aufgetreten, gilt E(x) = xⁱ + x^j, wobei i > j. Klammert man x^j aus, lässt sich dies auch als E(x) = x^j(x^{i − j} + 1) schreiben. wenn G(x) x⁰ enthält), reicht es zu fordern, dass G(x) nicht x^k + 1 teilt (für alle k bis zum maximalen Wert von (j − i), i.e. der maximalen Rahmenlänge).

Bei E(x) / G(x) wird also stehts x oder 1 als Rest bleiben, wenn E(x) ungerade Parität hat. (x + 1) ist das kleinste Polynom mit gerader Parität. Beweis: Bei der Division durch ein Polynom mit gerader Parität (= Anzahl der Therme in dem Polynom, also Anzahl der Einsen in der Bitfolge) bleibt die Geradheit oder Ungeradheit der Parität des Divisors erhalten, denn aus 00 wird 11 und umgekehrt und aus 01 wird 10 und umgekehrt.B.Ist eine ungerade Anzahl von Bits verfälscht, enthät E(x) eine ungerade Anzahl von Termen (z.B. x⁷ + x² + 1, aber nicht z. x² + 1). Wählt man das CRC-Polynom so, dass es (x + 1) als Faktor hat, werden alle Fehler mit einer ungeraden Anzahl von verfälschten Bits erkannt. Damit ist E(x) nicht durch G(x) teilbar.

Der Rest kann niemals 0 sein und der Bündelfehler wird erkannt.h. D. Wenn der Fehler erkannt werden soll, muss die Division von E(x) = xⁱb(x) durch G(x) einen Rest ergeben. Ein Bündelfehler der Länge k lässt sich schreiben als , wobei i bestimmt, wieviele Bitpositionen von der rechten Seite der empfangenen Bitfolge (bzw.Alle Bündelfehler der Länge , wobei r der Grad des CRC-Polynoms ist, werden erkannt. des empfangenen Rahmens) der Bündelfehler entfernt ist. Wenn G(x) einen x⁰ Term enthält, so hat G(x) xⁱ sicher nicht als Faktor., wenn G(x) | xⁱb(x), dann muss G(x) | b(x). Dies ist jedoch nicht möglich, da per Annahme der Grad von b(x) kleiner ist (deg(b(x)) = k − 1) als der Grad von G(x).