Джордан Элленберг - Как не ошибаться. Сила математического мышления

Наверное, сейчас вы подумали, что нам просто повезло. Разве загадочное сообщение не могло быть близким к двум разным кодовым словам? В таком случае мы не имели бы возможности дать однозначную оценку. Но этого никогда не произойдет, и вот почему. Посмотрите еще раз на линии плоскости Фано:

124

135

167

257

347

236

456

Как бы вы описали данную геометрию компьютеру? Компьютеры любят, чтобы с ними разговаривали в нулях и единицах, поэтому нужно записать каждую линию в виде последовательности цифр 0 и 1, где 0 на позиции n означает «точка n находится на линии», а 1 на позиции n означает «точка n не находится на линии». Таким образом, первая линия, 124, будет представлена в таком виде:

0010111

а вторая, 135, – в таком:

0101011

Обратите внимание, что обе строки символов представляют собой кодовые слова из кода Хэмминга. В действительности семь ненулевых кодовых слов из кода Хэмминга в точности соответствуют семи линиям плоскости Фано. Код Хэмминга и плоскость Фано (а также, если уж на то пошло, оптимальная совокупность билетов для трансильванской лотереи) – один и тот же математический объект, но в разных нарядах!

Это и есть тайная геометрия кода Хэмминга. Кодовое слово представляет собой совокупность трех точек на плоскости Фано, образующих прямую линию. Изменение одного бита в строке равносильно прибавлению или исключению одной точки. Следовательно, если исходное кодовое слово было не 0000000, искаженное сообщение, которое вы получите, соответствует множеству из двух или из четырех точек [225]. Если вы получите множество из двух точек, вам известно, как найти недостающую точку: это просто третья точка на единственной прямой, соединяющей две полученные вами точки. Что если вы получите множество из четырех точек, имеющее вид «прямая плюс одна дополнительная точка»? В таком случае вы можете сделать вывод, что правильное сообщение состоит из тех трех точек в вашем множестве, которые образуют прямую линию. Здесь есть одна тонкость: откуда вам известно, что существует только один способ выбора такого множества из трех точек? Давайте обозначим точки символами A, B, C и D . Если точки A, B и C лежат на прямой линии, тогда A, B и C должны быть тем самым множеством точек, которое намеревался передать вам отправитель. Но что если A, C и D также расположены на одной прямой? Не беспокойтесь: это невозможно, поскольку прямая, содержащая точки A, B и C , а также прямая, содержащая точки A, С и D , имели бы две общие точки – А и С . Однако две прямые линии могут пересекаться только в одной очке – таково правило [226]. Другими словами, благодаря аксиомам геометрии код Хэмминга имеет такое же магическое свойство по исправлению ошибок, что и метод «повторить три раза»: если в процессе передачи в сообщении будет искажен один бит, получатель может вычислить, какое сообщение намеревался передать отправитель. Однако вместо увеличения времени передачи сообщения в три раза ваш новый усовершенствованный код позволяет отправлять семь бит на каждые три бита исходного сообщения, что обеспечивает более эффективный коэффициент 2,33.

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