Usb Checksumme (CRC5)

[Johannes T. (johnsn)]

Hallo!

Ich versuche gerade die - an sich einfache - CRC5 für Usb in VHDL zu 
implementieren. Begonnen hätte ich mal damit die Polynomdivison händisch 
durchzuführen, allerdings komme ich da auf kein gültiges Resultat.

Was mich dabei verwirrt ist die Sache, dass Usb, die einzelnen 
Informationen LSB first schickt. Bedeuted das jetzt das das 
Generatorpolynom x5+x2+1 (100101) auch gespiegelt werden muss?

Warum wird im USB2.0 Standard erwähnt, "The binary bit pattern that 
represents this polynomial is 00101B", obwohl das doch 100101 sein 
müsste?

Beispiel aus http://www.usb.org/developers/whitepapers/crcdes.pdf

LSB       MSB
|           |
1000.0000.000 ... 11 Bit, die geprüft werden sollen.
1001.01       ... Generatorpolynom CRC5 (Usb)

Berechnung:

1000.0000.0000.0000
1001.01
--------
   1.0100.0
   1.0010.1
   --------
      110.100
      100.101
      -------
       10.0010.
       10.0101.
       --------
           111.000
           100.101
           -------
            11.1010
            10.0101
            -------
             1.1111 ... CRC5
       
Rückrechnung (check):

1000.0000.0001.1111
1001.01
-------
   1.0100.0
   1.0010.1
   --------
      110.100
      100.101
      -------
       10.0011.
       10.0101.
       --------
           110.111
           100.101
           -------
            10.0101
            10.0101
            -------
                  0 ... korrekt!

In diesem Whitepaper (siehe Link) steht aber, dass die Checksumme 10111 
sein sollte und nicht 11111. Allerdings stimmt doch meine Berechnung, 
oder wo liegt hier ein Fehler?

[Alban (Gast)]

Hast du dir mal das Projekt auf opencores angesehen um zu vergleichen 
wie es dort gemacht wird?

Vieleicht hilft das ja?

[Johannes T. (johnsn)]

Hi,

danke für den Tipp. Wenn du das Projekt "USB 1.1 Host and Function IP 
core" in Verilog geschrieben meinst, ja! Der Kollege lässt sich hier 
aber die Checksumme rein kombinatorisch ausrechnen, was meiner Meinung 
nach sehr ineffizient ist und zuviel Platz braucht. Die Implementierung 
funktioniert zwar (portiert auf VHDL und Modelsim), aber ich würde das 
ganze gerne mit Registerstufen machen und darüber hinaus meinen 
Denkfehler finden.

Bin für jeden Ratschlag dankbar.

[Alban (Gast)]

Ich nehme mal deinen 1. Post:

>Was mich dabei verwirrt ist die Sache, dass Usb, die einzelnen
>Informationen LSB first schickt. Bedeuted das jetzt das das
>Generatorpolynom x5+x2+1 (100101) auch gespiegelt werden muss?

Nein. Der CRC wird immer in der gleichen Reihenfolge berechnet. Am 
einfachsten kannst du dir das mit einer LFSR Implementierung vorstellen. 
Wenn jetzt wie bei USB die Daten LSB first geschickt werden, dann kommt 
als 1. Bit das LSB an, aber am Polynomial wird nichts gedreht.

>Warum wird im USB2.0 Standard erwähnt, "The binary bit pattern that
>represents this polynomial is 00101B", obwohl das doch 100101 sein
>müsste?

Ich hab hier ein Buch "Advanced Digital Logic Design" von Sunggu Lee, da 
beschäftigt sich ein Kapitel mit einem USB Analysator. Dort steht 
geschrieben:

"... the 5-bit generator polynomial used is G5(x) = x^5 + x^2 + 1 (= 
00101 as a 5-bit vector; the x^5 position is implicit)."

Vielleicht hilft das die andere Bitfolge zu erklären?

Zur Berechnung, die in dem Buch über LFSR beschrieben wird, dort werden 
alle Register auf 1 initalisiert. Jetzt weiss ich nicht genau wie du das 
bei deiner Berechnung einbauen musst.

Vielleicht hilft das etwas.

[Johannes T. (johnsn)]

@Alban:

- Das mit der Reihenfolge ist mir jetzt klar.
- Die Sache mit x5 + x2 + 1 = 00101, auch.

Doch trotzdem komme ich mit der händischen Berechnung (siehe oben) nicht 
auf das gewünschte Ergebnis, obwohl der CRC-Check beim Empfänger ja dann 
richtig ist!

Eine Implementierung habe ich auch bereits gemacht, nämlich genau mit 
LFSR, dabei kann man die CRC quasi rücksetzen und für ein neues Paket 
bereit machen, indem man alle Register auf 1 setzt. Das gemeine ist 
jetzt, das diese Implementierung auch funktioniert, ich will das ganze 
aber auch händisch berechnen können.

[Alban (Gast)]

Ich hab mal das folgende Beispiel von dem Dokument das du angegeben hast 
durchgerechnet und es scheint zu stimmen.

crc5 1000 0000 000
10111

Beide Werte scheinen mit LSB links geschrieben zu sein. Da alle Register 
im LFSR auf 1 initalisiert werden, hab ich das der Berechnung 
vorangestellt.

Für die Berechnung ist jetzt LSB rechts:

1111.1110.0000.0000.0
1001.01
-------
 110.101
 100.101
 -------
  10.0000
  10.0101
  -------
      101.000
      100.101
      -------
        1.1010.0
        1.0010.1
        --------
          1000.10
          1001.01
          --------
             1.1100.0
             1.0010.1
             --------
               1110.1   <--- Rest  [msb..lsb]

In dem Dokument gehe ich davon aus das der Rest genauso wie der 
Eingabewerte [lsb..msb] angeben ist.

[Johannes T. (johnsn)]

Danke vielmals!! Soweit hab ich nicht gedacht, dass ich diese 
Initialwerte auch bei der händischen Berechnung berücksichtigen soll. 
Damit wäre der Fall nun gelöst.

Gruß,
Johnsn