Diskussion:Fletcher’s Checksum

Dieser Artikel war am 4. August 2017 der Artikel des Tages.

Für spätere Zwecke:

• In Memoriam John Fletcher. (Memento vom 16. März 2017 im Internet Archive)
• Implementierung von Fletcher-16 in verschiedenen Programmiersprachen (Memento vom 16. März 2017 im Internet Archive)

- – — zyranivia 13:51, 24. Mär. 2017 (CET)

• Peter Kankowski: Hash functions: An empirical comparison. (Memento vom 17. Februar 2019 im Internet Archive) 2009.

- – — zyranivia 13:16, 17. Feb. 2019 (CET)

Übertrag Review 26. Schreibwettbewerb

Fletcher’s Checksum (übersetzt „Fletchers Prüfsumme“, auch Fletcher Checksum oder Fletcher Algorithm) ist ein 1982 von John G. Fletcher (1934–2012) vorgestelltes Fehlererkennungsverfahren in Form einer Prüfsumme. Mithilfe des Verfahrens können beispielsweise Fehler in einer digitalen Datenübertragung entdeckt werden.

Nachdem mir diese Lücke im Artikelbestand aufgefallen ist, habe ich mir mal ein Herz genommen und meinen ersten Artikel geschrieben. Für Anmerkungen jeglicher Art bin ich dankbar - – — zyranivia 13:50, 24. Mär. 2017 (CET)

Prima! Schöner Artikel. Meine Hauptanmerkung bezieht sich auf die Sorge, dass Deine Zielgruppe sich auf IT- und Mathenerds beschränkt. Das wäre cool und kultig, aber für WP etwas schwierig. Zwar sollte das Niveau nicht gesenkt werden, aber alles vermieden werden, was Anfänger vor den Kopf stößt. Die Vorschläge gehen alle etwa in diese Richtung:

• Möglichst Anglismen vermeiden. 'Summe' statt 'sum'. Länge statt length. Auch das Lemma mit dem 's ist ein Anglismus.
• Block ist zwar ein deutsches Wort, aber in dieser Bedeutung kennen es nur Großrechnerfreaks. Entweder erklären oder einen bekannteren Begriff nehen.
• Im ersten Abschnitt (Der Algorithmus) würde ich am Ende des ersten Absatzes (nach ...Der Fehler fällt auf.) ein Beispiel einbauen mit einem witzigen Satz, bei dem Du die Checksum vorbildlich mit alles Zahlen usw. ausrechnest. Ich würde zB eine Zeile oder gereimte Doppelzeile aus dem Gedicht Die Brille von Christian Morgenstern nehmen. ;)

Beispielsweise dies Gedicht

läse, so bebrillt, man – nicht!

Dreiunddreißig seinesgleichen

gäben erst – Ein – Fragezeichen!!

• Vielleicht kannst Du für das C-Code-Beispiel auch das Beispiel in Pseudocode schreiben?

Viel Erfolg und Grüße--Pacogo7 (Diskussion) 13:14, 25. Mär. 2017 (CET)

Danke für deine Hinweise, Pacogo. Nach reichlicher Überlegung habe ich jedoch nur die Hälfte umgesetzt. Dass Block nicht allgemeinverständlich war, ist mir völlig entgangen, ich hoffe, dass die aktuelle Version das nun erklärt. Wenn dir eine bessere Formulierung einfällt, setze sie einfach ein! Eine (wesentlich kürzere) Beispielrechnung findet sich jetzt auch.

• Zu erstens: Ursprünglich hatte ich den Artikel Fletcher Checksum genannt, aber Fletcher’s überwiegt eindeutig in der Literatur. Auf deutsch habe ich dazu überhaupt nichts gefunden; um TF zu vermeiden, nun also dieser unschöne Anglizismus. length und sum zu ersetzen ist schwierig. Es sollte kleingeschrieben bleiben, um Kohärenz mit dem C-Code zu bewahren: Variablen gehören nun mal kleingeschrieben. $summe_{x}$ verlängert die Formeln in den späteren Abschnitten unnötig, $s_{x}$ schien mir wiederum durch seine Kürze den Lesefluss zu irritieren. Ich habe einige weder technik- noch englischaffine Personen den Artikel lesen lassen und keine störte es, darum würde ich hier bei der gängigen Notation verbleiben.
• Zu viertens: Zusätzlichen Pseudocode fände ich Overkill. Der Algorithmus ist nicht übermäßig komplex, und wer keine Programmiersprache kennt, dem hilft Pseudocode genausowenig weiter wie C. Die Erklärung, jetzt bereichert durch das Rechenbeispiel, erläutert die Funktionsweise ausführlich genug, denke ich.

