mikrocontroller.net

Forum: FPGA, VHDL & Co. CRC - Generatorpolynom


Autor: Torben (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
bin ein neuling in diesem Gebiet und habe Verständigungs probleme.

Habe mir das CRC Verfahren mal angeschaut und habe da so meine
schwierigkeiten.
Also zuerst habe ich probleme mit dem Generatorpolynom, wie komme ich
genau an mein passenden Generatorpolynom, wenn sich die zu übertragende
bit Anzahl von Fall zu Fall ändert?

wenn ich das richtig verstanden habe, dann kann man max 32 bit
übertragen bzw mit crc prüfen, ist das richtig?
was mache ich wenn ich z.B. 118 bit übertragen möchte?

Falls die Fragen zu trivial sind, bitte ich um Links oder Beispiele die
mir weiter helfen könnten, in den meisten Links die ich gefunden habe
wird nur das prinzip erklärt.

Danke
Torben

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine CRC ist letztendlich auch nur eine Polynomdivision und daher dürfen
die zu prüfenden Zahlen natürlich beliebig groß sein.

http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check

Autor: Torben (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wie ist das den wenn sich die grösse meines signals ständig ändert, so
wie ich das verstanden habe muss man vorher ein generatorpolynom
kreieren. meine frage besteht immer noch wie genau, worauf muss ich
aufpassen um ein generatorpolynom zu kreieren? oder wähle ich
wirkürlich einen der dem sender und empfänger bekannt ist und prüfe
jedes signal mit dem selben generatorpolynom, egal wie gross das signal
ist?(da muss man doch bestimmt irgendein gesätz einhalten, oder?)


mfg
torben

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gibt schon Polynome unterschiedlicher Qualität, aber da nimmt man
halt einfach eines das sich bewährt hat. Das steht auch in den Links
die in der Wikipedia angegeben werden.

Man nimmt üblicherweise auch immer das gleiche Polynom, Sender und
Empfänger müssen halt zusammenpassen. Ich denke schon, daß man damit
prinzipiell beliebig lange Bitsequenzen absichern kann, aber dir Frage
stellt sich normalerweise nicht. Normalerweise nutzt es Dir ja nichts,
wenn Du einfach nur weißt, daß die Daten fehlerhaft sind. Du willst die
Daten ja entweder reparieren oder neu übertragen und da wird man kaum
10GByte mit einer einzigen Prüfsumme absichern und im Fehlerfall neu
übertragen.

Es ist aber schon 10 Jahre her seit ich mich mit dem Thema beschäftigt
habe, deswegen kann ich nicht mehr so sehr viel mehr über das Thema
sagen. Die im dem Wiki-Artikel angegebenen Links erklären das Thema
aber recht ausführlich. Und wenn Du gerade am Einarbeiten bist, dann
solltest Du Dir auch noch die Hamming-Distanzen
http://de.wikipedia.org/wiki/Hamming-Abstand ansehen.

Markus

Autor: Torben (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK.
Habe mir die Links angeschaut. also, crc32 entdeckt die fehler, aber
kann sie nicht korregieren oder neu übertragen. dazu benutzt man z.B.
das Hamming-Distanz Verfahren.

Beträgt die Distanz 3, dann lassen sich die 1bit Fehler korregieren.
ist die Distanz 2, so kann man es nicht reparieren.

Das Verfahren habe ich so verstanden, aber ich kann mir das nicht im
Bezug auch eine Datenübertragung vorstellen.
Ist das so, wenn man z.B. 100 bit übertragen möchte, und mit einem
crc32 Verfahren prüft, dann prüfft man quasi immer  in 32 bit
abschnitten? wenn das so ist dann habe ich doch z.B.
so ein Signal
01110001101011001110010110010001 -> 32 bit

Wäre das jetzt ein Wort? und wie würde man hier jetzt genau das Hamming
Distanz Verfahren anwenden?

Wenn man jetzt z.B. noch 2 Wörter dazu geben würde (a 32 bit) so wäre
es ein Code von der Grösse 96 bit. und wenn man jetzt eine Hamming
Distanz von 6 hätte, so könnte man 5 bit Fehler erkennen und 4 Bit
Fehler reparieren. oder?

Und wie kann ich das jetzt genau reparieren oder neu übertragen??

Torben

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Hamming-Distanz ist kein Fehlerkorrekturverfahren, sondern einfach
eine Methode um Fehlersicherung/-korrektur zu bewerten.

Die Hamming-Distanz ist der Abstand zwischen zwei gültigen Codes.
Beträgt die Distanz 1, dann führt jeder Fehler zu einem gültigen Wert,
d.h. man kann Fehler nicht erkennen.
gültig --- gültig

Ist der Abstand 2, dann liegt zwischen zwei gültigen Codes ein
ungültiger Code, d.h. man kann erkennen, daß ein ein Fehler
stattgefunden hat, aber nicht ob er vom linken oder rechten Code
stammt.
gültig --- ungültig --- gültig

Ist der Abstand 3, dann kann man bei Einzelbitfehlern sagen woher sie
kommen und dementsprechend korrigieren. Dazu muß man aber wissen, daß
es wirklich ein Einzelbitfehler war und nicht etwa ein Doppelbitfehler.
Verzichtet man auf das korrigieren, dann kann man auch Doppelbitfehler
erkennen.
gültig --- ungültig --- ungültig --- gültig

Bei einer Hamming-Distanz von 6 kann man 5Bit-Fehler erkennen, aber nur
Doppelbitfehler korrigieren.
g1 - u1 - u2 - u3 - u4 - u5 - g2
Wenn Du z.B. ungültig4 empfängst, dann könnte es entweder ein
Doppelbitfehler von gültig2 oder 4fach-Fehler von gültig1 sein. Wenn
man weiß, daß höchstens Doppelfehler auftreten können, dann weiß man,
der korrekte Code ist g2. Kann man 4fach-Fehler nicht ausschließen,
dann kann man den Fehler nicht korrigieren, denn es könnte ja auch ein
4fach-Fehler von g1 sein. Man kann aber grundsätzlich 6fach-Fehler
nicht erkennen, denn das gibt ja wieder einen gültigen Code.

Grundsätzlich sind Aussagen über die Fehlerwahrscheinlichkeit nicht so
einfach zu machen, deswegen sollte Du auf fehlerkorrigierende Verfahren
besser verzichten.

Ein Beispiel für ein fehlerkorrigierendes Verfahren ist die 2D-Parity:
Stell Dir 8 Bytes angeordnet als 8x8Bit vor. Nun bildet man zu jeder
Spalte und jeder Zeile die Parity. Wenn jetzt ein Fehler auftritt, dann
kann man genau sagen, in welcher Zeile und welcher Spalte das passiert
ist und das entsprechende Bit korrigieren. Natürlich nur bei einem
Einzelbitfehler, bei 2 Fehlern kann man nicht mehr sicher sagen wo das
passiert ist.

Zum neu übertragen:
Du teilst Deine Daten z.B. in Blöcke zu je 1KB auf bildest die CRC über
jeweils einen Block. Ist die CRC falsch, dann forderst Du beim Sender
eben diesen Block nochmals an.

Markus

Autor: Torben (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK.
Wie kann ich den die % Fehlerrate mit der Hamming-Distanz bei einer
CRC32 Prüfung ausrechnen?(ein Beispiel?)
Das Verfahren an sich habe ich denke verstanden. Aber wie soll ich es
anwenden? und die %Fehler bekommen.
Gibt es irgendwo ein Beispiel wie man es genau macht?

Habe mir mal sagen lassen, ich müsste gucken "wie viele Bits
umkippen", was heißt das eigentlich, hat das hiermit zu tun?

Torben




PS.
Hast du vielleicht ein Beispiel Programm das Daten in Blöcke bildet und
........?

Zum neu übertragen:
Du teilst Deine Daten z.B. in Blöcke zu je 1KB auf bildest die CRC über
jeweils einen Block. Ist die CRC falsch, dann forderst Du beim Sender
eben diesen Block nochmals an.

Autor: Marcus Maul (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Torben,

wenn ich sagen wir mal 100 Blöcke (a 1kbit = 1024bit = 128byte = 128
char) übertragen habe, dann weiß ich, auch, wie viele davon zweimal
übertragen worden sind und wie viele nicht. Die Prozent angabe ist
nichts anderes als: ([übertragene Blöcke] - [fehlerhafte
Blöcke])/[übertragene Blöcke] * 100 und davon dann den Betrag.

Zu dem Programm, dass Daten in Blöcke fasst:

char Send[128];

for (char i = 0; i < 128; i++) {
 Send[i] = Daten;

o.ä.
Gruß Marcus

Autor: Torben (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo,
erstmal danke für die antwort.
also die berechnung mit dreisatz ist klar. aber wie mache ich das den
mit der feststellung der fehlerhaften Blöcke, kann mir das nicht
vorstellen, wenn ich z.b. ein code habe:
100 und 011 dann ist die distanz 3 und jetzt?

wie mache ich das jetzt bei einem langen code z.b. von 1024bit???
oder werfe ich da ständig was durcheinander?

mit deinem code würde ich immer blöcke von 1 byte übertragen, ist das
richtig?

mfg
Torben

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Torben,

das mit den Hamming-Distanzen solltest Du mal vorläufig außer Acht
lassen. Das habe ich erwähnt, weil es halt zu den Grundlagen dieser
ganzen Thematik gehört, aber Du brauchst das nicht wirklich um eine
Übertragung mit einer CRC abzusichern.

Nimm einfach einen fertigen Sourcecode (davon gibts dutzende im Netz)
und benutzte den. Das ist für den Anfang am einfachsten.

Markus

Autor: stephan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hi

habe gerade eine crc8 berechnung vor mir : DOW-CRC

generatorpolynom ist wie folgt : X^8+X^5+X^4+X^0

und hex wert dieses polynoms = 0x18

nun frage ich micht, wie man auf den wert 0x18 kommt ???

denn 0x18 = 0001 1000 = x^4 + x^3

vielleicht weiss jemand rat



danke

Autor: Andreas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

weil bei einer 8 bit CRC x^8 und x^0 immer gesetzt sein müssen damit das 
Polynom Sinn ergibt.
x^8 gibt in diesem Fall den Grad des Polynoms an (=8) und x^0 brauchst 
Du damit überhaupt Daten in das Schieberegister geschoben werden können.

Autor: stephan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hm

verstehe ich leider nicht so ganz:

>>> weil bei einer 8 bit CRC x^8 und x^0 immer gesetzt sein müssen damit das
Polynom Sinn ergibt.

wo erkenne ich dass x^8 und x^0 immer gesetzt sind ???

>>> x^0 brauchst Du damit überhaupt Daten in das Schieberegister geschoben werden 
können.

wie hängt x^0 mit der aussage "damit überhaupt Daten in das 
Schieberegister geschoben werden können" zusammen

auch wenn x^8 und x^0 wegfallen, 0x18 = 0001 1000 ist immer noch  x^4 + 
x^3


sorry für mein missverständnis

Autor: Schlumpf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi zusammen!

Wenn´s um die Umsetzunge eines CRC-Generators (Checkers) in VHDL geht:

Es gibt ein Tool mit dem man sich den VHDL-Code für einen CRC-Generator 
(x Bit breit und beliebiges Generatorpolynom) erzeugen lassen kann.

http://www.easics.be/webtools/crctool

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.