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!!!
Gast
#937380
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.
Gast
#937453
Du kannst mit CRC8 zumindest einen oder mehrere Fehler im Bereich von 7 Bits erkennen. (Burstfehler) Gruß Max
Gast
#937483
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
Gast
#937489
Ein 8 bit CRC ist gut fuer 2^8 = 256 bit = 32 bytes
Gast
#937527
> Ein 8 bit CRC ist gut fuer 2^8 = 256 bit = 32 bytes
Halte ich für Blödsinn.
Jürgen
> 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
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
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?
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
> 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?
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.
>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)