„Fletcher’s Checksum“ – Versionsunterschied

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. Mithilfe des Verfahrens können beispielsweise Fehler 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 besseren Zyklischen Redundanzprüfung und den fehleranfälligeren simplen Berechnungen wie einer einfachen Summe oder der Vertikalen Redundanzprüfung dar. Fletcher’s Checksum wird unter anderem in verschiedenen Netzwerkprotokollen verwendet.

Die binär übertragene Nachricht wird in Abschnitte der Länge ${\displaystyle K}$ unterteilt, jeweils ${\displaystyle K}$ Bits bilden dann einen Block. Der letzte Block wird gegebenenfalls aufgefüllt und jeder Block als unsigned Integer interpretiert. Die Anzahl der Blöcke sei ${\displaystyle length}$. Der Prüfwert besteht aus zwei verschiedenen Summen: Die erste (${\displaystyle sum_{1}}$) summiert nacheinander sämtliche Blöcke auf, die zweite (${\displaystyle sum_{2}}$) ist die Summe aller Zwischenergebnisse der ersten Summe.^[2] Der erste Block geht also ${\displaystyle length}$-mal in ${\displaystyle 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 ${\displaystyle 2\cdot K}$) übertragen werden können soll, werden beide Summen zuletzt modulo ${\displaystyle M}$ gerechnet und anschließend in die Nachricht integriert. Normalerweise wird ${\displaystyle M=2^{K}}$ oder ${\displaystyle M=2^{K}-1}$ gewählt.^[2] Letzteres entspricht einer Berechnung im Einerkomplement, kann aber auch auf heutigen Computern, die das Zweierkomplement benutzen, imitiert werden. Für das Ergebnis ist unerheblich, ob die Modulo-Operation nach jeder Addition oder am Ende erfolgt.^[3] Um Überlauf zu vermeiden, erfolgt in einer Implementierung diese Rechnung nicht erst am Ende.

Grundsätzlich kann für ${\displaystyle K}$ eine beliebige natürliche Zahl gewählt werden, der Algorithmus würde entsprechend als Fletcher-${\displaystyle 2\cdot K}$ bezeichnet werden. Verbreitet sind Fletcher-16 und Fletcher-32, teilweise auch Fletcher-8.^[4]

