Dies ist ein als exzellent ausgezeichneter Artikel.

Fletcher’s Checksum

aus Wikipedia, der freien Enzyklopädie

Fletcher’s Checksum (übersetzt „Fletchers Prüfsumme“, auch Fletcher checksum oder Fletcher algorithm) ist ein 1982 von John G. Fletcher (1934–2012)[1] vorgestelltes Fehlererkennungsverfahren in Form einer Prüfsumme. Mit dem Verfahren können Fehler, beispielsweise in einer digitalen Datenübertragung, entdeckt werden. Es basiert darauf, dass die einzelnen Bits der Nachricht nicht nur aufsummiert, sondern zusätzlich abhängig von ihrer Position gewichtet werden. Damit stellt der Algorithmus einen Kompromiss zwischen der langsameren, aber sensitiveren zyklischen Redundanzprüfung (CRC) und fehleranfälligen Verfahren wie einer einfachen Prüfsumme oder vertikaler Redundanzprüfung dar. Fletcher’s Checksum wird unter anderem in verschiedenen Netzwerkprotokollen und Dateisystemen verwendet.

Der Algorithmus

Die binär übertragene Nachricht wird in Abschnitte der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} unterteilt, jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} Bit bilden somit einen Block. Der letzte Block wird gegebenenfalls für die Dauer des Algorithmus aufgefüllt und jeder Block als vorzeichenloser Integer interpretiert. Die Anzahl der Blöcke sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{length}} . Der Prüfwert besteht aus zwei verschiedenen Summen: Die erste (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_1} ) summiert schrittweise sämtliche Blöcke auf, die zweite (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} ) ist die Summe aller Zwischenergebnisse der ersten Summe.[2] Der erste Block geht also -mal in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} ein, der letzte dagegen nur einmal. Werden durch eine Störung beim Übertragen Bits invertiert oder zwei Blöcke unterschiedlichen Wertes vertauscht, verändert sich im Normalfall der Prüfwert: Der Fehler fällt auf.

Da der Prüfwert unabhängig von der Länge der Nachricht in einer festen Anzahl von Bits (im Allgemeinen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2\cdot K} ) übertragen werden können soll, werden beide Summen zuletzt modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} gerechnet und anschließend in die Nachricht integriert. Normalerweise wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = 2^K} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = 2^K-1} gewählt.[2] Letzteres ist trotz leicht aufwändigerer Berechnung zu bevorzugen, weil Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^K-1} vergleichbar groß ist, im Gegensatz zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^K} jedoch nicht durch 2 – die Basis des Binärsystems – teilbar.[3] Für das Ergebnis ist unerheblich, ob die Modulo-Operation nach jeder Addition oder am Ende angewandt wird.[4] Um Überlauf zu vermeiden, erfolgt sie in einer Implementierung schon im Laufe der Berechnung.

Die Anzahl an möglichen Prüfwerten von Fletcher’s Checksum beträgt . Eine genügend lange Nachricht vorausgesetzt, verringert sich also mit größerem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} die Wahrscheinlichkeit, dass eine verfälschte Nachricht denselben Prüfwert aufweist.[5] Grundsätzlich kann für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} eine beliebige natürliche Zahl gewählt werden, der Algorithmus würde entsprechend als Fletcher-Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2\cdot K} bezeichnet werden. Verbreitet sind Fletcher-16 und Fletcher-32, teilweise auch Fletcher-8.[5]

Beispielrechnung

Wird die Nachricht „Wikipedia“ in ASCII binär übermittelt, findet für Fletcher-16 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=255} die in der Tabelle ausgeführte Rechnung statt. Ist ein Zwischenergebnis einer Summe größergleich 255, wird modulo angewendet, hier dargestellt als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} .

Nachricht W i k i p e d i a Ergebnis
binäre Darstellung 01010111 01101001 01101011 01101001 01110000 01100101 01100100 01101001 01100001
dezimaler Wert 87 105 107 105 112 101 100 105 97
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_1} 87 192 299 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 44 149 261 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 6 107 207 312 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 57 154 154
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} 87 279 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 24 68 217 223 330 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 75 282 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \equiv} 27 84 238 238

