CRC8 über Datenstrom mit ungerader Länge

Die CRC wird grundsätzlich bitweise berechnet. Die Ausgabe ist 
üblicherweise ein 8,16,32bit-Wert, aber die Eingabe ein Bitstrom. Die 
meisten Algorithmen werden aber darauf ausgelegt sein ganze Bytes zu 
verwenden.

Man kann die CRC selbstverständlich auch bitweise berechnen, dann spart 
man sich sogar die Lookup-Tabelle. Ist allerdings langsamer.

Nop schrieb:
> Ist allerdings langsamer.

Auf uC. In Bitströmen (Schieberegistern) sind es nur ein paar Gatter, 
und sie bitzahl ist egal.

M. D. schrieb:

> wie kann eine CRC8-Prüfsumme über einen Datenstrom, dessen Länge kein
> Vielfaches von 8 ist, berechnet werden?
> Z.B. wenn der Datenstrom 10 Bit lang ist. Muss dieser dann mit irgedn
> etwas aufgefüllt werden um auf 16 Bit zu kommen?

Nein. Eine CRC ist eigentlich immer "bitwise". Nur aus 
Performancegründen wird sie jenseits der Hardware-Hölle vielfach in 
größeren Einheiten berechnet. Wenn der eigene Bitstream nicht in's 
Raster der verwendeten Routine passt, muss man einfach die 
"leftover"-Bits ganz klassisch dazu rechnen, eben "bitwise".

Auffüllen auf die nächstgrößere Unit der raubkopierten CRC-Routine 
funktioniert nicht (naja: in sehr seltenen Ausnahmefällen halt doch...), 
ganz egal, was du auffüllst!

c-hater schrieb:
> Auffüllen auf die nächstgrößere Unit der raubkopierten CRC-Routine
> funktioniert nicht

Und warum nicht? Man definiert sich sein Datenpaket halt so, dass es 
nicht z.B. 43 sondern 48 Bits lang ist und die letzten 5 Bits immer 
etwas fixes sind, z.B. 0x15. Beim Prüfen muss man diese Bits natürlich 
nach dem Empfang auf den bekannten Wert setzen.

Manche Mikrocontroller wie die STM32 haben auch eine Hardware-Einheit 
zur schnellen CRC-Berechnung, diese z.B. kann nur ganze 32bit-Words auf 
einmal verwursten. Da bleibt einem gar nichts anders übrig, als die 
übrig bleibenden Bits mit Dummy-Werten aufzufüllen.

Mit 0en aufzufüllen ist einfach, aber nicht unbedingt optimal:
https://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung#Nullproblem_und_Nachbearbeitung

Dr. Sommer schrieb:

> Und warum nicht?

Weil's halt nicht geht. Weil es der Sinn einer CRC ist, dass auch die 
Position/Anzahl der Bits im Datenstrom eine Rolle spielt.

> Man definiert sich sein Datenpaket halt so, dass es
> nicht z.B. 43 sondern 48 Bits lang ist

Ja, das kann man natürlich machen, wenn man die Bitlänge des Datenstroms 
selber bestimmen kann. Wenn diese aber vorgegeben ist, dann geht das 
eben nicht.

Übrigens: Selbst wenn man den Datenstrom selber kontrolliert, ist es 
auch nicht gerade schön, die eventuell knappe Kanalbandbreite mit 
Padding zu verschwenden, nur weil man zu doof ist, ein paar verschissene 
CRC-Bits von Hand zu berechnen.
Mal ganz davon abgesehen, dass das unnütze Padding die 
Wahrscheinlichkeit für eine korrekte Übertragung negativ beeinflusst. 
Denn auch im (völlig unformationslosen) gepaddeten Teil des Datenstroms 
können Störungen auftreten. Und es wäre doch wirklich blöd, ein Paket 
verwerfen zu müssen, nur weil es an einer Stelle gestört wurde, an der 
es überhaupt keine Nutzinformation übertragen hat. Da sträuben sich die 
Nackenhaare jedes Informatikers und jedes gelernten Programmierers...

Du bist wohl weder das eine noch das andere...

c-hater schrieb:
> Du bist wohl weder das eine noch das andere...

Warum gleich so aggressiv?
1. Bin ich M.Sc. Informatik.
2. Habe ich schon diverse CRC-Algorithmen selbst programmiert, auch mit 
mehrstufiger Look-Up-Table.
3. Weiß ich daher dass z.B. dank dieser LUT, oder dank des genannten 
Hardware CRC Beschleunigers, das Berechnen des gepaddeten Werts sogar 
schneller sein kann als das Verarbeiten einzelner Bits.
4. Hat niemand gesagt, dass man die (z.B. 5) zusätzlichen Padding Bits 
mit übertragen muss. Die steckt man nur mit in die CRC Routine. Auf der 
Leitung sind es weiterhin nur 43.

Wenn du schon bei einem derart emotionslosen Thema wie CRCs so verbal 
entgleist, wie reagierst du dann in richtigen Konflikt-Situationen? 
Hattest du keine gute Kinderstube? Wirfst du auch beim Kauf eines 
Brötchens mit Schimpfworten um dich?

Dr. Sommer schrieb:

> 3. Weiß ich daher dass z.B. dank dieser LUT, oder dank des genannten
> Hardware CRC Beschleunigers, das Berechnen des gepaddeten Werts sogar
> schneller sein kann als das Verarbeiten einzelner Bits.
> 4. Hat niemand gesagt, dass man die (z.B. 5) zusätzlichen Padding Bits
> mit übertragen muss. Die steckt man nur mit in die CRC Routine. Auf der
> Leitung sind es weiterhin nur 43.

Jetzt verstehe ich, was du gemeint hast. Wenn Sender und Empfänger sich 
einig sind, dass es da noch ein paar Überhangbits gibt und ein 
bestimmter Zustand dieser Bits als vereinbart gilt, dann geht das. 
Allerdings schwächt es immer noch die Übertragungssicherheit. Nur nicht 
mehr durch die Möglichkeit von Kanalfehlern fürs Padding, sondern nur 
noch durch die von Kanalfehlern für die übertragene CRC. Schönes 
Extrembeispiel zum Durchrechnen für einen gelernten Informatiker: 1 Bit 
Nutzdaten, 32 Bit CRC...
Reale Anwendungfälle wären natürlich weit weniger dramatisch, aber 
wegzudiskutieren ist der Nachteil nicht. Oder siehst du das anders?

Im beiden Fällen werden 33 Bits übertragen. Die Wahrscheinlichkeit von 
Übertragungs-Fehlern ist in beiden Fällen gleich, nämlich 1-(1-p)^33.

c-hater schrieb:
> für einen gelernten Informatiker
Ah, eine Übungsaufgabe vom Schulmeister. Wie lehrreich.

Da der TO nichts zum Einsatzfall schreibt, hat jeder recht. Wenn er 
beide Seiten beeinflussen kann kann er machen, was er will. Auch 1en 
anfügen oder die letzten Bits verodern.

Wenn eine Gegenstelle fix ist und wirklich beliebige bitmengen 
schickt/erwartet, dann bleibt nur die Beschäftigung mit dem bitweisen 
Algorithmen, zumindest für die letzten Bits.