CRC Logik

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

CRC Logik

Beitrag von 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
Clipboard01.png (9.55 KiB) 1358 mal betrachtet

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: CRC Logik

Beitrag von 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.
Zuletzt geändert von Steven am 16. Sep 2008 09:55, insgesamt 1-mal geändert.

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: CRC Logik

Beitrag von 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
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: CRC Logik

Beitrag von 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.

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: CRC Logik

Beitrag von itportal2 »

Ist das dann richtig?
Clipboard03.png
Clipboard03.png (6.77 KiB) 1306 mal betrachtet

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: CRC Logik

Beitrag von 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).

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: CRC Logik

Beitrag von 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
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: CRC Logik

Beitrag von 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.

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: CRC Logik

Beitrag von Krümelmonster »

Wie berechnet sich aus dem Polynom D(x) das Generatorpolynom G(x)?
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

bashFish
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 3. Okt 2007 17:38

Re: CRC Logik

Beitrag von 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

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: CRC Logik

Beitrag von Krümelmonster »

Danke, aber ausgerechnet jetzt ist die Seite down.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
seth2k1
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 29. Sep 2006 00:53
Wohnort: Darmstadt - Eberstadt

Re: CRC Logik

Beitrag von seth2k1 »

"Hallo, ich verkaufe diese modischen Lederjacken!"

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: CRC Logik

Beitrag von Krümelmonster »

Achja, Google gibts ja auch noch.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Antworten

Zurück zu „Archiv“