mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hilfe mit CRC-8


Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Zusammen!

Ich brauche dringend Hilfe!!!! Es geht um CRC-8.
Es gibt ein Generatorpolynom vom Grad 8 : 0x8E=x^8+x^4+x^3+x^2+1, der 
für eine 56 Bit Message (7 Bytes Daten ) verwendet wird.
Die  Frage ist, ob dieses Generatorpolynom  für 120 Bit Message (d.h 15 
Bytes Daten, der 16. Byte ist für CRC reserviert) gut oder schlecht ist 
.
Hat jemand eine Idee, wie man es beweisen oder zeigen kann?

Danke im Voraus!!!

Autor: eProfi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also, alle Angaben ohne Gewähr:
Es gibt Generatorpolynome, die funktionieren, und andere, die 
funktionieren nicht.

Wieviele Bits Du damit zusammenfasst, ist nebensächlich. Das hat eher 
mit der Wahrscheinlichkeit zu tun, mit der ein Übertragungsfehler 
erkannt wird.

120 Bits mit CRC8 ist ein absolut übliches Verfahren, wenn auch nicht 
absolut sicher.

Autor: Max (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du kannst mit CRC8 zumindest einen oder mehrere Fehler im Bereich von 7 
Bits erkennen.  (Burstfehler)

Gruß Max

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit ein wenig Suchen findet man
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Demnach wurde diese Polynom schon von ernstzunehmenden Leuten benutzt
(SAE J1850 ist ein veralteter Standard zur Kommunikation in Fahrzeugen).

Irreduzibel ist es auch.

Was ist denn der Hintergrund der Frage?

Jürgen

Autor: 3359 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein 8 bit CRC ist gut fuer 2^8 = 256 bit = 32 bytes

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ein 8 bit CRC ist gut fuer 2^8 = 256 bit = 32 bytes

Halte ich für Blödsinn.

Jürgen

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Hat jemand eine Idee, wie man es beweisen oder zeigen kann?

Ohne mathematische Vertiefung sollte dieser Praktiker-Ansatz helfen:

www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

-Hans

Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jürgen wrote:
> Mit ein wenig Suchen findet man
> http://en.wikipedia.org/wiki/Cyclic_redundancy_check
> Demnach wurde diese Polynom schon von ernstzunehmenden Leuten benutzt
> (SAE J1850 ist ein veralteter Standard zur Kommunikation in Fahrzeugen).
>
> Irreduzibel ist es auch.
>
> Was ist denn der Hintergrund der Frage?
>
> Jürgen

Erstmal Danke!
Jetzt zum Hintergrund:
Es geht um die Datenübertragung zwischen zwei Steuergeräten im Fahrzeug.
Da es immer mehr Information übetragen wird, reichen dafür die 7 Bytes 
nicht mehr aus und es wird um weitere Bytes erweitert. Dabei hat man das 
bedenken, dass bei der Übertragung von 15 Byte langen Botschaften mit 
CRC8 die Fehler nicht erkannt werden können. Deswegen muss es bewiesen 
werden.
Kennst du dich in diesem Thema aus? Für mich ist es ganz was neues:-( 
Habe kein Plan

Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hans Hein wrote:
>> Hat jemand eine Idee, wie man es beweisen oder zeigen kann?
>
> Ohne mathematische Vertiefung sollte dieser Praktiker-Ansatz helfen:
>
> www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
>
> -Hans

Danke für Hinweis!
Weisst du , wie man es mathematisch mit Formeln beweisen könnte?
Es wäre dann der sichere Weg für mich
Welche Rolle spielt dabei die Hamming-Distanz? Damit kann man doch nur 
die Fehler korrigieren aber nicht erkennen?

Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
eProfi wrote:
> Also, alle Angaben ohne Gewähr:
> Es gibt Generatorpolynome, die funktionieren, und andere, die
> funktionieren nicht.
>
> Wieviele Bits Du damit zusammenfasst, ist nebensächlich. Das hat eher
> mit der Wahrscheinlichkeit zu tun, mit der ein Übertragungsfehler
> erkannt wird.
>
> 120 Bits mit CRC8 ist ein absolut übliches Verfahren, wenn auch nicht
> absolut sicher.

Genau darum geht es, zu zeigen wie hoch ist die wahrscheinlichkeit, dass 
bei 15 Bytes langen Botschaften mit CRC8 die Fehler nicht erkannt werden

Autor: Dieter Werner (dds5)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Damit kann man doch nur die Fehler korrigieren aber nicht erkennen?

Hier scheint ein Verständnisproblem vorzuliegen, wie soll man Fehler 
korrigieren wenn sie nicht erkannt werden?

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Laut obigem Link gilt: "CRC polynomials detect (single) burst errors 
shorter than the number of the position of the highest polynomial 
coefficient."

Wenn also strikt bewiesen werden muss, dass die CRC alle Fehler erkennt 
(so die Formulierung des OP), dann muss die CRC länger als die gesamte 
Message sein. Da das bei einer CRC8 und 7 Bytes auch schon nicht der 
Fall ist, ändert sich mit 15 Bytes nur die Erkennungswahrscheinlichkeit.

Autor: Hans Hein (hanshein)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Genau darum geht es, zu zeigen wie hoch ist die wahrscheinlichkeit, dass
>bei 15 Bytes langen Botschaften mit CRC8 die Fehler nicht erkannt werden

mein "Jungnickel", Codierungstheorie (Spektrum Verlag) ist leider im 
Buero,
aber es gilt (modulo Erinnerung)....

E::=Wahrscheinlichkeit

-Generatorpolynom g(x) vom Grad r mit g(0)=1
-ein(!) Fehlerbuendel der Laenge b (gleichverteilt) ("Fehlermodell")

* fuer b=r+1 ist die E(Fehler werden nicht erkannt) = 2^-r+1
* fuer b>=r+2 ist die E(Fehler werden nicht erkannt) = 2^-r

Diese Aussage auf jeden Fall mit einem "Codierungstheorie" Buch
nachverifizieren, davon sind genuegend Klassiker in der
Referenzenliste des obigen Links zu sehen.

-Hans

PS: Das Fehlermodell kann/wird im Automobilsektor anders sein.
PPS:
>Wenn also strikt bewiesen werden muss, dass die CRC alle Fehler erkennt
>(so die Formulierung des OP), dann muss die CRC länger als die gesamte
>Message sein.

Nope, die HD des CRCs muss > der Laenge der Message sein, aber dann
ist man in Bereichen, in denen fehlerkorrigierende Codes vorzuziehen
sein (Stichwort z.B. Reed Solomon)

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]
  • [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.