Pseudocode

Nachfolgend ein Pseudocode für Fletcher-16 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=255} ohne jegliche Optimierung. Als Prüfwert werden beide Summen aufeinanderfolgend zurückgegeben. 

Fletcher_16 (data)
Input: Array data von 8-Bit-Integern
Output: 16-Bit-Prüfsumme zu data

sum1 := 0
sum2 := 0
for i := 0 to length (data) do
    sum1 := (sum1 + data[i]) modulo 255
    sum2 := (sum2 + sum1) modulo 255
endfor
checksum := sum1 gefolgt von sum2
return checksum

Varianten

In einer Variante, die Fletchers ursprünglichem Algorithmus näher liegt,[2] werden zwei Prüfblöcke der Länge an das Ende der Nachricht angehängt, die derart gewählt werden, dass beide Summen des Prüfwerts über die neue, verlängerte Nachricht null betragen. Dazu werden die beiden Summen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} zunächst wie gehabt berechnet. Dem ersten Prüfblock wird dann der Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -\text{sum}_1 - \text{sum}_2 \pmod{M}} zugewiesen, dem zweiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} . Betty Salzberg zeigte kurz nach Fletchers Veröffentlichung, dass die Lage der beiden aufeinanderfolgenden Prüfblöcke beliebig innerhalb der Nachricht gewählt werden kann, ohne dass dabei die Prüfeigenschaften verschlechtert werden. Sollen die Blöcke an die Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} , ist ihr Wert als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\text{length} - n)\cdot \text{sum}_1 - \text{sum}_2} und , jeweils modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} , zu wählen. Dabei entspricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{length}} der Anzahl an Blöcken der ursprünglichen Nachricht.[6] Tatsächlich können die beiden Blöcke an frei wählbaren Stellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} stehen, solange der Betrag Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |i-j|} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} teilerfremd sind.[7]

Keith Sklower entwickelte eine Rekursion, die zwei Blöcke auf einmal verarbeitet und am Ende denselben Prüfwert wie Fletcher’s Checksum erzeugt.[8] Des Weiteren kann es in bestimmten Fehlermodellen von Vorteil sein, den Prüfwert im Trailer statt wie in den meisten Netzwerkprotokollen im Header unterzubringen.[9]

Optimierung

Werden die Summen in jeweils mehr als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} Bit gespeichert, muss die Modulo-Operation nicht nach jeder Addition erfolgen, sondern erst, wenn die Variable überzulaufen droht. Man nimmt den Worst Case an, also eine Nachricht, bei der jeder Block den größtmöglichen Wert aufweist, um eine obere Grenze (upper bound) für die Anzahl an Additionen ohne Überlauf zu ermitteln. Besitzen beide Summen denselben Datentyp, erfolgt dieser zuerst auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_2} . Bei einer Umsetzung von Fletcher-16 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K=8} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=255} sowie unter Verwendung von vorzeichenlosen 16-Bit-Integers beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_u = 21} .[10]

Zusätzlich kann die Modulo-Operation durch bitweise Operatoren ersetzt werden. Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=2^K} , genügt x & (M-1) statt x % M (notiert in der Programmiersprache C), für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=2^K-1} könnte die Einerkomplement-Arithmetik verwendet werden, bei der sich durch das in dieser Arithmetik erforderliche Addieren des Übertrags (end-around carry) das passende Resultat ergibt. Allerdings verwendet heutige Hardware nahezu ausschließlich eine Zweierkomplement-Arithmetik, das Addieren des Übertrags kann in diesem Fall durch (x & (M-1)) + (x >> K) imitiert werden, unter der Voraussetzung, dass der verwendete Datentyp mehr als Bits aufnehmen kann.[11] In der Literatur zu Prüfsummen allgemein und auch bei Fletcher wird dementsprechend häufig als Einer- und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=2^K} als Zweierkomplementversion bezeichnet.[2]

