it-swarm-eu.dev

Was ist eine schnellere Alternative zu einem CRC?

Ich mache eine Datenübertragung von einem dsPIC zu einem PC und mache eine 8-Bit-CRC zu jedem Block von 512 Bytes, um sicherzustellen, dass es keine Fehler gibt. Wenn mein CRC-Code aktiviert ist, erhalte ich ungefähr 33 KB/s, ohne ihn erhalte ich 67 KB/s.

Welche alternativen Fehlererkennungsalgorithmen sind schneller zu überprüfen?

27
FigBug

Es gibt zwar möglicherweise schnellere Optionen als CRC, aber wenn Sie sie verwenden, werden Sie wahrscheinlich ein gewisses Maß an Fehlererkennungsfähigkeit verlieren. Abhängig von Ihren Anforderungen an die Fehlererkennung kann eine Alternative darin bestehen, stattdessen CRC-Code zu verwenden, der für Ihre Anwendung optimiert ist.

Einen Vergleich von CRC mit anderen Optionen finden Sie in der Antwort ausgezeichnet von Martin Thompson .

Eine Option, um dabei zu helfen, ist pycrc, ein Tool (in Python geschrieben)1) die C Quellcode für Dutzende von Kombinationen von crc Modell und Algorithmus erzeugen kann. Auf diese Weise können Sie Geschwindigkeit und Größe für Ihre eigene Anwendung optimieren, indem Sie verschiedene Kombinationen auswählen und vergleichen. 1: Benötigt Python 2.6 oder höher.

Es unterstützt das crc-8 Modell, unterstützt aber auch crc-5, crc-16 und crc-32 unter anderem. Algorithmen unterstützt bit-by-bit, bit-by-bit-fast und table-driven.

Zum Beispiel (Herunterladen des Archivs):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Mit der 256-Byte-Nachschlagetabelle können Sie sogar funky Dinge wie das Festlegen mithilfe von Dual-Nibble-Lookups (mit einer 16-Byte-Nachschlagetabelle) anstelle einer Einzelbyte-Nachschlagetabelle ausführen.

Zum Beispiel (Klonen des Git-Repositorys):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

In Anbetracht Ihrer Speicher- und Geschwindigkeitsbeschränkungen ist diese Option möglicherweise der beste Kompromiss zwischen Geschwindigkeit und Codegröße. Der einzige Weg, um sicher zu sein, wäre ein Benchmarking.


Das pycrc git-Repository befindet sich auf github , ebenso wie sein Issue-Tracker , kann es aber auch heruntergeladen werden von sourceforge .

41
Mark Booth

Ein wirklich gutes Papier, das die Leistung verschiedener Prüfsummen und CRCs in einem eingebetteten Kontext vergleicht:

Die Wirksamkeit von Prüfsummen für eingebettete Netzwerke

Einige Zitate aus den Schlussfolgerungen (basierend auf ihren Studien zu unentdeckten Fehlerwahrscheinlichkeiten):

Wenn Burst-Fehler dominieren

XOR, die Zweierkomplementaddition und die CRC-Prüfsummen bieten eine bessere Fehlererkennungsleistung als die Komplementadditions-, Fletcher- und Adler-Prüfsummen.

In anderen Anwendungen

zur Fehlererkennung sollte nach Möglichkeit ein „gutes“ CRC-Polynom verwendet werden

Wenn die Berechnungskosten sehr begrenzt sind

(wie in Ihrem Fall), verwenden Sie (in der Reihenfolge der Wirksamkeit):

Andere Zitate:

Die Fletcher-Prüfsumme hat geringere Rechenkosten als die Adler-Prüfsumme und ist entgegen der landläufigen Meinung in den meisten Situationen auch effektiver.

und

Es gibt im Allgemeinen keinen Grund, die gängige Praxis der Verwendung einer XOR-Prüfsumme in neuen Designs) fortzusetzen, da diese die gleichen Software-Rechenkosten wie eine additionsbasierte Prüfsumme hat, jedoch nur etwa halb so effektiv ist Fehler erkennen.

11
Martin Thompson

Einfach Ein-Bit-Parität (im Grunde XORing der Daten immer wieder über sich selbst) ist so schnell wie möglich. Sie verlieren jedoch viel von der Fehlerprüfung eines CRC.

Im Pseudocode:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
11
Billy ONeal

