Fehlererkennung Effizienz (CRC, Prüfsumme, etc)

Question

Ich habe eine hypothetische Situation des Sendens von Dateneinheiten, jeder von tausend Bytes. Die Fehlerrate ist selten, aber wenn ein Fehler auftritt, ist es weniger wahrscheinlich, dass es sich um einen Einzelbitfehler handelt, und es ist wahrscheinlicher, dass es ein Fehler in einigen Bits hintereinander ist.

Zuerst dachte ich an die Verwendung einer Prüfsumme, aber das kann Bitfehler übersehen, die größer als ein einzelnes Bit sind. Eine Paritätsprüfung funktioniert auch nicht, daher könnte CRC die beste Option sein.

Verwendet eine zyklische Redundanzprüfung auf tausend Bytes effizient? Oder gibt es andere Methoden, die besser funktionieren würden?

Answer 1

Cyclic Redundancy Checks (CRC) sind beliebte speziell wegen ihrer Effizienz bei mehreren Bitfehler mit einer garantierten Genauigkeit zu erfassen.

Es gibt verschiedene Designs zum Generieren von CRC-Polynomen, bei denen der Kompromiss zwischen Genauigkeit und Rechenkomplexität besteht. In Ihrem Fall können Sie den "schnellsten" auswählen, der Ihren Anforderungen an Genauigkeit entspricht.

Sie können mit diesem Wikipedia-Artikel auf der Cyclic Redundancy Check beginnen.

Answer 2

Es ist normal, einen CRC zu verwenden. Ich bin mir nicht sicher, was Sie mit "Effizienz" meinen, aber ich denke, dass der CRC manchmal in Hardware implementiert ist (z. B. auf der Ethernet-Karte). Andernfalls können Sie "optimierte" Implementierungen finden (mithilfe einer Nachschlagetabelle).

Answer 3

CRC ist in einer anderen Frage hier bedeckt
When is CRC more appropriate to use than MD5/SHA1?
Es eignet sich zum Nachweis von zufälligen Fehlern und einfach zu implementieren.

Answer 4

Wie groß sind Ihre Festplattensektoren? Wahrscheinlich mindestens 512 Bytes. Und CRC ist ein altehrwürdiges Schema für Festplatten-ECC auf Hardware-Ebene.

Die Aktien-CRC-Polynomalgorithmen sind ziemlich effektiv für kleine Zahlen von Bitfehlern. Die genaue Genauigkeit ist mathematisch berechenbar. CRC ist auch sehr effizient in der Hardware, wo eine relativ kleine Anzahl von Gattern und Schieberegistern den Job im Fluge verwalten kann.