Viele Grüße - – — zyranivia 19:13, 25. Mär. 2017 (CET)

Kandidatur vom 06. Juni 2017 bis zum 01. Juli 2017

Fletcher’s Checksum (übersetzt „Fletchers Prüfsumme“, auch Fletcher Checksum oder Fletcher Algorithm) ist ein 1982 von John G. Fletcher (1934–2012) 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.

Mein Beitrag zum letzten Schreibwettbewerb hat es auf den siebten Platz geschafft.

„Der erste Artikel dieses Neuautoren stellt sein anspruchsvolles Thema prägnant vor. Soweit es bei diesem Thema möglich ist, ist hier Allgemeinverständlichkeit erreicht.“

Nun möchte ich schauen, ob es auch für ein Bapperl reicht. Ich danke Pacogo7 für sein Review und allen, insbesondere meinen Sektionsjuroren Toter Alter Mann und Iva für ihre Jurorentätigkeit; vielleicht habt ihr Zeit, euch hier zu Wort zu melden. Ansonsten freue ich mich über jegliche Bewertungen und sachdienliche Hinweise.

Kurzer Hinweis, bevor dazu Fragen aufkommen: Das ist tatsächlich mein erster Artikel, auch wenn ich bei Wikipedia wesentlich länger mitarbeite als dieser Nachfolgeaccount alt ist.

Als Hauptautor ohne Votum. Viele Grüße - – — zyranivia 16:33, 6. Jun. 2017 (CEST)

 Exzellent - Ich mache mal den Anfang: Habe den Artikel im Schreibwettbewerb erstmals gelesen und fand ihn dort schon außergewöhnlich bündig in Darstellung und Formulierung. Was aber den Ausschlag gibt ist die verständliche Aufbereitung.--Zweedorf22 (Diskussion) 18:24, 6. Jun. 2017 (CEST)

 Exzellent Artikel macht auf mich einen exzellenten ersten Eindruck.--JonskiC (Diskussion) 18:32, 6. Jun. 2017 (CEST)

Stimmt die Untergliederung systematisch? Jetzt heißt es "Beispielrechnung" und "Implementierung in C", das ist doch ein logisches Gefälle? Tatsächlich ist es aber keins. Eigentlich bräuchte es nur "(zwei) Beispielrechnungen" oder "Beispiele" zu heißen. Die beiden Fälle mit M=255 könnten ohne Unterüberschrift "Implementierung" hintereinander stehen, zumal das zweite Beispiel textlich nur aus einem Satz besteht. Um das zu veranschaulichen, habe ich es ausgeführt und wieder rückgängig gemacht. --Aalfons (Diskussion) 20:11, 6. Jun. 2017 (CEST)

Für alle anderen: Wir reden gerade von dieser Formatierung (neu) im Vergleich zu dieser dieser.

Danke erstmal für die konkrete Umsetzung, ich wäre mir sonst nicht sicher gewesen, was du meinst. Ich bin jedoch der Meinung, dass die Gliederung vorher klarer war. Die Unterkapitel über den Algorithmus steigern sich in ihrer Abstraktion und dem benötigten Vorwissen, und da gibt es definitiv einen Sprung von einer expliziten Beispielrechnung zu einem allgemeinen Codeschnipsel. Die kurzen Texte davor erklären nur die geltenden Parameter, um Missverständnisse zu vermeiden.

Außerdem suche zumindest ich in Artikeln über Algorithmen, nachdem ich die Einleitung gelesen habe, zuerst den Code auf (sofern existent), um zu verstehen, was der Algorithmus genau tut. Diesen unter „Beispiele“ zu suchen, fände ich nicht besonders intuitiv. Eine Überschrift „Implementierung“ würde die Tabelle unterschlagen, bliebe also „Beispielrechnung und Implementierung“ – dann lieber zwei eigene Abschnitte, die unabhängig voneinander betrachtet werden können.

