Forum: Mikrocontroller und Digitale Elektronik CRC-8: Startwertproblem


von A. B. (alfa)


Lesenswert?

Hallo CRC-Spezialisten!
Ich, als eine Anfängerin auf diesem Gebiet, brauche schon wieder Eure 
Hilfe.
Es geht  um CRC-8 mit dem Generator-Polynom:  x^8+x^4+x^3+x^2+x+1.
Meine Frage ist: wie hoch ist die Wahrscheinlichkeit, dass ein Fehler 
bei der Datenübertragung nicht erkannt wird, wenn man als Startwert 
nicht konstant immer den Wert 0x00 oder den Wert  0xFF nimmt, sondern 
durch den Zufallsgenerator einen Startwert ermittelt und entsprechend 
für jede CRC-Berechnung einen Wert von den 256 Möglichkeiten nimmt? Hat 
die Auswahl von Startwerten überhaupt irgend ein Einfluß darauf, dass 
ein Fehler bei der Übertragung nicht erkannt wird?
Kann man es irgendwie zeigen oder die Wahrscheinlichkeit  für die 
einzelne Startwerte  ausrechnen? Oder läßt sich das nur durch das Testen 
und Simulieren bestimmen (was für mich nicht erwünscht ist!!!)?

Besten Dank im Voraus!!!

von Falk B. (falk)


Lesenswert?

@A. B. (alfa)

>durch den Zufallsgenerator einen Startwert ermittelt und entsprechend
>für jede CRC-Berechnung einen Wert von den 256 Möglichkeiten nimmt? Hat

Ein Zufallswert als Startwert ist nciht sinnvoll, denn den müsste man ja 
zusätzlich übertragen, damit der Empfänger ihn zur CRC Prüfung nutzen 
kann.
Praktisch wird man oft 0xFF wählen, damit der CRC "Mischjvorgang" sofort 
startet. Das kann nämlich bei 0x00 und 00x00 am Anfang des Datenblocks 
nicht starten, und somit wird die CRC "schwächer".

Siehe auch die Links im Artikel CRC

MFG
Falk

von A. B. (alfa)


Lesenswert?

Danke!
Weisst du vielleicht,wie ich über andere Startwerte wie zum Beispiel 
0x1F oder 0x9A eine Aussage machen kann? Lässt sich das irgendwie 
beweisen?

von Falk B. (falk)


Lesenswert?

@ A. B. (alfa)

>0x1F oder 0x9A eine Aussage machen kann? Lässt sich das irgendwie
>beweisen?

Möglichwerweise, wenn man RICHTIG fit in Mathe ist. Ich bins nicht ;-)

MFG
Falk

von Freizeitbastler (Gast)


Lesenswert?

Der Startwert ist ziemlich egal. Bereits nachdem das erste Byte in die 
CRC-Summe eingegangen ist, können in der Zwischensumme 256 möglichen 
Werte drinstehen.

von Freizeitbastler (Gast)


Lesenswert?

Der Startwert ist ziemlich egal. Bereits nachdem das erste Byte in die
CRC-Summe eingegangen ist, können in der Zwischensumme alle 256 
möglichen
Werte drinstehen.

von Freizeitbastler (Gast)


Lesenswert?

Begründung: Die CRC ist als Polynomdivision definiert und damit linear.

von Falk B. (falk)


Lesenswert?

@Freizeitbastler (Gast)

>Der Startwert ist ziemlich egal.

Falsch. Siehe

http://www.employees.org/~surendra/asic/crc.html

Wenn am Anfang alles Nullen sind, wir die CRC-Vermischung nicht 
angestossen. Deshalb 0xFF.

MfG
Falk

von Freizeitbastler (Gast)


Lesenswert?

@Falk

Ein schöner Text. Das Argument darin ist folgendes: Theoretisch (das 
heißt bei gleichverteilten Nutzdaten) ist der Startwert egal. Das war 
auch, was ich meinte. Praktisch hat man oft den Fall,  dass die Zeichen 
in den Nutzdaten nicht gleichverteilt sind. Man hat z. B. 
überproportional viele Nullen. Es lohnt sich in diesem Fall, den 
Startwert auf die Nutzzeichenverteilung anzupassen. 0xFF ist für 
überproportional häufige Nullen ein besserer Startwert als 0.

Den optimalen Startwert könnte man bei bekannter Nutzdatenverteilung 
ausrechnen, wenn man auch für die Fehler ein mathematisches Modell 
bereitstellt. Einfacher ist ein Monte Carlo Algorithmus, der soweit 
möglich realistische Nutzdaten mit den erwarteten Fehlern stört für alle 
Startwerte durchlaufen zu lassen. Mein Tip ist, dass auch 0xff in den 
meisten Fällen ein suboptimaler (obgleich besser als 0) Startwert ist.

Schöne Grüße, Peter

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.