Ich führe eine Datenübertragung von einem dsPIC zu einem PC durch und führe eine 8-Bit-CRC für jeden Block mit 512 Bytes durch, um sicherzustellen, dass keine Fehler vorliegen. Wenn mein CRC-Code aktiviert ist, erhalte ich ungefähr 33 KB / s, ohne ihn erhalte ich 67 KB / s.

Mit welchen alternativen Fehlererkennungsalgorithmen können Sie feststellen, ob dies schneller ist?

Es gibt zwar möglicherweise schnellere Optionen als CRC, aber wenn Sie diese verwenden, werden Sie wahrscheinlich ein gewisses Maß an Fehlererkennungsfähigkeit einbüßen. Abhängig von Ihren Anforderungen an die Fehlererkennung besteht eine Alternative darin, stattdessen einen für Ihre Anwendung optimierten CRC-Code zu verwenden.

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

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

Es unterstützt das crc-8 Modell , sondern auch unterstützt crc-5, crc-16und crc-32unter anderem. Wie für Algorithmen unterstützt sie bit-by-bit, bit-by-bit-fastund 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

Sie können sogar irre Dinge wie das Festlegen mit Dual-Nibble-Lookups (mit einer 16-Byte-Lookup-Tabelle) anstelle von Single-Byte-Lookups (mit 256-Byte-Lookup-Tabelle) ausführen.

Zum Beispiel (Klonen des Git-Repository):

$ 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

Angesichts 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 jedoch ein Benchmarking.

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

Einfache Ein-Bit-Parität (im Grunde XOR-Verknüpfung der Daten über sich selbst immer wieder) ist ungefähr so ​​schnell wie möglich. Sie verlieren jedoch einen Großteil der Fehlerprüfung eines CRC.

Im Pseudocode:

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

Ein wirklich gutes Papier zum Vergleich der Leistung verschiedener Prüfsummen und CRCs in einem eingebetteten Kontext:

Die Wirksamkeit von Prüfsummen für eingebettete Netzwerke

Einige Zitate aus den Schlussfolgerungen (basierend auf ihren Studien über unentdeckte Fehlerwahrscheinlichkeiten):

Wenn Burst-Fehler dominieren

XOR, Zweierkomplementadditions- und CRC-Prüfsummen bieten eine bessere Fehlererkennungsleistung als die eigenen 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):

• Fletchers Prüfsumme
• jemandes Ergänzung
• Zweierkomplementaddition

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 übliche Praxis der Verwendung einer XOR-Prüfsumme in neuen Konstruktionen fortzusetzen, da sie die gleichen Software-Berechnungskosten wie eine additionsbasierte Prüfsumme hat, jedoch nur etwa halb so effektiv bei der Erkennung von Fehlern ist.

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 erfolgen modulo 65521 (die größte Primzahl kleiner als 2 ^ 16 oder 65536). 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 Zeichenfolge von Bytes, für die die Prüfsumme berechnet werden soll, und n ist die Länge von D.

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 es mit einer einfachen Prüfsumme versuchen, aber das ist weitaus unwahrscheinlicher, Fehler zu erkennen.

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 die gesamte Technik ändern, um die Übertragungskomponente von der Validierungskomponente zu trennen.

Wenn Sie diese als zwei unabhängige Elemente (auf verschiedenen Threads) haben, können Sie die 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-Chunks). Stellt sie in die Warteschlange "gesendet werden".
• Jedes Paket wird mit einer 16- oder 32-Bit-ID UND seiner Prüfsumme übertragen.
• Der Client empfängt jedes Paket und stellt es in eine Warteschlange, um es zu verarbeiten.
• Auf einem separaten Thread entnimmt der Client jeweils ein Paket 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 zu sendende Paket in die Warteschlange stellt.
• Sobald Sie die Pakete erhalten und validiert haben und die IDs in der richtigen Reihenfolge (beginnend mit 1) vorliegen, 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 übertragen, und wenn Sie mit Ihrer Paketgröße spielen, können Sie die Optimium-Fehlerrate im Vergleich zur Validierungs- / Erneutsenderate ermitteln.

Prüfsummen sind traditionell

(reduziere # '+ stream)

XOR wie oben angegeben würde ebenfalls funktionieren

(Reduziere # 'XOR-Stream)

Ein etwas aufwändigeres (langsameres) Schema ist die Standard-Paritä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ürde darin bestehen, 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.