Wie berechnen Sie die XOR-Rest in CRC verwendet?

Question

Ich versuche, daran zu erinnern, wie die Mathematik ausgearbeitet wird, um den Rest eines XOR-Algorithmus in Cyclical Redundancy Checks zu berechnen, die restlichen Bits einer Netzwerknachricht zu überprüfen.

Ich habe diesen Text Buch nicht geworfen.

Dies ist leicht in Code getan, aber wie ist es funktioniert von Hand aus?

Ich weiß es so etwas wie ein Standard-Divisions-Algorithmus aussieht, aber ich kann mich nicht erinnern, wo von dort aus zu gehen, um den Rest zu erhalten.

      ___________
1010 | 101101000

. Hinweis: habe ich es googeln, war aber nicht in der Lage, einen Platz zu finden, wo sie die Schritte in Bezifferung der Rest abgebildet

Answer 1

Es ist eine Division durch binäre 11. Es ist ein Beispiel auf Wikipedia .

Answer 2

1010 | 101101000
       1010
       0001 this result is 1011 XOR 1010 = 0001
          1010
          1010
          0000  thus no remainder. 

So 101101000 ist perfekt und kein Fehler in Sende- / Empfangs

aufgetreten

Answer 3

Nach meiner Erfahrung ist es einfacher, es zu einem Polynom zu konvertieren, wenn sie von Hand zu berechnen, vor allem, wenn es eine Menge Nullen ist.

1010 = 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3 + x = x3 + x
101101000 = x8 + x6 + x5 + x3

       -------------------
x3 + x ) x8 + x6 + x5 + x3

Dann Sie teilen Sie den größten Begriff in der Dividende (x^8) mit dem ersten Term in dem Divisor (x^3), was zu x^5. Sie setzen diese Zahl auf und dann multiplizieren es mit jedem Begriff in der Divisor . Daraus ergibt sich folgende für die erste Iteration:

        x5
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6

Doing XOR für jeden Begriff ergibt dann die neue Dividende: x5 + x3:

        x5
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6
       -------------------
         x5 + x3

Folgen Sie dem gleichen Muster, bis der größte Begriff Dividenden kleiner ist dann der größte Ausdruck der Divisor. Nachdem die Berechnungen abgeschlossen sind, wird es wie folgt aussehen:

        x5 + x2
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6
       -------------------
         x5 + x3
         x5 + x3
       -------------------
         0

Die Erinnerung ist in diesem Fall 0, was die höchstwahrscheinlich keine Fehler während der Übertragung aufgetreten ist, zeigen würde.

Hinweis: Ich habe x^y als xy im Beispiel verkürzt über die Unordnung in der Antwort zu reduzieren, da SO keine mathematische Gleichung Formatierung unterstützen.

Hinweis 2:. Hinzufügen / ein Vielfaches der Divisor vom Dividenden subtrahiert wird auch die Erinnerung 0 geben, da (P(x) + a*C(x)) / C(x) = P(x)/C(x) + a*C(x)/C(x) die gleiche Erinnerung wie P(x)/C(x) gibt, da die Erinnerung an a*C(x)/C(x) 0