wie lang muss eine CRC sein? [Archiv]

Archiv verlassen und diese Seite im Standarddesign anzeigen : wie lang muss eine CRC sein?

anorakker

2006-09-06, 10:31:50

hi,

ich bastel gerade an einer Funkübertragungsstrecke und möchte zum sicherstellen der Datenintegrität den Nutzdaten eine CRC anhängen.
Jetzt frage ich mich aber, wie lang bzw. wieviel Koeffizienten eine CRC haben muss, um z.b. 16 oder 24 bit möglichst gut als "richtig" verifizieren zu können.
Da das ganze auf einem kleinen Mikrocontroller läuft (Mega48/88), kann der CRC Algorithmus nicht allzu kompliziert sein, eine Fehlerkorrektur ist in anbetracht der begrenzten Ressourcen wohl auch nicht möglich.
Ich möchte also nur feststellen, ob die Daten, die übertragen wurden, korrekt sind, Bitfehler müssen sehr sicher erkannt werden.

Ich habe atm noch nicht so wirklich herausgefunden, eine wie grosse CRC (CRC-8,CRC-16,CRC-32 usw.) ich z.b. für mein "kleines" 24bit Datenpaket benötige, insgesamt soll die übertragene Framelänge nämlich so kurz wie möglich sein.

Bei Wiki steht zwar ne Menge, mir fehlt aber im Moment noch eine "Hausnummer" in der Richtung : eine 8bit CRC bietet mir auf 24bit Daten eine eine xx,x% Sicherheit für erkannte Fehler, 16Bit xx,x% usw.

Kann mir jemand da weiterhelfen, oder hat noch ein paar nützliche Links ?

/dev/NULL

2006-09-06, 10:50:51

http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check

Steht alles da: Welche Fehler er erkennt usw.

anorakker

2006-09-06, 12:53:56

nunja, die Wiki ist natürlich immer die erste Anlaufstelle, hab das auch schon(vorher) gemacht, trotzdem steht da nicht wirklich, welches CRC Polynom für mich am geeignetsten wäre. Insbesondere scheint die übliche CRC keine 2Bit Fehler erkennen zu können, und das könnte bei meinen kleinen Datenframes schneller passieren als mir lieb ist :(

TheFallenAngel@Gast

2006-09-06, 14:50:09

hiho!

Nur 24Bit für ein Nachrichtenpaket erscheint mir doch sehr wenig - hast du schon mal überlegt die Pakete zu vergrößern und sie dann mittels MAC bzw. HMAC vernünftig zu authentifizieren? ich würde dir HMAC mittels SHA-256 empfehlen.... beide Verfahren eigenen sich übrigens auch für den mobilen Einsatz, da sie sehr flink und doch hardwareschonen sind...

cya

anorakker

2006-09-06, 16:29:59

Das Datenpaket enthält nur Status- und Identifizierungs Daten, die sich in der Anwendung nur wenig ändern, ähnlich einem "i´m alive" Signal, die 24Bit sind somit die komplette Information.
Wichtig ist, dass die Info fehlerlos übertragen wird (bei gemächlichen 4,8 oder 9,6 kbits), es darf zu keiner "Fehldeutung" kommen, jedes Paket für sich ( diese werden repetiv in kürzen ms Abständen gesendet und empfangen) könnte entscheidend sein.

TheFallenAngel

2006-09-06, 17:51:28

hiho!

wenn Hashfunktionen, aufgrund deren Komplexität nicht in Frage kommen, würde ich ebenfalls auf einen CRC zurückgreifen...

für deine Paketgröße sollte jedoch CRC-8 ausreichend sein (dieser wird beispielsweise auch bei der IrDA eingesetzt http://www.dch-faq.de/kap05.html )

cya

TheFallenAngel

2006-09-06, 18:14:27

hiho!

habe noch etwas interressantes für dich:

"Prüfverfahren: CRC-8, CRC-16, ....

Die Prüfverfahren schützen in allen Fällen, in den die Anzahl der Bitfehler
kleiner ist als die Anzahl der Prüfbits. Darüber hinaus werden die meisten
anderen Fehler erkannt."

Quelle: http://www.fh-friedberg.de/users/u10705/referenzen/netzwerke/RN-Skript.pdf#search=%22fehlererkennung%20crc8%22

wenn es also bei deiner Übertragung durchaus möglich ist, dass mehr als 8 Bitfehler auftreten, dann wäre ein besserer CRC von nöten.....

wenn ich die oben zitierte Quelle richtig verstanden habe hast du, in deinem fall, nur mit einem CRC-24 totale 100%-ige Sicherheit.....

natürlich stellt sich nun die frage der wahrscheinlichkeit, dass mehr als 8 Bitfehler auftreten.... ich glaube jedoch, dass dies bei einem 24Bit Paket nahezu unmöglich ist (ist aber natürlich von der "Qualität" der Verbindung abhängig)

cya

anorakker

2006-09-06, 21:22:12

TheFallenAngel

2006-09-06, 21:39:30

danke schonmal :)

ich werde die wichtigsten Informationen (boolesche Bedingungen) wahrscheinlich auch noch kodiert (also auf mehrere bits) in den Daten verteilen, um die Sicherheit für die wichtigsten Informationen noch zu erhöhen, denn eine Falschmeldung muss ich unbedingt ausschliessen.
Ein verlorenes, zu kurzes oder fehlerhaftes Paket ist nicht so schlimm.

np :)

