Math
Kod, który sam się naprawia
Szesnaście bitów w kwadracie, jedenaście z nich to wiadomość: kliknij jeden, a cztery lampki kontrolne przeliterują jego adres, i blok sam się naprawi. Dwa błędy zostaną wykryte, ale nie naprawione; przy trzech blok kłamie z przekonaniem. Każde twierdzenie jest wyczerpujące: wszystkie 32 768 błędów pojedynczych zlokalizowane, wszystkie 245 760 podwójnych wykryte, każdy potrójny źle poprawiony.
Co się dzieje
Szesnaście bitów ułożonych cztery na cztery. Jedenaście niesie wiadomość; cztery to kontrole parzystości na potęgach dwójki (1, 2, 4, 8), a piąta na pozycji 0 sprawdza cały kwadrat. Każda kontrola obserwuje dokładnie połowę bloku. Ponieważ każdy indeks należy do innej kombinacji kontroli, cztery odpowiedzi razem to nie alarm, lecz ADRES: różnica symetryczna indeksów wszystkich zapalonych bitów daje liczbę zapisaną pod błędnym kafelkiem. Kliknij drugi, a blok wciąż wie, że coś jest nie tak — szesnasty bit oddziela «poprawić jeden błąd» od «poprawić jeden i wiedzieć, że są dwa». Przy trzecim kod kłamie: wskazuje kafelek z pełnym przekonaniem i zwraca złą wiadomość. Odległość cztery kupuje jedną naprawę i dwa wykrycia, nic więcej. Bez tego szesnastego bitu kod jest DOSKONAŁY w sensie technicznym: 2048 słów kodowych, każde z piętnastoma sąsiadami, i 2048 × 16 = 32 768 = 2¹⁵ dokładnie. To arytmetyka pamięci ECC, każdego kodu QR i każdej płyty optycznej; dlatego porysowana płyta wciąż gra.
Równania modułu
Równania syndrom: s = XOR indeksów wszystkich ustawionych bitów; s = 0 oznacza, że cztery kontrole się zgadzają, a s ≠ 0 JEST adresem błędnego bitu kontrole: kontrola p pilnuje każdego indeksu i, dla którego (i AND p) ≠ 0; p = 1, 2, 4, 8, a pozycja 0 kontroluje cały kwadrat werdykt: s = 0 i parzystość parzysta → całość; parzystość nieparzysta → jeden błąd w s (s = 0 oznacza sam bit 0); s ≠ 0 i parzystość parzysta → dwa błędy, wykryte i niemożliwe do naprawienia kod doskonały: Hamming(15,11) ma 2^11 = 2048 słów kodowych, każde z 15 sąsiadami oddalonymi o jedno odwrócenie bitu; 2048 × 16 = 32 768 = 2^15 dokładnie - kule o promieniu jeden pokrywają przestrzeń bez żadnej reszty odległość: d = 3 dla Hamming(15,11), d = 4 z bitem całego kwadratu; poprawianie t błędów wymaga d ≥ 2t + 1, wykrywanie t wymaga d ≥ t + 1 pełne sprawdzenie: 32 768 przypadków pojedynczego bitu, 0 błędnie zlokalizowanych; 245 760 przypadków dwóch bitów, 0 pominiętych i 0 błędnie poprawionych; 35 840 przypadków trzech bitów, wszystkie 35 840 "poprawione" błędnie sprawność: 11 bitów wiadomości na 16 wysłanych = 68.75 %; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - dłuższe bloki to tańsze ubezpieczenie, ale więcej tracą przy drugim błędzie
