Math
Код, що лагодить сам себе
Шістнадцять бітів у квадраті, одинадцять із них — повідомлення: клацни по одному, і чотири лампи перевірок назвуть його адресу, а блок полагодить себе сам. Дві помилки блок упіймає, але виправити не зможе; три — і він збреше впевнено. Кожне твердження вичерпне: усі 32 768 одиночних помилок знайдено, усі 245 760 подвійних упіймано, усі потрійні виправлено хибно.
Що відбувається
Шістнадцять бітів, викладених чотири на чотири. Одинадцять несуть повідомлення; чотири — перевірки парності на степенях двійки (1, 2, 4, 8), а п’ята на позиції 0 перевіряє весь квадрат. Кожна перевірка дивиться рівно половину блоку. Оскільки кожен індекс належить до свого поєднання перевірок, чотири відповіді разом — не сигнал тривоги, а АДРЕСА: додай за виключним АБО індекси всіх одиниць, і отримаєш число, написане під хибною плиткою. Клацни по другій — блок усе ще знає, що щось не так: шістнадцятий біт відділяє «виправити одну помилку» від «виправити одну і знати про дві». На третій код бреше: називає плитку з повною впевненістю і повертає хибне повідомлення. Відстань чотири купує одне виправлення і два виявлення, і нічого понад. Без шістнадцятого біта код ДОСКОНАЛИЙ у технічному сенсі: 2048 кодових слів, у кожного п’ятнадцять сусідів, і 2048 × 16 = 32 768 = 2¹⁵ рівно. Ця арифметика працює в ECC-пам’яті, у кожному QR-коді й на поверхні будь-якого оптичного диска; тому подряпаний компакт-диск усе ще грає.
Рівняння модуля
Рівняння синдром: s = XOR індексів усіх встановлених бітів; s = 0 означає, що чотири перевірки узгоджені, а s ≠ 0 і є адресою хибного біта перевірки: перевірка p стежить за кожним індексом i з (i І p) ≠ 0; p = 1, 2, 4, 8, а позиція 0 перевіряє весь квадрат вердикт: s = 0 і парність парна → ціле; парність непарна → одна помилка в s (s = 0 означає сам біт 0); s ≠ 0 і парність парна → дві помилки, виявлені й невиправні досконалий код: Hamming(15,11) має 2^11 = 2048 кодових слів, кожне з 15 сусідами на відстані одного переключення; 2048 × 16 = 32 768 = 2^15 точно - сфери радіуса один замощують простір, не залишаючи нічого відстань: d = 3 для Hamming(15,11), d = 4 з бітом усього квадрата; виправлення t помилок потребує d ≥ 2t + 1, виявлення t потребує d ≥ t + 1 вичерпно: 32 768 однобітових випадків, 0 хибно локалізованих; 245 760 двобітових випадків, 0 пропущених і 0 хибно виправлених; 35 840 трибітових випадків, усі 35 840 "виправлено" хибно швидкість коду: 11 бітів повідомлення на 16 надісланих = 68.75 %; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - довші блоки є дешевшим страхуванням і більше втрачають через другу помилку