Als Autor habe ich da natürlich einen gewissen blinden Fleck gegenüber meinem Artikel, das letzte Wort soll das hier also nicht sein. Viele Grüße - – — zyranivia 11:03, 7. Jun. 2017 (CEST)

ja, mein Einwand war schwierig zu verstehen. Vielleicht gibt's noch andere Stimmen zu diesem Gliederungsansatz. Vom grünen Bapperl wird mich das nicht abhalten, was OmA schon im SW am sicheren Textauftritt festmachte, und hier am Ausbleiben von Expertenkritik. --Aalfons (Diskussion) 11:27, 7. Jun. 2017 (CEST)

Kleiner Edelstein. Mindestens lesenswert, wenn nicht sogar  Exzellent--Pacogo7 (Diskussion) 00:46, 8. Jun. 2017 (CEST)

Ich fand ihn schon beim Schreibwettbewerb lesenswert und verständlich. Er hat seitdem noch "gewonnen", weshalb also nicht  Exzellent? Gruß -- Iva 22:54, 16. Jun. 2017 (CEST), Mitjurorin beim SW

Finde schön, dass es hier mal wieder einen interessanten IT-Artikel gibt. Aber das mit dem Einer- und Zweierkomplement scheint mir noch etwas misslungen: "...auch auf heutigen Computern, die das Zweierkomplement benutzen, imititiert werden...". Was heißt es denn, wenn ein Computer das Zweikomplement benutzt? Meiner Meinung nach kann es nur heißen, dass er für negative Zahlen die 2-Komplement-Darstellung verwendet. Aber negative Zahlen kommten im Algorithmus gar nicht vor. Also wo wird hier was imitiert? Verstehe ich nicht.--Cactus26 (Diskussion) 09:18, 23. Jun. 2017 (CEST)

Ihc habe mal ein bisschen recherchiert und auch den englischsprachigen Artikel und dessen Disk. mal genauer angesehen... Uff... Dass ein eigentlich so einfacher Algorithmus so viele Fallstricke haben kann... Ausgangspukt ist wohl das hier in rfc1146:

  The 8-bit Fletcher Checksum Algorithm is calculated over a sequence
  of data octets (call them D[1] through D[N]) by maintaining 2
  unsigned 1's-complement 8-bit accumulators A and B whose contents are
  initially zero, and performing the following loop where i ranges from
  1 to N:

          A := A + D[i]
          B := B + A

  It can be shown that at the end of the loop A will contain the 8-bit
  1's complement sum of all octets in the datagram, and that B will
  contain (N)D[1] + (N-1)D[2] + ... + D[N].

Hier spricht man von "unsigned 1's-complement 8-bit accumulators A", das heißt, hier wird von sehr spezisicher Hardware ausgegangen und der Überlauf soll stattfinden (entgegen der Aussage im Artikel und dem Beispiel), und der Überlauf soll so stattfinden, wie es bei "1's-complement 8-bit accumulators" denn so ist. Dort gibt es ziemlich sicher ein end-around carry. Ich frage mich da so einiges, beispielsweise auch, ob die Programmiersprache C bei unsigend-Datentypen überhaupt jemals ein "end-around carry" gemacht hat (ist ja eigentlich auch Blödsinn, denn negative Zahlen gibt es ja micht). Eine Sache, die mich sehr interessiert hätte, die ich aber auch im engl.spachigen Artikel bisher nicht gefunden habe, wäre, ob die "1-Komplement-Logik" nur historischer Balast ist, der der Kompatibilität und der Hardware der damaligen Zeit geschuldet ist, überhaupt irgendwas signifikantes zum Algorithmus beiträgt.

Ich finde, der Artikel sollte nochmals ins Review, würde mich dann beteiligen, falls das gewünscht wäre.--Cactus26 (Diskussion) 11:16, 23. Jun. 2017 (CEST)

Hoi, entschuldige die verspätete Antwort.

