CRC Berechnung in Hardware mittels LFSR

[M. Н. (Gast)]

Hallo,

ich muss zugeben, ich habe gestern Abend über CRC sinniert und bin an 
ein gedankliches Problem gestoßen, dass sich auch über nacht noch nicht 
verflüchtigt hat. Und zwar geht es mir um die praktische Implementierung 
einer bitweisen CRC:

Wenn ich eine CRC mit einem Polynom (n+1)-ten Grades händisch berechne, 
dann hänge ich n Nullen an meine Nachricht an und arbeite mich fleißig 
mit der Polynomdivision durch.

Der Rest am Ende ist meine CRC, die ich an die Nachricht hängen kann.

Der Empfänger kann nun mit dem selben Algorithmus, ohne die Nachricht 
mit Nullen aufzufüllen dasselbe tun und schauen, ob das Ergebnis null 
ist.

Die hardwareseitige Implementierung mittels eines Schieberegisters und 
den rückgekoppelten XOR zweigen ist soweit klar.

Allerdings habe ich auch bei dieser Hardware-Implementierung die 
Eigenschaft, dass ich nach meiner Nachricht noch n Nullen 
hinterherschieben muss, bevor ich das CRC Ergebnis auslesen kann.

Oraktische Implementierungen kenne ich als Anweder allerdings so, dass 
ich dieses Anhängen nicht machen muss, sondern einfach nur die m 
Nachrichten bits durchschaufeln muss und danach bekomme ich n CRC bits.

Wenn ich danach alle m Nachrichtenbits + n CRC-bits durch den selben 
Algorithmus laufen lasse, ist bei einer validen CRC das Ergebnis dann 0.

Ich muss also bei keiner Implementierung, die ich je benutzt habe, 
manuell zeischen der "Generierung" der CRC und der Prüfung 
unterscheiden, was aber bei einem LFSR, wie es in der Literatur 
beschrieben ist, notwendig ist, da beim "Generieren" nach nullen 
durchgeschoben werden müssen.

Kann mir jemand da gedanklich auf die Sprünge helfen?

Vielen Dank

[Duke Scarring (Gast)]

M. H. schrieb:
> Und zwar geht es mir um die praktische Implementierung
> einer bitweisen CRC
Ich habe praktisch immer nur byteweise CRC implementiert.

> manuell zeischen der "Generierung" der CRC und der Prüfung
> unterscheiden
Ich mußte schon unterscheiden. Beim Erzeugen wird die 'Prüfsumme' 
weggelassen. Bei der Prüfung dagegen, muß sie beachtet werden.
Die Nachricht ist bei der Prüfung um die Größe des CRC (8 Bit, 16 Bit 
oder 32 Bit) länger.

Duke

[ChristophZ (Gast)]

M. H. schrieb:
> Wenn ich eine CRC mit einem Polynom (n+1)-ten Grades händisch berechne,
> dann hänge ich n Nullen an meine Nachricht an und arbeite mich fleißig
> mit der Polynomdivision durch.

Bist du sicher?

Ich habe bisher immer nur die Nachricht durchs LFSR geschoben und dann 
hast du die CRC als paralleles Wort im Register drin.

Wenn die CRC auch bit-seriell ausgegeben werden soll, muss man am 
Schluss natürlich noch n Takte hinzufügen, damit sie hinten rauspurzelt.

Beim Prüfen ähnlich. Zwei Möglichkeiten:
- Nachricht ohne CRC durchschieben und dann den Inhalt des LFSR mit der 
CRC vergleichen
- Nachricht und CRC durchschieben und dann den Inhalt des LFSR mit 0 
vergleichen

[M. Н. (Gast)]

Ich habe meinen gedanklichen Knoten nun gelöst.

Es gibt zwei Möglichkeiten das Schieberegister zu bauen:
https://stackoverflow.com/questions/25415724/understanding-two-different-ways-of-implementing-crc-generation-with-lfsr

Die Option (B) ist die "Lehrbuch" Version, die quasi 1-zu-1 der 
Polynomdivision entspricht. Hie rmüssen die 0-bytes angefügt werden.
Die andere Option (A) ist die sogenannte "direkte" Form. Diese besitzt 
die Eigneschaft, dass keine Padding Bytes mehr bei der Generierung 
benötigt werden.

Nachzulesen hier: https://zlib.net/crc_v3.txt unter "10. A Slightly 
Mangled Table-Driven Implementation". Der Abschnitt ist zwar für die 
Tabellenbasierte berechnung auf Byte Ebene, aber die Begründung gilt 
auch für die bitweise CRC.

[Michael W. (Gast)]

aha!