Fletcher’s Checksum kann sowohl parallelisiert als auch vektorisiert werden.[12] Der Algorithmus kann zusätzlich durch generelle Optimierungsmethoden, insbesondere Loop unrolling, beschleunigt werden.

Geschichte

John Fletcher entwickelte den Algorithmus Ende der 1970er Jahre im Lawrence Livermore National Laboratory. Im Januar 1982 veröffentlichte die IEEE Communications Society Fletchers Artikel über die Prüfsumme und ihre Eigenschaften in IEEE Transactions on Communications.[13] Darin begründet er seine Entwicklung einer arithmetischen Prüfsumme damit, dass Computer eher für arithmetische Operationen als für Polynomdivision, wie sie die zyklische Redundanzprüfung benötigt, ausgelegt seien. Fletcher beschrieb den Prüfwert nicht als Zusammensetzung von zwei, sondern von beliebig vielen Summen, wobei die erste wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{sum}_1} berechnet wird und jede weitere die Zwischenergebnisse der vorhergehenden aufsummiert.[2] Die Verwendung von mehr als zwei Summen verbessert den Algorithmus jedoch nicht genügend, um die Verlangsamung zu rechtfertigen.[14]

Angepasste Varianten von Fletchers Algorithmus werden unter anderem in der vierten Schicht (Transport) des ISO-Netzwerkprotokollstandards[15] und im IS-IS-Protokoll[16] eingesetzt. J. Zweig und C. Partridge schlugen 1990 vor, das TCP dahingehend zu erweitern, dass Fletcher’s Checksum verwendet werden kann.[17] Diese Erweiterung besitzt seit 2011 den Status Historic.[18] Sowohl im 2006 eingeführten Dateisystem ZFS[19] als auch im 2016 vorgestellten Apple File System[20] wird die Prüfsumme genutzt.

1995 stellte Mark Adler mit Adler-32 eine Variation von Fletcher-32 vor, bei der modulo 65.521 (die größte Primzahl kleiner 216) gerechnet wird.

Eigenschaften und Vergleich mit anderen Verfahren

Bei gleicher Byteanzahl des Prüfwerts ist Fletcher’s Checksum einer gut implementierten zyklischen Redundanzprüfung (CRC) in der Fehlererkennung unterlegen.[21] Dafür kann die Berechnung schon beginnen, bevor die Nachricht vollendet wurde, da es keine direkten Abhängigkeiten zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{length}} gibt.[7] Werden einzelne Blöcke verändert, nachdem die Prüfsumme bereits ausgerechnet wurde, kann diese aktualisiert werden, ohne auf die unveränderten Blöcke zuzugreifen.[22]

Nachfolgende Eigenschaften beziehen sich stets auf den Algorithmus mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=2^K-1} . Fletcher’s Checksum entdeckt alle Bündelfehler bis zur Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} , anfällig ist es gegen solche Burstfehler, die einen Block aus nur Einsen zu einem aus nur Nullen invertieren oder umgekehrt, denn modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^K-1} sind diese beiden Blöcke äquivalent. Lässt man diese spezielle Art von Fehler aus der Betrachtung heraus, werden alle Bündelfehler bis zur Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2\cdot K} erkannt.[23] Für Nachrichten bis zu einer Länge von Bit besitzt das Verfahren eine Hamming-Distanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h=3} , für längere Nachrichten ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h=2} . Fletcher-16 erkennt also ab Nachrichtenlänge von 2.056 Bit nicht mehr alle Zwei-Bit-Fehler,[24] während für eine geeignete CRC mit einem gleichlangen Prüfwert ein Abstand zwischen den beiden Fehlern von bis zu 65.535 Bit noch zum Erkennen reicht. Hier offenbart sich eine Schwäche der Umsetzung von Fletcher-16 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M=256} , da hier der Abstand kleinergleich 16 Bit sein muss.[25]

Fletcher’s Checksum erkennt keine fälschlich an eine Nachricht angehängten Nullen, da sich dadurch die Summen nicht mehr verändern. Dies kann verhindert werden, indem der Empfänger entweder die Länge der Nachricht im Voraus kennt oder sie ihm innerhalb dieser mitgeteilt wird.[26]

