Schnelles, kurz zu implementierendes Prüfsummenverfahren gesucht.

Es muss sehr schnell sein und darf keine Hilfstabellen brauchen, da es für einen uC ist. Sowas tolles wie MD5 u.a. kommt also nicht in Frage ;-).

Korbinian

CRC? Oder simple Pruefbits (1 oder 2 dimensional)

junix

Sehr beliebt sind auch "Bitweise invertieren dann Addieren"-Verfahren bei uC... Dabei wird jedes Byte des Speicherbereichs invertiert und dann die Summe darüber gebildet...

Jester

Warum invertiert man da noch?

net 0

Molocko_ schrieb:

Es muss sehr schnell sein und darf keine Hilfstabellen brauchen, da es für einen uC ist. Sowas tolles wie MD5 u.a. kommt also nicht in Frage ;-).

z.b. sowas:

#define GOODFCS 0xf0b8
#define INITFCS 0xffff

static UINT16 crc_tab[16] =
{
  0x0000, 0x1081, 0x2102, 0x3183,
  0x4204, 0x5285, 0x6306, 0x7387,
  0x8408, 0x9489, 0xA50A, 0xB58B,
  0xC60C, 0xD68D, 0xE70E, 0xF78F
};

/* CRC16 implementation acording to CCITT standards */
UINT16 crc_update (UINT16 crc, UINT8 c)
{
    crc = (((crc >> 4) & 0x0FFF) ^ crc_tab[((crc ^ c) & 0x000F)]);
    crc = (((crc >> 4) & 0x0FFF) ^ crc_tab[((crc ^ (c>>4)) & 0x000F)]);
    return crc;
}

die 32 bytes für die tabelle bekommste in die kleinste mcu rein. der code ist ja auch recht wenig...

Prof84

Molocko_ schrieb:

Es muss sehr schnell sein und darf keine Hilfstabellen brauchen, da es für einen uC ist. Sowas tolles wie MD5 u.a. kommt also nicht in Frage ;-).

Was spricht gegen chksum? Einfach die Summe bilden?!
Ist < O(n/2^8) ...

Ja, so habe ich es nun gemacht.

Danke an alle!

lst < O(n/2^8)

was soll das bedeuten, kann mir das einer erklaeren?

Jester

Das wird Dir wohl niemand erklären können, weil es nämlich falsch ist.
Das Verfahren läuft in O(n), nicht schneller. Wenn Dir das nichts sagt, schau mal bei wikipedia nach O-Kalkül.

Gegen die einfache Summe spricht, unter Umständen die Anwendung. Wenn es dabei um Kommunikation geht, dann ist das nicht so toll, weil sich Fehler lokal wieder wegheben können. Bei CRC hat man Garantien, das wenn eine gewisse höchstmenge aufeinanderfolgender Bits gestört sind die Checksumme auf jeden Fall falsch ist.

Prof84

@Jester:
Joh, Faktoren sind nicht statthaft in der Klassifikation!
Punkt für dich.

Hier eine schönere Kladde:
http://www.physik.fu-berlin.de/~goerz/studies/semester01/comp_sci2/inf_skript.pdf

Das heißt chksum, weil die Summe gecheckt wird.
Das reduziert nur die Wahrscheinlichkeit von Fehlern auf ein Minimum,
schließt Sie aber nicht aus.

1:1 !