Die Adler-Prüfsumme sollte ausreichen, um Übertragungsverzerrungen festzustellen. Es wird von der Zlib-Komprimierungsbibliothek verwendet und vom Java 3D Mobile Graphics Standard) übernommen, um eine schnelle, aber effektive Überprüfung der Datenintegrität zu ermöglichen.

Von der Wikipedia-Seite :

Eine Adler-32-Prüfsumme wird erhalten, indem zwei 16-Bit-Prüfsummen A und B berechnet und ihre Bits zu einer 32-Bit-Ganzzahl verkettet werden. A ist die Summe aller Bytes in der Zeichenfolge plus eins, und B ist die Summe der einzelnen Werte von A aus jedem Schritt.

Zu Beginn eines Adler-32-Laufs wird A auf 1, B auf 0 initialisiert. Die Summen werden modulo 65521 (die größte Primzahl kleiner als 2 ^ 16 oder 65536) berechnet. Die Bytes werden in der Netzwerkreihenfolge (Big Endian) gespeichert, wobei B die beiden höchstwertigen Bytes belegt.

Die Funktion kann ausgedrückt werden als

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

dabei ist D die Folge von Bytes, für die die Prüfsumme berechnet werden soll, und n die Länge von D.

6
Gnawme

Mir ist nichts bekannt, das bei der Fehlererkennung so effektiv ist wie ein CRC und schneller - wenn es das gäbe, würden die Leute es stattdessen verwenden.

Sie könnten eine einfache Prüfsumme versuchen, aber es ist weitaus weniger wahrscheinlich, dass Fehler erkannt werden.

5
Bob Murphy

Nun, die Prüfsummenlogik selbst ist gut und die Leute können mit schnelleren Algorithmen helfen.

Wenn Sie die Geschwindigkeit Ihrer Komponente verbessern möchten, müssen Sie möglicherweise Ihre Gesamttechnik ändern, um die Übertragungskomponente von der Validierungskomponente zu trennen.

Wenn Sie diese als zwei unabhängige Elemente (in verschiedenen Threads) haben, können Sie Ihre volle Übertragungsgeschwindigkeit erhalten und nur fehlgeschlagene Pakete erneut senden.

Der Algorithmus würde ungefähr so ​​aussehen:

  • Der Server teilt sich in bekannte Paketgrößen auf (z. B. 1K-Blöcke). Stellt sie in die Warteschlange "gesendet werden".
  • Jedes Paket wird mit einer 16- oder 32-Bit-ID UND seiner Prüfsumme gesendet.
  • Der Client empfängt jedes Paket und stellt es in eine zu verarbeitende Warteschlange.
  • Auf einem separaten Thread nimmt der Client jeweils ein Paket ab und führt die Validierung durch.
    • Bei Erfolg wird es der endgültigen Sammlung von Paketen (in ID-Reihenfolge) hinzugefügt
    • Bei einem Fehler wird die fehlgeschlagene ID an den Server zurückgemeldet, der das erneut zu sendende Paket in die Warteschlange stellt.
  • Sobald Sie die Pakete erhalten und validiert haben und die IDs in der richtigen Reihenfolge (ab 1) haben, können Sie diese auf die Festplatte schreiben (oder tun, was immer erforderlich ist).

Auf diese Weise können Sie mit der höchstmöglichen Geschwindigkeit senden. Wenn Sie mit Ihrer Paketgröße spielen, können Sie die Optimium-Fehlerrate im Vergleich zur Validierungs-/Wiederholungsrate ermitteln.

3
Robin Vessey

Prüfsummen sind traditionell

(# '+ Stream reduzieren)

XOR wie oben angegeben würde ebenfalls funktionieren

(Reduziere den XOR-Stream #)

Ein etwas ausgefeilteres (langsameres) Schema ist die Standardparitätsprüfung für serielle Verbindungen.

Auf dieser Ebene tauschen Sie Korrektheit gegen Geschwindigkeit. Diese werden gelegentlich fehlschlagen.

Auf der nächst anspruchsvolleren Ebene können Sie einige Dinge vom Typ crc/hash verwenden.

Ein anderes Design wäre, die Größe des für den Stream verwendeten Blocks zu erhöhen.

Sie sollten eine Schätzung der tatsächlichen Fehlerrate haben, um Ihre Algorithmusauswahl und Parameter für die Blockgröße abzustimmen.

2
Paul Nathan