Джордан Элленберг

Логика формирует узкий канал, по которому протекает многократно усиленная интуиция.

Открытие кодов с исправлением ошибок, как первых кодов Хэмминга, так и разработанных впоследствии более эффективных кодов, преобразило проектирование информационных систем. Больше не требовалось создавать системы с двойной проверкой, нуждающиеся в столь сильной защите – защите, которая полностью исключала бы возможность ошибок. После открытий Хэмминга и Шеннона было достаточно сделать ошибки просто редкими, чтобы гибкость кода с исправлением позволяла нейтрализовать любые искажения. В настоящее время коды с исправлением ошибок используются в тех случаях, когда необходимо обеспечить быструю и надежную передачу данных. Орбитальный модуль Mariner 9 отправлял снимки поверхности Марса на Землю с использованием одного из таких кодов, кода Адамара. Компакт-диски кодируются с помощью кода Рида – Соломона – именно поэтому они звучат идеально, даже если их поцарапать. (Читатели, родившиеся после 1990 года и не знающие, что такое компакт-диски, могут просто вспомнить о картах флеш-памяти, в которых среди прочего используется код Боуза – Чоудхури – Хоквингема, чтобы предотвратить нарушение целостности данных.) Код вашего банка шифруется с помощью простого кода, который называется «контрольная сумма». Это не код с исправлением ошибок, а просто код с обнаружением ошибок, подобный протоколу «повторить каждый бит дважды». Если вы напечатаете одну цифру неправильно, компьютер, выполняющий перевод, может не понять, какое число вы на самом деле имели в виду, но он хотя бы определит, что что-то не так, и не отправит ваши деньги не в тот банк.

Для того чтобы код был кодом с исправлением ошибок, ни одна строка (ни одна точка, если серьезно относиться к этой аналогии) не может находиться на расстоянии 1 от двух разных кодовых слов; другими словами, требуется, чтобы две сферы Хэмминга с соответствующими кодовыми словами в центре не имели общих точек.

Таким образом, задача конструирования кодов с исправлением ошибок имеет такую же структуру, что и классическая геометрическая задача про упаковку сфер: каким образом разместить множество сфер одинакового размера в небольшом пространстве как можно плотнее, при условии что любые две сферы никогда не пересекутся? Проще говоря, сколько апельсинов можно уложить в ящик?