Wird die Nachricht „Wikipedia“ in ASCII binär übermittelt, findet für Fletcher-16 mit ${\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 ${\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
${\displaystyle sum_{1}}$	87	192	299 ${\displaystyle \equiv }$ 44	149	261 ${\displaystyle \equiv }$ 6	107	207	312 ${\displaystyle \equiv }$ 57	154	154
${\displaystyle sum_{2}}$	87	279 ${\displaystyle \equiv }$ 24	68	217	223	330 ${\displaystyle \equiv }$ 75	282 ${\displaystyle \equiv }$ 27	84	238	238

In C auf einer Zweierkomplementmaschine könnte eine Umsetzung eines Unterprogramms für Fletcher-16 mit ${\displaystyle M=255}$, das als Prüfwert eine 16-Bit-unsigned-Integer zurückgibt, die beide Summen aufeinanderfolgend beinhaltet, folgendermaßen aussehen:

  uint16_t Fletcher-16 (const uint8_t* data, const size_t length) {

      uint16_t sum1 = 0, sum2 = 0;

      for (size_t i = 0; i < length; i++) {
          sum1 = (sum1 + data[i]) % 255;
          sum2 = (sum2 + sum1) % 255;
      }

      return (sum2 << 8) | sum1;
  }

In einer Variante, die Fletchers ursprünglichem Algorithmus näher liegt,^[2] werden zwei Prüfblöcke der Länge ${\displaystyle K}$ 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 ${\displaystyle sum_{1}}$ und ${\displaystyle sum_{2}}$ zur Nachricht zuerst wie gehabt berechnet. Dem nächsten Block wird dann der Wert ${\displaystyle -sum_{1}-sum_{2}{\pmod {M}}}$ zugewiesen, dem übernächsten ${\displaystyle 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 ${\displaystyle n}$ bzw. ${\displaystyle n+1}$, ist ihr Wert als ${\displaystyle (length-n)\cdot sum_{1}-sum_{2}}$ und ${\displaystyle (length-(n-1))\cdot (-sum_{1})+sum_{2}}$, jeweils modulo ${\displaystyle M}$, zu wählen. Dabei entspricht ${\displaystyle length}$ der Anzahl an Blöcken der ursprünglichen Nachricht.^[5] Tatsachlich können die beiden Blöcke an frei wählbaren Stellen ${\displaystyle i}$ und ${\displaystyle j}$ stehen, solange der Betrag ${\displaystyle |i-j|}$ und ${\displaystyle M}$ teilerfremd sind.^[6]

Keith Sklower entwickelte eine Rekursion, die zwei Blöcke auf einmal verarbeitet und am Ende denselben Prüfwert wie Fletcher’s Checksum erzeugt.^[7]

In bestimmten Fehlermodellen kann es von Vorteil sein, den Prüfwert im Trailer statt im Header, wie es in den meisten Netzwerkprotokollen umgesetzt ist, unterzubringen.^[8]

Werden die Summen in mehr als ${\displaystyle K}$ Bits gespeichert, muss die Modulo-Operation nicht nach jeder Addition erfolgen, sondern erst, wenn die Variable droht überzulaufen. 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) ${\displaystyle B_{u}}$ für die Anzahl an Additionen ohne Überlauf zu ermitteln. Besitzen beide Summen denselben Datentyp, erfolgt dieser zuerst auf ${\displaystyle sum_{2}}$. Bei einer Umsetzung von Fletcher-16 mit ${\displaystyle K=8}$ und ${\displaystyle M=255}$ sowie unter Gebrauch von 16-Bit-unsigned-Integers beträgt ${\displaystyle B_{u}=21}$.^[9]

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

John Fletcher entwickelte diesen 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.^[11] Darin begründet er seine Erfindung einer arithmetischen Prüfsumme damit, dass Computer eher für arithmetische Operationen (Grundrechenarten) als für Polynomdivision, wie es die Zyklische Redundanzprüfung benötigt, ausgelegt sind. Fletcher beschrieb den Prüfwert nicht als Zusammensetzung von zwei, sondern allgemein von beliebig vielen Summen, wobei die erste wie ${\displaystyle sum_{1}}$ fungiert 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.^[12]

Angepasste Varianten von Fletchers Algorithmus werden unter anderem in der vierten Schicht (Transport) des ISO-Netzwerkprotokollstandards^[13] und im IS-IS-Protokoll^[14] eingesetzt. J. Zweig und C. Partridge schlugen 1990 vor, das TCP dahingehend zu erweitern, dass Fletcher’s Checksum verwendet werden kann.^[15] Diese Erweiterung besitzt seit 2011 den Status Historic.^[16]

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

Einer gut implementierten Zyklischen Redundanzprüfung (CRC) ist Fletcher’s Checksum bei gleicher Byteanzahl des Prüfwerts in der Fehlererkennung unterlegen.^[17] Dafür kann die Berechnung schon beginnen, bevor die Nachricht vollendet wurde, da es keine direkten Abhängigkeiten zu ${\displaystyle length}$ gibt.^[6] 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.^[18]

Die Anzahl an möglichen Prüfwerten von Fletcher’s Checksum beträgt ${\displaystyle M^{2}}$, im Folgenden sei angenommen, dass mit steigenden ${\displaystyle K}$ auch ${\displaystyle M}$ entsprechend größer gewählt wird. Eine genügend lange Nachricht vorausgesetzt, verringert sich also die Anzahl an unerkannten Fehlern, je größer ${\displaystyle K}$ gewählt wird.^[4] Nach dieser Logik sollte die Einerkomplement-Variante von Fletcher’s Checksum schlechter sein als die im Zweierkomplement. ${\displaystyle 2^{K}-1}$ besitzt jedoch wesentlich weniger Primfaktoren als ${\displaystyle 2^{K}}$, weswegen die Einerkomplement-Variante trotz leicht aufwändigerer Berechnung zu bevorzugen ist.^[19] Nachfolgende Eigenschaften beziehen sich stets auf den Algorithmus mit ${\displaystyle M=2^{K}-1}$.

Bis zu einer von ${\displaystyle M}$ abhängigen Länge der Nachricht besitzt Fletcher’s Checksum eine Hamming-Distanz von ${\displaystyle h=3}$, für längere Nachrichten ist ${\displaystyle h=2}$. Ein-Bit-Fehler werden demnach immer entdeckt, einzelne Zwei-Bit-Fehler nicht mehr, wenn sie mehr als ${\displaystyle K\cdot M=K\cdot (2^{K}-1)}$ Bits auseinanderliegen: Bei Fletcher-16 gilt die schlechtere Hamming-Distanz also ab einer Nachrichtenlänge von 2.056 Bit,^[20] während für eine geeignete CRC mit einem gleichlangen Prüfwert ein Abstand zwischen den beiden Fehlern von kleinergleich 65.535 Bits noch zum Erkennen reicht. Hier offenbart sich die Schwäche der Umsetzung mit ${\displaystyle M=256}$, für diese muss der Abstand kleinergleich 16 Bits sein.^[21] Das Verfahren entdeckt alle Bündelfehler bis zur Länge ${\displaystyle k}$, anfällig ist es gegen solche Burstfehler, die alle Einsen innerhalb eines Blocks zu Nullen invertieren oder vice versa, denn im Einerkomplement sind dies die beiden Darstellungen der Null. Lässt man diese spezielle Art von Fehler aus der Betrachtung heraus, werden alle Bündelfehler bis zur Länge ${\displaystyle 2\cdot k}$ erkannt.^[22]

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.^[23]

Obwohl bei Adler-32 die Besetzung von ${\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.^[4]

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 und sollte benutzt werden, sofern die Rechenleistung vorhanden ist. Ist eine CRC umsetzbar, sollte diese jedoch bevorzugt werden.^[24]

• John G. Fletcher: An Arithmetic Checksum for Serial Transmissions. In: IEEE Transactions on Communications. Jahrgang 30, Heft 1, 1982, doi:10.1109/TCOM.1982.1095369, S. 247–252.
• Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. In: Computer Communication Review. Jahrgang 18, Heft 5, 1988, doi:10.1145/53644.53648, S. 63–88.
• John Kodis: Fletcher’s Checksum: Error correction at a fraction of the cost. In: Dr. Dobb’s Journal. Jahrgang 17, Heft 5, 1992, ISSN 1044-789X, S. 32.
• Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. In: IEEE Transactions on Dependable and Secure Computing. Jahrgang 6, Heft 1, 2009, doi:10.1109/TDSC.2007.70216, insbesondere Kapitel 3.4 (PDF; 676 kB).

• J. Zweig, C. Partridge: TCP Alternate Checksum Options. RFC 1146, 1990.
• Implementierung von Fletcher-16 in verschiedenen Programmiersprachen (englisch)

1. ↑ In Memoriam John Fletcher. Lawrence Livermore National Laboratory, abgerufen am 16. März 2017 (englisch).
2. ↑ ^{a b c d} 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. 76f.
4. ↑ ^{a b c} Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 69.
5. ↑ 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.
6. ↑ ^{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.
7. ↑ 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).
8. ↑ 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.
9. ↑ 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.
10. ↑ 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.
11. ↑ John Kodis: Fletcher’s Checksum: Error correction at a fraction of the cost. 1992, Kapitel Enter Fletcher.
12. ↑ 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.
13. ↑ David M. Piscitello, A. Lyman Chapin: Open Systems Networking: TCP/IP and OSI. Addison-Wesley Longman, Boston 1993, ISBN 0201563347, Kapitel 12, S. 307.
14. ↑ 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).
15. ↑ J. Zweig, C. Partridge: TCP Alternate Checksum Options. RFC 1146, 1990.
16. ↑ 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.
17. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 67.
18. ↑ 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.
19. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 71f.
20. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 65.
21. ↑ John G. Fletcher: An Arithmetic Checksum for Serial Transmissions. 1982, S. 251.
22. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 64f.
23. ↑ Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 73.
24. ↑ Theresa C. Maxino, Philip J. Koopman: The Effectiveness of Checksums for Embedded Control Networks. 2009, S. 70.

Dieser Artikel nimmt am Schreibwettbewerb teil. Bitte hilf mit, ihn zu verbessern!