Fehler bei Wikipedia: Zyklische Redundanzprüfung (CRC)



  • Hallo zusammen,

    ich beschäftige ich mit der CRC. Auf Wikipedia steht ein Algorithmus, mit dem man solch eine Prüfung in Hardware leicht implementieren kann.

    http://de.wikipedia.org/wiki/Zyklische_Redundanzprüfung#Implementierung

    Entweder ich stelle mich total blöd an oder dieser Algorithmus funktioniert nicht.

    Beispiel: Seien das CRC-Polynom = 110101, Schieberegister: S := 000000 und der Rahmen: 1101100000 (11011 sind die zu übertragenden Daten und die fünf Nullen müssen angehängt werden, da das CRC Polynom den Grad 5 hat)

    Durch herkömmliche Polynomdivision komme ich auf ein Ergebnis von 101 (Rest). Beim Ausführen des genannten Algorithmus' komme ich aber zu folgendem Ergebnis:

    Linke Zahl = aktuelles Bit des Rahmen
    rechte Zahl = msb des Schieberegisters

    ________S := 000000
    1 != 0 ==> S := 110101
    1 == 1 ==> S := 101010
    0 != 1 ==> S := 100001
    1 == 1 ==> S := 000010
    1 != 0 ==> S := 110001
    0 != 1 ==> S := 010111
    0 == 0 ==> S := 101110
    0 != 1 ==> S := 101001
    0 != 1 ==> S := 100111
    0 != 1 ==> S := 111011

    Der letzte Wert des Schiebregisters ist nun 111011 und das ist definitiv falsch.

    Weiß jemand, wo der Fehler liegt?

    Danke und lg,
    freakC++



  • Die führende 1 für die höchste Potenz des Polynoms lässt immer Weg, wenn man das Polynom als Zahl ausdrückt. Das wär ja im 32Bit-CRC Fall dann auch eine 33-Bit Zahl (also ein Polynom 32. Grades mit x^32 als höchste und x^0 als kleinste Pozenz).

    Wenn du den von dir verlinkten Algo startest, rechtest du tatsächlich mit dem Polynom x6+x5+x4+x2+x^0, also einem Polynom 6. Grades. Dann macht es auch Sinn, dass du mit einem Schieberegister von 6 Bits rechnest, wobei du bei deiner Nachricht dann auch 6 statt 5 Nullen hättest dranhängen müssen. Das Dranhängen der 6 Nullen ist aber im Algorithmus schon implizit mit eingebaut und brauchst du vorher gar nicht machen.

    Also:

    CRC-Poly  = 110101 (ohne führende 1 für die höchste Potenz)
    Nachricht = 11011
    
     Eingabe     Register
    ----------------------
                  000000  (Initialzustand)
        1
                  000000  (geshiftet)
                ^ 110101  (XOR mit Poly weil Eingabe^rausgefallenes Bit==1)
                --------
                  110101
        1
                  101010  (geshiftet)
        0
                  010100  (geshiftet)
                ^ 110101  (XOR mit Poly weil Eingabe^rausgefallenes Bit==1)
                --------
                  100001
        1
                  000010  (geshiftet)
        1
                  000100  (geshiftet)
                ^ 110101  (XOR mit Poly weil Eingabe^rausgefallenes Bit==1)
                --------
                  110001
    
    ==> 110001 ist die CRC-Prüfsumme 
    ==> 110001 ist der Divisionsrest von 11011000000:1110101
    
    Probe:
    
      11011000000
      1110101
        110010000
        1110101
          1000100
          1110101
           110001
    
    Passt.
    


  • Hallo krümelkacker!

    Danke für deine Mühe. Bedeutet das, dass beim von mir verlinkten Algorithmus stets die führendre 1 des CRC-Polynoms weggelassen wird? Wenn Du nämlich mal hochscrollst, so siehst Du ein Beispiel, das mit der herkömmlichen Polynomdivision rechnet. Hierbei wird das Polynom

    1x5+1x4+0x3+1x2+0x1+1x01x^5 + 1x^4+0x^3+1x^2+0x^1+1x^0

    verwendet. Binär wird schließlich mit 110101 gerechnet. Hier wird die führende Eins also nicht weggelassen.

    Wie kann das sein?

    Vielen Dank und herzliche Grüße
    freakC++



  • freakC++ schrieb:

    Danke für deine Mühe. Bedeutet das, dass beim von mir verlinkten Algorithmus stets die führendre 1 des CRC-Polynoms weggelassen wird?

    Ja, hab ich doch gesagt und sogar vorgerechnet.

    freakC++ schrieb:

    Wenn Du nämlich mal hochscrollst, so siehst Du ein Beispiel, das mit der herkömmlichen Polynomdivision rechnet. Hierbei wird das Polynom

    1x5+1x4+0x3+1x2+0x1+1x01x^5 + 1x^4+0x^3+1x^2+0x^1+1x^0

    Die entsprechende Polynomdivision habe ich hier ja auch gemacht, mit x6+x5+x4+x2+1.

    freakC++ schrieb:

    Wie kann das sein?

    Ich verstehe Dein Problem nicht.

    Wenn Du deren Polynomdivisionsbeispiel mit dem darunter beschriebenen Algorithmus nachrechnen willst, musst du als "crc poly"-Konstante 10101 und ein Schieberegister mit 5 Bits verwenden.

    Zugegeben. Das geht aus diesem Artikel nicht deutlich hervor. Aber du darfst ihn ja gerne dahingehend verbessern. Der erwähnte Wert 0x04C11DB7 ist der, mit dem du für CRC-32 den Zustand verXORen musst, steht aber für das Polynom x32+x26+x^23... also eigentlich 0x104C11DB7, nur passt das offensichtlich nicht mehr in 32 Bit rein.



  • krümelkacker schrieb:

    Ich verstehe Dein Problem nicht.

    Mein Problem ist, dass man anscheinend bei der Polynomdivion auf dem Blatt die führende Eins nicht weglässt, aber der verlinkte Algorithmus nur funktioniert, wenn ich die führende Eins streiche.

    Und da wollte ich nur noch mal um Bestätigung fragen. Nicht, dass ich hier etwas Falsches verstehe 🙂


Log in to reply