www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC-8: Startwertproblem


Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht 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!!!

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: A. B. (alfa)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Freizeitbastler (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Freizeitbastler (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Freizeitbastler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Begründung: Die CRC ist als Polynomdivision definiert und damit linear.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Freizeitbastler (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

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.