Ich arbeite das einfach mal chronologisch ab: Zweierkomplement bedeutet, dass im Gegensatz zum Einerkomplement das Vorzeichen nur indirekt ist. Wesentlicher Unterschied ist also die Darstellung von negativen Zahlen, was – wie du erkannt hast – für den Algorithmus irrelevant ist. Außerdem gibt es im Einerkomplement zwei Darstellungen der Null, alles Einsen und alles Nullen. Das findet sich etwas versteckt am Anfang des dritten Absatzes hier wieder, aber auch im entsprechenden Artikel. Diese Eigenschaft kann man in Zweierkomplementdarstellung imitieren, indem beispielsweise für Fletcher-16 modulo 255 rechnet; 0 und 255 sind dann äquivalent.

Ausgangspunkt ist nicht der RfC, sondern Fletchers Paper bzw. Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. Ich kann sie dir (und auch alle anderen zitierten Paper) per Mail zukommen lassen, wenn du möchtest. Dort wird der Algorithmus wie im Artikel entsprechend abstrakt behandelt, konkrete Hardwareumsetzungen aufzuführen kann nicht Aufgabe der Wikipedia sein. So findet sich hier im Gegensatz zu en-WP auch kein optimierter Code wieder; die konkreten Optimierungen hängen immer von Anwendung und Hardware ab, die Wege werden im entsprechenden Abschnitt wiedergegeben. So kann es, wie im RfC dargestellt, auch sein, dass der der Überlauf das macht, was man will – der Normalfall ist das nicht.

Warum $M=2^{K}-1$ gegenüber $M=2^{K}$ zu bevorzugen ist, wird so weit angerissen, wie man es verständlich ausdrücken kann, ohne gleich ein Paper zu schreiben. Wer mehr wissen möchte, kann sich an die Belege halten. Einer- bzw. Zweierkomplementversion sind nur historisch gewachsene Begriffe, heutzutage ist (fast) alles Zweierkomplement. Die Geschichte der beiden Komplemente darzustellen kann ebenfalls nicht Aufgabe dieses Artikels sein, das könnte ich auch nicht schreiben, dazu habe ich zu wenig Ahnung davon.

Mir ist nicht ganz klar, warum du mich jetzt zum Review schicken möchtest; einzelne Aspekte kann man während der Kandidatur abarbeiten, mehr ist hier bisher noch nicht aufgekommen. Insbesondere denke ich, dass das Groß meiner Antwort sich in den drei Artikeln wiederfindet, um die sie sich dreht. Viele Grüße - – — zyranivia 13:17, 27. Jun. 2017 (CEST)

Hm. Dass beim Zweierkomplement im Gegensatz zum Einer-Komplement das Vorzeichen nur indirekt wäre, stimmt so nicht. Auch beim 2-er-Komplement ist das Vorzeichen an einem Bit erkennbar... Aber nicht so wichtig.

Ich hoffe nicht, Dich zu sehr demotiviert zu haben wegen dem späten Zeitpunkt mit meiner Kritik. Ist ein unglücklicher Zufall, dass mir der Artikel erst kürzlich aufgefallen ist. Mittlerweile habe ich ein paar der online verfügbaren Paper überflogen und mir ist zwischenzeitlich auch klar geworden, dass das modulo 255 (bzw. allgemein 2**k-1) offensichtlich Vorteile gegenüber einem modulo 256 hinsichtlich Sensitivität hat. Es steht ja sogar (allerdings an mMn unpassender Stelle), wir Du sagst, eine Begründung im Artikel, diese scheint mir aber nicht zutreffend, zumindest finde ich in dem Paper von Maxino, Koopman 2009 mir eine mehr einleuchtende Begründung. Warum das modulo 255 so gerne als 1-Komplement-Logik aufgefasst bzw. dargestellt wird, ist mir immer noch nicht ganz klar, da keine der heutigen Implementierungen daraus einen Nutzen ziehen kann, aber dazu müsste ich wohl mal das Original-Paper lesen (das ich bisher mir noch nicht versucht habe zu besorgen).