dache ich mir, deshalb habe ich den Vorschlag mit den Hashfunktionen gemacht - die sind im Allgemeinen sehr empfindlich d.h. wenn auch nur 1 Bit gekippt ist sieht der dadurch resultierende Hashwert total anders aus und bei ausreichender Länge sind sie kollisionsfrei. Wenn du aber nur begrentze Hardware-Ressourcen hast (kenne den Mega48/88 nicht), ist ein CRC sicher empfehlenswerter da nicht so komplex...

aber wie schon gesagt (ich weiß zwar nicht welch ein system du wofür baust), wir wollen ja nicht mit Kanonen auf Spatzen schiessen ;)

Ansonsten ist es natürlich immer empfehlenswert die empfangenen Daten selbst noch mal zu verifizieren....

cya

Gast

2006-09-06, 22:06:16

Evtl. wäre auch eine FEC (z.B. ein Reed-Solomon-Code) sinnvoll. Hängt von der Zuverlässigkeit des Übertragungsmediums ab.

Tyson

2006-09-06, 22:13:22

TheFallenAngel

2006-09-06, 22:32:05

Du kannst auch zusätzlich alles 2x Senden und vergleichen und zusätzlich CRC einsetzen.

das würde aber die bandbreite halbieren und da stehen ohnehin nur 4,8 bis 9,6 kbits zur verfügung...

anorakker

2006-09-07, 00:32:41

Du kannst auch zusätzlich alles 2x Senden und vergleichen und zusätzlich CRC einsetzen. Reed Solomon ist zwar ne gute Idee, aber das ist ein 8-Bit Mikrokontroller mit mit max. 20 MHz und ich weiß zwar nicht was da sonst noch so auf dem läuft, aber das könnte doch dauern.

Such doch mal hier:
http://www.mikrocontroller.net/forum/list-1-1.html

Vielleicht hast du Glück und jmd. stand schonmal vor dem Problem und hat auch schon ne passende Library programmiert und online gestellt.

Gruß Tyson

das geht so leider nicht, weil es eine Art "Echtzeit-Alarmsystem" werden soll, d.h. es geht nicht um viele Daten, sondern dass ich möglichst schnell und sicher auf Sensordaten reagieren kann. Nun kann man sich gut vorstellen, dass man nicht einen Alarm auslösen möchte, wenn eigentlich alles ok ist, aber ebenso der Alarmfallstatus korrekt gemeldet wird.

Ich denke schon, dass es fertige libs für einfache CRC Berechnungen geben wird, wichtig ist mir halt der theoretische background, also z.b. können 2Bit Fehler bei einer einfachen CRC durchrutschen usw.

ethrandil

2006-09-07, 00:53:46

Also ich würde rein intuitiv vorschlagen, dass Alarmmeldungen durch ein zweites Datenpaket überprüft werden, um Fehlalarme zu verhindern.
Die leicht erhöhte Latenzzeit sollte vernachlässigbar klein sein...

