CRC Logik

[itportal2]

Hallo alle,

Kann mir jemand vielleicht erklären, wie eine CRC Logik Implementierung aus einem Generatorpolynom erstellt wird?
Ich kann irgendwie Folie 50, VL 2 (Zeichencodierung) nicht verstehen. Gibt es irgendwelche Zusammenhänge zwischen die Nullen und Einsen beim Generatorpolynom und Logikaufbau?

Clipboard01.png (9.55 KiB) 1449 mal betrachtet

[Steven]

Für mich sieht das angehängte Bild wie folgt aus:
Hier wird ein bitweises XOR mit dem Generatorpolynom 1011 (x^3 + x +1) gemacht. Das erste Bit wird geXORt und dann in a gespeichert (FlipFlop o.ä.). Eigentlich käme jetzt das nächste XOR-Gatter oder Schaltnetz, um dessen Ergebnis wieder in B zu speichern. Da a XOR 0 aber immer a ist kann man sich das sparen und einfach a durchreichen. Danach geht es normal mit einem XOR weiter, das nächste Bit ist ja wieder 1. Das Ergebnis landet in C.
Das letzte Bit wird wieder an den Anfang durchgereicht, das entspricht dem Übertrag wenn du es per Hand aurechnest. Um Bauteile zu sparen hat man den letzten XOR 1 dann gleich in den nächsten Durchlauf integriert. Das geht, weil erstes und letztes Bit des Generatorpolynoms gleich sind. Per Hand machst du einen XOR 1, schreibst den Übertrag hin, füllst auf und machst wieder ein bitweises XOR 1, also betrachtest du das erste Bit zweimal. In der Hardware spart man sowas möglichst ein.

[itportal2]

Hm ... logisch.
Das Generatorpolynom ist Umgekeht - nicht 1011, sondern 1101 (steht in der Folie).
Aber was wenn das Letzte/Erste Ziffer eine Null ist? Dann können wir denselben XOR Baustein nicht benutzen und deswegen müssen wir direkt zu a weiterleiten? Oder?

[Steven]

Bevor ich deinen Post gesehen habe, habe ich habe meinen Post eben noch mal präzisiert (letzten Absatz erweitert).
Der ReUse geht wirklich nur, wenn erstes und letztes Bit gleich sind. Sie dürfen auch beide 0 sein, das ändert nichts am Prinzip.

[itportal2]

Ist das dann richtig?

Clipboard03.png (6.77 KiB) 1397 mal betrachtet

[Steven]

Das geht so nicht, in ein FlipFlop kannst du exakt ein Bit schreiben, in deiner Zeichnung ist die Leitung aber zwei Bit breit. Einfach beide Kabel zusammenlöten geht auch nicht

Außerdem erfolgt die Rückleitung im Beispiel nicht nur an das erste XOR, da der Übertrag meistens länger als 1 Bit ist. Der Unterschied ist nur, dass das letzte Bit in jedem Fall umgeleitet wird, von den anderen Bits wird ein 000... Präfix entfernt. Von 00010 wird nur 10 übernommen, der Rest wird vom Datenstrom aufgefüllt. Andernfalls könntest du nie auffüllen, da deine gesamte Bitbreite von Nullern belegt wird.

Die Zeichnung ist ein Schema, auch wenn ich es mit Gattern erklärt habe. In diesem Sinne würde ich die erste Rückleitung in deiner Zeichnung einfach oben an das "FlipFlop" malen. Um die Schaltung wirklich zu implementieren muss man noch ein bisschen was tun (Blöcke explizitieren).

[itportal2]

Ich habe vergessen die XORs mit der obigen Leitung zu verbinden. Egal. Ist auch falsch.
Also, es gibt kein Muster für CRC Logik Implementierung (das war auch meine Frage).

[Steven]

Ich bin von der manuellen Methode ausgegangen und habe daraus eine Schaltung gebaut bzw. eine bestehende Schaltung darauf zurückgeführt. Das erfordert natürlich etwas Vorsicht, um keine Fehler zu machen. Eine Schema F-Methode gibt es also tatsächlich nicht.

[Krümelmonster]

Wie berechnet sich aus dem Polynom D(x) das Generatorpolynom G(x)?

[bashFish]

@itportal
http://www.inf.fh-flensburg.de/lang/alg ... rc/crc.htm
ich find dort wird es ziemlich deutlich etwas unterhalb der mitte ist eine "allgemeine" skizze

@kruemel
generatorpolynom ist vorher festgelegt

[Krümelmonster]

Danke, aber ausgerechnet jetzt ist die Seite down.

[seth2k1]

http://209.85.135.104/search?q=cache:Ng ... =firefox-a

[Krümelmonster]

Achja, Google gibts ja auch noch.