Zur Bewertung: Der Artikel mag Laien ein ganz guten Eindruck vermitteln, um was es bei solchen Prüfsummen-Verfahren geht. Aber einem Entwickler hilft er kaum weiter. Den Beispielcode finde ich auch äußerst unglücklich, da die Bit-Operatoren der Programmiersprache C suggerieren er wäre effizient, was er aber genau nicht ist, denn er verwendet den Modulo-Operator. In der englischsprachigen Wikipedia ist dieser Code zumindest als "straightforward" bezeichnet (im Ggs. zu den folgenden optimierten Varianten). Eine Pseudocode-Darstellung wäre sinnvoller, wenn man auf eine Darstellung einer wirklich optimierten Version verzichtet. Der englischsprachige Artikel ist für Entwickler etwas besser geeignet, aber auch dieser Artikel ist nicht gerade ideal strukturiert, this "experience [actually] isn't unique". Was mich außerdem interessiert hätte, was ich aber bisher noch nicht gefunden habe, ist eine Aufstellung der Parameter und sonstigen Spezifikationen der Fälle, in denen die Fletcher checksum standardisiert verwendet wird. Beispielsweise nimmt sich das letzte optimierte Beispiel in der englischsprachigen WP die Freiheit heraus, statt 0x0000 immer 0xFFFF zu verwenden, was bei dem verwendeten modulo (65535) äquivalent sei. Das kann man so machen, es hat wohl die beim Beispiel dokumentierten Vorteile, aber entspricht das so einem Standard?

Um exzellent zu sein, müsste dieser Artikel zumindest auch Entwicklern irgendetwas bieten. Um lesenswert zu sein, müsste er meiner Meinung nach zumindest seine Unvollständigkeiten klarstellen. Auch würde ich erwarten, dass klar herausgearbeitet wird, warum man in Verbindung mit diesem Algorithmus die 1-Komplement-Logik so eine große Rolle zu spielen scheint. Unbedingt nötig wäre hier die Erklärung der damit verbundenen "end around carry"-Logik, die heute kaum noch einem Entwickler klar sein dürfte und die hier die entscheidende Rolle spielt (die mir auch nicht mehr präsent war, weshalb ich die Zusammenhänge anfangs nicht verstanden habe, s.o.).--Cactus26 (Diskussion) 13:59, 27. Jun. 2017 (CEST)

Ja, bei der Aussage hatte ich einen kurzen gedanklichen Aussetzer, der Rest stimmt ja wieder. Welche Stelle fändest du denn für die Erklärung, weshalb $2^{K}-1$ besser ist, passender?

Ich habe gerade noch mal nachgeschaut, finde aber die einleuchtende Erklärung von Maxino nicht: „We use the one’s complement addition version, which provides better error detection than the two’s complement addition version [29]. We confirmed this experimentally.“ [29] bezieht sich auf Nakassis, der wiederum eine mathematisch komplexere Begründung gibt, die man zumindest meiner Meinung nach sehr gut mit der Primfaktorbegründung zusammenfassen kann. Es gibt noch die Stelle, an der Fletcher’s Checksum mit der Adler-Checksum verglichen wird und das schlechtere Abschneiden letzterer erklärt wird; das findet sich im Artikel wieder: „Obwohl bei Adler-32 die Besetzung von 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.“

Den C-Code durch Pseudocode zu ersetzen, da er Effizienz suggeriert, ist ein sinnvoller Vorschlag; kennst du zufälligerweise eine gängige Notation innerhalb von WP? Zu den Optimierungen im englischen Pendant: Das findet sich nicht in der Literatur wieder, ist also TF. (Ich hoffe, dass ich nicht irgendein Paper übersehen habe.) Die Beleglage dort ist allgemein knapp, ich zweifle die Richtigkeit der Ausführungen nicht an, kann das aber nicht guten Gewissens übernehmen. Ich habe bei meiner Recherche allgemein keine Standards gefunden, Fletcher’s Checksum fristet ein ausgewiesenes Nischendasein.

Ich kann noch schauen, ob ich etwas dazu finde, modulo durch die „end-around carry expression“ zu ersetzen, dies allerdings nicht mehr innerhalb der Kandidaturzeit. Das würde ich dann in den Optimierungsabschnitt einbauen und sollte wie von dir gefordert klarstellen, warum die Einerkomplementlogik immer wieder vorkommt.

Da auf der Rückseite die Diskussion aufkam: Ich kenne mich nicht gut genug mit den Kriterien im Algorithmenbereich aus, um einschätzen zu können, ob ein echter Mehrwert für Entwickler gefordert ist. Ich kann zumindest sagen, dass Cactus’ Anmerkungen grundsätzlich korrekt sind und der Artikel aus dieser Sicht nicht vollständig ist, es leider aber auch nicht werden kann, solange sich nicht ein Paper findet, dass sich genau dieser Themen annimmt.