CRC sollte natürlich zusätzlich sein. Aber was machst du, wenn plötzlich alle CRC-Prüfungen fehlschlagen (zB durch Störsender)? ;-)

mfg
- eth

anorakker

2006-09-07, 11:23:58

Es wird eine Art "Totzeit" geben, d.h. falls innerhalb einer gewissen Zeit nicht ein "alles in Ordnung" Signal gesendet werden kann (weswegen auch immer), wird dies auf jeden Fall als ein Fehler bewertet.
Mir ist es halt ganz wichtig, dass ein vom Sender verschicktes Paket mit einer Fehlermeldung, im Empfänger nicht fehlinterpretiert wird (werden kann), falls also z.b. die CRC die Daten als korrekt kennzeichnet obwohl ich einen Bitdreher drin habe.

Gast

2008-02-05, 15:52:23

Ich würde gern ein struct mit einem crc versehen

#define POLY16 0x8005
struct
{
float f1;
float f2;
unsigned short crc;
} crcfoo;

Ich fülle das Struct mit Daten und belege das CRC zuerst nach 0. Wie bekomme ich das struct nun sinnvoll durch das Polynom dividiert/xor'd? Muß ich das dazu in ein unsigned short array casten oder wie laufe ich durch die Daten? Brauche ich dazu vielfache von 16bit?

Gast

2008-02-06, 11:21:15

Man soll den CRC auch mit einer vorberechneten Tabelle zu einem Polynom schneller berechnen können. Wenn ich das richtig verstanden habe, wird nicht mehr für jedes Bit die Operation ausgeführt sondern ein CRC für jedes Byte vorberechnet.

Was ich nicht so ganz verstehe, wie man mit dieser Tabelle dann zu rechnen hat. Das heißt wie bekomme ich aus meinen z.B. 10 Byte Eingabedaten-Array und einer solchen Tabelle den CRC für die Gesamtdaten? Einfach die Tabellenwerte der einzelnen Bytes xor'n ist es wohl noch nicht, oder?

Gast

2008-02-07, 08:27:37

Ich berechne so die Tabelle für jedes Byte und gehe dann durch den Datenstrom Byte für Byte durch. Ich bekomme da auch immer einen schönen Wert raus, der sich auch immer ändern, wenn ich was kleines verändere, der auch 0 ist, wenn das ganze Objekt =0 ist; aber wenn ich diesen CRC in das obige struct crcfoo schreibe und dann nochmal durchlaufen lasse, kommt bei diesem nicht null raus - was doch zumindest eigentlich der Sinn wäre.

Was läuft da falsch?

Wäre klasse wenn irgendwer eine Idee hätte?

//tabelle
UINT16 c;
for(UINT16 i=0; i<256; ++i )
{
c = i;
for(UINT16 j=0; j<8; ++j)
{
if( c & 1)
{
c = (c>>1) ^ CRC16_POLYNOM;
}
else
{
c = c>>1;
}
}
table[i] = c;
}
//calc
UINT16 calc( UINT8* buffer, int length )
{
UINT16 crc = 0;
for( size_t i = 0; i<length; ++i)
{
crc ^= buffer[i];
crc = (crc>>8) ^ table[crc & 0xff];
};
return crc;
};

Gast

2008-02-08, 07:55:32

Weiß da niemand was zu? :(

Xmas

2008-02-08, 11:44:36

Das heißt wie bekomme ich aus meinen z.B. 10 Byte Eingabedaten-Array[...]
Ich sehe nur 2 floats, also 8 Byte. Der CRC-Wert kann schließlich nicht zur Berechnung von sich selbst herangezogen werden.

Gast

2008-02-08, 11:50:31

Danke. Aber ich dachte der CRC wird beim Start mit 0 vorgegeben und für die Berechnung an die Daten angehängt. Wenn der CRC berechnet ist, wird dann dieser Wert wieder an die Daten angehängt und gespeichert. Beim Überprüfen der Daten mit dem CRC müßten wenn kein Fehler drin ist, der CRC 0 rauskommen, d.h. kein Fehler.

Oder habe ich das falsch verstanden? So steht es zumindest in einigen Dokumenten im Netz.