Obwohl bei Adler-32 die Besetzung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} durch eine Primzahl die möglichen Prüfwerte besser verteilt, gibt es doch insgesamt weniger von ihnen, sodass die aufwändigere Berechnung trotzdem fast immer schlechter prüft als Fletcher-32.[5]

Damit ist Fletcher’s Checksum bei gleicher Bitanzahl des Prüfwerts sowohl einfachen Algorithmen wie der vertikalen Redundanzprüfung, einer simplen Summe oder der XOR-Prüfsumme als auch der Adler-Prüfsumme überlegen. Ist eine CRC umsetzbar, sollte diese jedoch bevorzugt werden.[27]

Literatur

Weblinks

Einzelnachweise

  1. ↑ In Memoriam John Fletcher. Lawrence Livermore National Laboratory, abgerufen am 16. März 2017 (englisch).
  2. ↑ a b c d e John G. Fletcher: An Arithmetic Checksum for Serial Transmissions. 1982, S. 248.
  3. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 71f.
  4. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 76f.
  5. ↑ a b c Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 69.
  6. ↑ Betty Salzberg: A Modification of Fletcher’s Checksum. In: IEEE Transactions on Communications. Jahrgang 31, Heft 2, 1983, doi:10.1109/TCOM.1983.1095789, S. 296.
  7. ↑ a b Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 65.
  8. ↑ Keith Sklower: Improving the Efficiency of the OSI Checksum Calculation. In: Computer Communication Review. Jahrgang 19, Heft 5, 1989, doi:10.1145/74681.74684, S. 32–43 (PDF; 524 kB).
  9. ↑ Jonathan Stone, Michael Greenwald, Craig Partridge, James Hughes: Performance of Checksums and CRC’s over Real Data. In: IEEE/ACM Transactions on Networking. Jahrgang 6, Heft 5, 1998, doi:10.1109/90.731187.
  10. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 68, für die Herleitung siehe Appendix A, S. 76ff.
  11. ↑ Douglas W. Jones: Modulus without Division, a tutorial. 2001.
  12. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, Appendix D, S. 84ff.
  13. ↑ John Kodis: Fletcher’s Checksum: Error correction at a fraction of the cost. 1992, Kapitel Enter Fletcher.
  14. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 70, S. 72.
  15. ↑ Für den verwendeten Code siehe Gerard J. Holzmann: Design and Validation of Computer Protocols. Prentice Hall, 1991, ISBN 0-13-539925-4, S. 63.
  16. ↑ Adrian Farrel: The Internet and Its Protocols: A Comparative Approach. Morgan Kaufmann, San Francisco 2004, ISBN 155860913X, S. 181 (eingeschränkte Vorschau in der Google-Buchsuche).
  17. ↑ J. Zweig, C. Partridge: TCP Alternate Checksum Options. RFC 1146, 1990.
  18. ↑ L. Eggert: Moving the Undeployed TCP Extensions RFC 1072, RFC 1106, RFC 1110, RFC 1145, RFC 1146, RFC 1379, RFC 1644, and RFC 1693 to Historic Status. RFC 6247, 2011.
  19. ↑ James Guilford, Vinodh Gopal: Fast Computation of Fletcher Checksums. Intel Data Center Group, 14. Januar 2016, Kapitel Introduction.
  20. ↑ Für den verwendeten Code siehe Matthias Luft: ERNW Whitepaper 65 – APFS Internals for Forensic Analysis. 16. April 2018, S. 7f.
  21. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 67.
  22. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 65, für Formeln und deren Herleitung siehe Appendix B, S. 80ff.
  23. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 64f.
  24. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 65.
  25. ↑ John G. Fletcher: An Arithmetic Checksum for Serial Transmissions. 1982, S. 251.
  26. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 73.
  27. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 70.
Abgerufen von „https://de.wikiup.org/index.php?title=Fletcher’s_Checksum&oldid=190764334“