Mein Vorschlag wäre also, guten Gewissens auszuwerten, und ich treffe mich mit Cactus (und anderen Interessierten) auf der Artikelrückseite wieder - – — zyranivia 17:13, 28. Jun. 2017 (CEST)

 Exzellent Wenn es zu der angesprochenen Lücke kein verwertbares Material gibt, kann dies dem Autor nicht angelastet werden. Ansonsten weist der Artikel ein hohes Niveau auf, was eine Bewertung als exzellent rechtfertigt. --Chewbacca2205 (D) 19:29, 28. Jun. 2017 (CEST)

Ich habe den Artikel gemäß der mittlerweile etwas verstreuten Anmerkungen noch mal überarbeitet. Es findet sich jetzt direkt am Anfang, warum 255 gegenüber 256 besser ist, der C-Code wurde durch Pseudocode ersetzt (dem man gerne noch etwas verschönern kann) und die Sache mit dem Einer- und Zweierkomplement findet sich jetzt an nur einer Stelle in Gesellschaft des end-around carrys. Gerne hätte ich noch eine Erklärung, warum die Begründung für den ersten Punkt „obendrein fragwürdig“ ist. Anmerken möchte ich, dass die Codeschnipsel zum Ersetzen von modulo momentan noch an der Grenze zu TF sind, eine oberflächliche Recherche hat da auch erstmal keine Quelle für ergeben. Mir scheint, als wäre das in C-Programmierer-Kreisen allgemein bekannt (gewesen), mathematisch ist es nicht allzu schwer beweisbar korrekt, deswegen kann man es mMn erstmal so drin lassen. Viele Grüße - – — zyranivia 14:01, 29. Jun. 2017 (CEST)

Schön, dass Du mit meinen Anregungen etwas anfangen kannst (und nicht darauf herumreitest, dass ich der einzige mit diesem Standpunkt bin). Nach diesen Änderungen habe ich gegen eine Auszeichnung nicht mehr einzuwenden, für Exzellenz müsste man, wie gesagt, meiner Meinung nach noch mehr für Entwickler bieten (dann könnte man sich wohl im eine konkrete Implementierung nicht mehr drücken), aber so ist der Artikel eine runde Sache und damit erfüllt er meiner Meinung nach den Lesenswert-Anspruch.

Mir hätte gereicht, wenn Du beim C-Code auf den Sachverhalt hingewiesen hättest, dass es zwar C-Notation ist, aber dennoch als Pseudocode zu verstehen ist. Ich tue mich auch sehr schwer mit einer vernünftigen Psudocode-Notation. Aber so wie es jetzt ist versteht man den Code und das ist die Hauptsache.

