Math
Ein Code, der sich selbst repariert
Sechzehn Bits in einem Quadrat, elf davon eine Nachricht: Klicken Sie auf eines, und die vier Prüflampen buchstabieren seine Adresse, und der Block setzt sich selbst instand. Zwei Fehler werden erkannt, aber nicht repariert; bei drei lügt der Block überzeugt. Jede Aussage ist erschöpfend geprüft: alle 32 768 Einzelfehler lokalisiert, alle 245 760 Doppelfehler erkannt, jeder Dreifachfehler falsch korrigiert.
Was passiert
Sechzehn Bits, vier mal vier gelegt. Elf tragen eine Nachricht; vier sind Paritätsprüfungen auf den Zweierpotenzen (1, 2, 4, 8), und eine fünfte an Position 0 prüft das ganze Quadrat. Jede Prüfung beobachtet genau die Hälfte des Blocks. Da jeder Index zu einer anderen Kombination von Prüfungen gehört, sind die vier Antworten zusammen kein Alarm, sondern eine ADRESSE: das Exklusiv-Oder der Indizes aller gesetzten Bits ist die Zahl unter der falschen Kachel. Klicken Sie eine zweite an, und der Block weiß immer noch, dass etwas nicht stimmt — das sechzehnte Bit trennt «einen Fehler korrigieren» von «einen korrigieren und von zweien wissen». Bei einem dritten lügt der Code: Er nennt eine Kachel mit voller Überzeugung und liefert die falsche Nachricht. Distanz vier kauft eine Reparatur und zwei Erkennungen, mehr nicht. Ohne das sechzehnte Bit ist der Code PERFEKT im technischen Sinn: 2048 Codewörter, jedes mit fünfzehn Nachbarn, und 2048 × 16 = 32 768 = 2¹⁵ genau. Diese Arithmetik steckt im ECC-Speicher, in jedem QR-Code und auf jeder optischen Disc; darum spielt eine zerkratzte CD noch.
Gleichungen des Moduls
Gleichungen Syndrom: s = XOR der Indizes aller gesetzten Bits; s = 0 bedeutet, dass die vier Prüfungen übereinstimmen, und s ≠ 0 IST die Adresse des falschen Bits Prüfungen: Prüfung p überwacht jeden Index i mit (i UND p) ≠ 0; p = 1, 2, 4, 8, und Position 0 prüft das ganze Quadrat Urteil: s = 0 und Parität gerade → ganz; Parität ungerade → ein Fehler bei s (s = 0 bedeutet Bit 0 selbst); s ≠ 0 und Parität gerade → zwei Fehler, erkannt und nicht korrigierbar perfekter Code: Hamming(15,11) hat 2^11 = 2048 Codewörter, jedes mit 15 Nachbarn, die einen Bitwechsel entfernt sind; 2048 × 16 = 32 768 = 2^15 exakt - die Kugeln vom Radius eins pflastern den Raum ohne Rest Abstand: d = 3 für Hamming(15,11), d = 4 mit dem Bit des ganzen Quadrats; das Korrigieren von t Fehlern braucht d ≥ 2t + 1, das Erkennen von t braucht d ≥ t + 1 vollständig: 32 768 Einzelbitfälle, 0 falsch lokalisiert; 245 760 Doppelbitfälle, 0 übersehen und 0 falsch korrigiert; 35 840 Dreibitfälle, alle 35 840 "korrigiert" und damit falsch Rate: 11 Nachrichtenbits pro 16 gesendete Bits = 68.75 %; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - längere Blöcke sind die günstigere Versicherung und verlieren mehr durch einen zweiten Fehler
