Math
Код, который сам себя чинит
Шестнадцать битов в квадрате, одиннадцать из них — сообщение: щёлкни по одному, и четыре лампы проверок назовут его адрес, а блок починит себя сам. Две ошибки блок поймает, но исправить не сможет; три — и он солжёт уверенно. Каждое утверждение исчерпывающее: все 32 768 одиночных ошибок найдены, все 245 760 двойных пойманы, все тройные исправлены неверно.
Что происходит
Шестнадцать битов, разложенных четыре на четыре. Одиннадцать несут сообщение; четыре — проверки чётности, стоящие на степенях двойки (1, 2, 4, 8), и пятая на позиции 0 проверяет весь квадрат. Каждая проверка смотрит ровно половину блока: проверка 1 — все нечётные индексы, проверка 2 — индексы 2, 3, 6, 7, 10, 11, 14, 15, и так далее. Поскольку каждый индекс принадлежит своему сочетанию проверок, четыре ответа вместе — не сигнал тревоги, а АДРЕС: сложи по исключающему ИЛИ индексы всех единиц, и получишь число, написанное под неверной плиткой. Щёлкни по любой плитке — она перевернётся, и лампы назовут её. Щёлкни по второй — блок всё ещё знает, что что-то не так: шестнадцатый бит, проверяющий весь квадрат, и отделяет «исправить одну ошибку» от «исправить одну и знать про две». Щёлкни по третьей — и код солжёт: назовёт плитку с полной уверенностью и вернёт неверное сообщение. Расстояние четыре покупает одно исправление и два обнаружения, и ничего сверх. Без шестнадцатого бита код СОВЕРШЕНЕН в техническом смысле: 2048 кодовых слов, у каждого пятнадцать соседей в одном перевороте, и 2048 × 16 = 32 768 = 2¹⁵ ровно — шары радиуса один замощают пространство без остатка. Эта арифметика работает в ECC-памяти, в каждом QR-коде и на поверхности любого оптического диска; поэтому поцарапанный компакт-диск всё ещё играет.
Уравнения модуля
Уравнения синдром: s = XOR индексов всех установленных битов; s = 0 означает, что четыре проверки согласны, а s ≠ 0 И ЕСТЬ адрес неверного бита проверки: проверка p следит за каждым индексом i, для которого (i AND 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 % - более длинные блоки дают более дешёвую страховку и сильнее проигрывают при второй ошибке