Das "zudem fragwürdig" kam daher, dass ich an allen anderen Stellen eigentlich eine andere Begründung gefunden habe und die Primfaktoren-Begründung nirgendwo. Vielleicht lässt Du mir mal Deine Quelle zukommen, ich schicke Dir meine Mail-Adresse. Die Begründung, die ich überall finde, ist dass 1-Komplement-Logik verhindert, dass das MSB (most signifant bit) rausgeschoben wird und somit grundsätzlich sich in einer Prüfsumme nicht auswirkt (siehe z.B. https://users.ece.cmu.edu/~koopman/thesis/maxino_ms.pdf S. 10. Es gibt dann noch ein häufig genanntes Argument, und das ist die "Endianness-Invarianz" der 1-complement-Arithmetik (siehe hier, ganz unten. Ob letzteres wirklich so bedeutend ist, weiß ich auch nicht, jedenfalls reicht eine Begründung aus und wenn es für die Primfaktoren-Begründung eine Quelle gibt, dann ok, sonst könnte man argumentieren, dass die 1-Komplement Logik verhindert, dass Fehler in den signifikantesten Bit sonst häufig unerkannt bleiben (ich denke, Fletcher relativiert den Nachteil gegenüber einer einzelnen Prüfsumme etwas, da er ja aus 2 Prüfsummen besteht).

Was aus den Links ersichtlich wird und was ich bei meinen Recherchen auch (erstaunt) erkannt habe, ist dass die 1-Komplement-Logik schon vor Fletcher einen Bezug zu Prüfsummen hatte. Interessant ist, und das habe ich bei dieser Sache gelernt, ist das diese anachronistische Arithmetik bei Prüfsummen überlebt zu haben scheint, und das steht fast schon zitierfähig hier auf S. 33: [1].

Ich werde mich (wenn Du magst) nochmal genauer mit dem Artikel auseinandersetzen, weiß noch nicht genau, ob ich heute nochmal Zeit dazu finde. Für die Imitation des "end araound carry" gibt es sicher eine Quelle, das ist keine TF.--Cactus26 (Diskussion) 08:30, 30. Jun. 2017 (CEST)

Nachtrag: Du hattest geschrieben: "Bei Übertragsaddition garantiert erst eine weitere Modulo-Iteration am Ende des Algorithmus, dass sich die Summe im gewünschten Intervall befindet.". Ich vermute, dies hast Du der optimierten Version im engl. Artikel entnommen ([2]). Ich bin recht sicher, dass das nur aufgrund der Optimierung nötig ist, denn dieser macht den "end around carry" ja nicht nach jedem Schritt, sondern sammelt die Überträge ja, solange sie im höherwertigen Halbwort Platz haben. Deshalb habe ich den Satz weggelassen, der wäre erst nötig, wenn man einen solchen optimierten Algorithmus darstellen würde.--Cactus26 (Diskussion) 08:55, 30. Jun. 2017 (CEST)

Ich sehe den Anspruch, Code einer optimierten Variante für Exzellenz zu fordern, auch wenn ich der Meinung bin, dass der Artikel alles nötige enthält, um eine schnelle Programmierung zu ermöglichen. Der Code selbst ist mit der mir vorliegenden Literatur einfach nicht zu decken, selbst das englische Pendant ist ja nicht komplett optimiert, zumindest taucht in Papern Loop unrolling immer wieder als wichtiger Zeitfaktor auf, dort aber gar nicht.

Sobald ich deine Emailadresse habe, lasse ich dir das gerne zukommen. Ich finde es interessant, dass dieses Argument von Maxino in ihrem späterem Paper nicht auftaucht und sie nur auf Nakassis verweist, das hat sicherlich auch Gründe … Tatsächlich erwähnt auch Fletcher in einem Nebensatz, dass die Teilbarkeit von 255 durch 3 bedeutet, dass eine dritte Summe für Fletcher-16 profitabler ist als für andere $K$.

Ich suche noch eine Quelle, die diese Imitation klipp und klar erwähnt, aber mit der Zeit wird man schon fündig werden. Die weitere Modulo-Iteration ist bei einer nicht optimierten Variante tatsächlich überflüssig, der Absatz beginnt jedoch mit „[z]usätzlich“, also könnte man es schon so verstehen, dass die erste Beschleunigung davor auch beachtet wird. Schwierig.

Vielen Dank für deine Anmerkungen wie Bearbeitungen und ich würde mich freuen, wenn du dich – sobald du die Zeit findest – noch etwas mehr mit dem Artikel befasst, der kann dadurch nur gewinnen. Viele Grüße - – — zyranivia 10:42, 30. Jun. 2017 (CEST)

PS: An sich müsste man ja jetzt daran gehen, Prüfsumme etwas aufzupolieren, neverending story …

Stimmt. Der Gedanke kam mir auch schon...

Kurz noch zu meinem letzten Bearbeitungskommentar , der völlig misslungen ist. Ich meine nicht 1-Komplement- bzw. 2-Kompement-Variante sondern -Hardware. An dem von mir oben hineinkopierten RFC-Auszug ([3]) sieht man ja, wie einfach die Sache auf einer 1-Komplement-Hardware wäre. Man würde einfach addieren, addieren, addieren, sonst nichts. Voraussetzung ist ein "8-bit accumulator", der exakt dem für die Summen verwendeten Datentyp entspricht (hier soll ein Fletcher-16 berechnet werden, obwohl das hier "8-bit Fletcher Checksum Algorithm" genannt wird).

Ich vermute, dass explizites Loop unrolling zumindest in C heute kein Thema mehr ist, da man das dem Compiler (bei entsprechend gesetzten Optimierungsoptionen) überlassen kann. Es müsste ja kein perfekt optimiertes Beispiel sein, nur vielleicht eins, was als Ausgangsbasis taugt. Ich finde das Beispiel im englischsprachigen Artikel auch nicht besonders glücklich, da es wirklich sehr schwer zu verstehen ist und dann noch die (mehr oder weniger empirisch ermittelte, siehe Disk.) Konstante 359 enthält. Aber mein Gefühl ist schon, dass man den Artikel noch ganz gut weiterbringen kann, und wenn er jetzt schon exzellent wäre, worauf solle man dann hinarbeiten? ;-)

