CRC-Generator: Woher kommen die Gleichungen?

[Franco (Gast)]

Hallo Leute,

ich habe bei OutputLogic.com einen VHDL-Code für die CRC-Berechnung in 
einem Ethernet-MAC generiert. Eines würde mich mal brennend 
interessieren.
Das Polynom wird irgendwie auf XOR-Gleichungen abgebildet.
Beispiel:

  -- polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
    lfsr_c(0) <= lfsr_q(24) xor lfsr_q(30) xor data_in(0) xor data_in(6);
    lfsr_c(1) <= lfsr_q(24) xor lfsr_q(25) xor lfsr_q(30) xor lfsr_q(31) xor data_in(0) xor data_in(1) xor data_in(6) xor data_in(7);
    lfsr_c(2) <= lfsr_q(24) xor lfsr_q(25) xor lfsr_q(26) xor lfsr_q(30) xor lfsr_q(31) xor data_in(0) xor data_in(1) xor data_in(2) xor data_in(6) xor data_in(7);
    lfsr_c(3) <= lfsr_q(25) xor lfsr_q(26) xor lfsr_q(27) xor lfsr_q(31) xor data_in(1) xor data_in(2) xor data_in(3) xor data_in(7);
...

Wie funktioniert das? Wie ergeben sich die XOR-Gleichungen aus dem 
Polynom?
Beispiel:

    lfsr_c(0) <= lfsr_q(24) xor lfsr_q(30) xor data_in(0) xor data_in(6);

Wie stehen die Bitnummern 24, 30, 0 und 6 mit dem Polynom in 
Zusammenhang?

[Mike (Gast)]

Es ist ein Generatorpolynom definiert, das im Galois-Feld arbeitet. 
Daher auch die XOR-Verknüpfung.
Im GF(2) ist:

$$0 + 0 = 0$$

$$0 + 1 = 1$$

$$1 + 0 = 1$$

$$0 + 0 = 1$$

[Mike (Gast)]

Fehler in der letzten Zeile^^
Sie sollte so aussehen:

$$1 + 1 = 0$$

[Xenu (Gast)]

XOR ist einfach eine bitweise Addition.

[berndl (Gast)]

http://www.ross.net/crc/download/crc_v3.txt

Das beste was ich zu dem Thema bisher gelesen habe (~20 Jahre alt!)

[Inder Preter (Gast)]

Ja, damals wurde im Netz noch Gutes geschrieben, ohne Grafick, Smeilies 
und andere Sch...sse.

Hauptsächlich die Leute von den Unis waren aktiv. Damals wurden 90% der 
Info hochgeladen, die heute als Internetprimärwissen gelten.

Danach kamen erst die Wirtschaftler, die Hausfrauen und die 
Schweinkramindustrie auf die Idee, das Netz zuzuspammen. Schliesslich 
noch die Abzockanwälte.

[Jackson Farmer (Gast)]

>Wie stehen die Bitnummern 24, 30, 0 und 6 mit dem Polynom in
Zusammenhang?

Wenn Du einen bit-seriellen CRC-Generator hättest, d.h. immer nur 1 Bit 
pro Takt, wäre dieser einfach und gut verständlich aufgebaut:
Schieberegister mit XOR an jeder '1' des Generator-Polynoms.

Dein Code verarbeitet aber 8 Bits auf einmal pro Takt. D.h. es werden 
quasi 8 Takte des bit-seriellen Generators in einen einzigen Takt 
hineinoptimiert, weshalb sich eine aufwendige Verknüpfungslogik ergibt. 
Wie sich diese Gleichungen berechnen, weiß ich auch nicht, aber es ist 
sicherlich reichlich mathematisch.

[Lattice User (Gast)]

Jackson Farmer schrieb:
> Wie sich diese Gleichungen berechnen, weiß ich auch nicht, aber es ist
> sicherlich reichlich mathematisch.

Es gab mal eine Zeit da hat man sowas in der Schule gelernt, nannte sich 
Algebra. Einfach einsetzen und vereinfachen, so etwa:
c = a + b
d = c + b
->
d = a + 2 * b.

Für die CRC Berechnung also einfach Gleichungen für jede einzele 
Shiftoperation aufschreiben und nach viel Schreibarbeit kommt man zu 
Ergebniss.

[Franco (Gast)]

Lattice User schrieb:
> Es gab mal eine Zeit da hat man sowas in der Schule gelernt, nannte sich
> Algebra.
Verdammt, und ich dachte, so nahe an der Hardware gäbe es keine 
Mathematik mehr... ;)
Danke an alle.

[Matthias (Gast)]

Das dazu passende Stichwort lautet "Kanalcodierung".

[Franco (Gast)]

Franco schrieb:
> Wie funktioniert das? Wie ergeben sich die XOR-Gleichungen aus dem
> Polynom?

Schön doof!
Auf outputlogic.com wird das ja sogar erklärt!
http://outputlogic.com/?p=158
Wer lesen kann, ist klar im Vorteil...

[Franco (Gast)]

Lattice User schrieb:
> Es gab mal eine Zeit da hat man sowas in der Schule gelernt, nannte sich
> Algebra. Einfach einsetzen und vereinfachen, so etwa:
Von wegen! Das ist seriöser mathematischer Geheimscheiß!