Aber didaktisch ist er in seiner jetzigen Version bereits deutlich besser als der englischsprachige Artikel.

--Cactus26 (Diskussion) 12:28, 30. Jun. 2017 (CEST)

Mit sechs Stimmen Exzellent und einer Stimme Lesenswert wird der Artikel in dieser Version als Exzellent ausgezeichnet. Begründung: Die notwendige Anzahl an Stimmen für eine Auszeichnung als Exzellent wurde erreicht, Gründe die einer Auszeichnung zwingend entgegenstehen würden (z. B. gravierende inhaltliche Fehler) wurden nicht genannt. Die noch ausstehenden Kritikpunkte sollten nach Möglichkeit natürlich noch umgesetzt werden, die Diskussion hierzu aber auf der Artikeldiskussionsseite fortgeführt werden. Tönjes 09:28, 1. Jul. 2017 (CEST)

Simpel

... "simple Berechnungen" scheint einzigartig zu sein. Gibt es dafür eine Alternative? Etwa: einer simplen Summe => einfache (Auf)Summierung - in der Art? GEEZER ^{… nil nisi bene} 07:41, 4. Aug. 2017 (CEST)

Habe mal einen Formulierungsversuch gemacht, "Berechnungen" passt bei vertikaler Redundanzprüfung auch nicht so ganz. Kannst Du meine Änderung nochmals grammatikalisch prüfen, mein Grammatik-Modul scheint heute nicht voll funktionsfähig zu sein... --Cactus26 (Diskussion) 09:42, 4. Aug. 2017 (CEST)

Einwandfrei! :-) GEEZER ^{… nil nisi bene} 10:13, 4. Aug. 2017 (CEST)

2 hoch N - 1 ?

... weil 2 K − 1 {\displaystyle 2^{K}-1} {\displaystyle 2^{K}-1} vergleichbar groß ist, im Gegensatz zu 2 K {\displaystyle 2^{K}} {\displaystyle 2^{K}} jedoch nicht durch 2 – die Basis des Binärsystems – teilbar.[3]

Das ist keine Begründung. Wo ist der Vorteil? --46.232.229.52 17:21, 30. Jun. 2020 (CEST)

Diese Diskussion kam auch schon in der Kandidatur auf, für einen ersten Überblick siehe dort (ab Auftreten von Cactus26). Belegt ist die Aussage mit Anastase Nakassis: Fletcher’s Error Detection Algorithm: How to implement it efficiently and how to avoid the most common pitfalls. 1988, S. 71f., siehe dort für eine recht ausführliche Beschreibung der Vorteile von $2^{K}-1$ gegenüber $2^{K}$. (Ich kann dir eine PDF des Artikels zukommen lassen, wenn du mir einen Kommunikationskanal nennst.) Die Argumentation ist nicht-trivial und daher meines Erachtens nicht geeignet, vollständig im Artikel aufgeführt zu werden. Ein konkreter Aspekt wird später noch mal im Artikel aufgegriffen:

„Für Nachrichten bis zu einer Länge von $K\cdot M=K\cdot (2^{K}-1)$ Bit besitzt das Verfahren eine Hamming-Distanz von $h=3$, für längere Nachrichten ist $h=2$. Fletcher-16 erkennt also ab Nachrichtenlänge von 2.056 Bit nicht mehr alle Zwei-Bit-Fehler, 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 $M=256$, da hier der Abstand kleinergleich 16 Bit sein muss.“

Ich bin für Vorschläge offen, die Begründung auszuweiten, solange es kein Exkurs wird, der den Lesefluss stark stört. Danke für dein Interesse und viele Grüße - – — zyranivia 23:09, 30. Jun. 2020 (CEST)