Как не ошибаться. Сила математического мышления

У Хэмминга, молодого ветерана Манхэттенского проекта, в Bell Labs был доступ к десятитонной релейной вычислительной машине Model V, однако уровень его допуска позволял ему работать с этой машиной только по выходным{191}. Проблема заключалась в том, что любая механическая ошибка могла остановить процесс вычислений, и никто не мог снова запустить машину до утра понедельника. Это раздражало. А раздражение, как известно, – один из величайших стимулов технического прогресса. Хэмминг подумал, как было бы отлично, если машина смогла бы исправлять собственные ошибки и продолжать работать. В итоге он написал программу. Данные, которые вводятся в машину, можно представить в виде нулей и единиц, точно так же как и при передаче сообщений на спутник; с точки зрения математики не имеет значения, что представляют собой эти цифры: биты в цифровом потоке, состояние электрического реле или отверстия на перфоленте – в то время самый современный интерфейс передачи данных.

Первый шаг Хэмминга состоял в разбиении сообщения на блоки, состоящие из трех символов:

111 010 101…

Код Хэмминга[224] – правило, в соответствии с которым каждый блок из трех цифр преобразуется в последовательность из семи цифр. Вот таблица кодирования:

000 → 0000000

001 → 0010111

010 → 0101011

011 → 0111100

101 → 1011010

110 → 1100110

100 → 1001101

111 → 1110001

Таким образом, кодированное сообщение будет выглядеть так:

1110001 0101011 1011010…

Перечисленные выше блоки из семи бит называются кодовыми словами. Эти восемь кодовых слов представляют собой единственные восемь блоков, которые разрешает данный код; если получатель видит что угодно другое, значит, что-то наверняка пошло не так. Предположим, вы получили блок 1010001. Вы знаете, что он не может быть правильным, потому что 1010001 – не кодовое слово. Более того, полученное вами сообщение отличается от кодового слова 1110001 всего на одну позицию. Другого кодового слова, которое было бы столь близким к искаженному сообщению, не существует. Следовательно, вы можете с довольно высокой степенью уверенности предположить, что кодовое слово, которое намеревался передать отправитель, – 1110001, а это означает, что соответствующий блок из трех цифр в исходном сообщении был 111.

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

124

135

167

257

347

236

456

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

0010111

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

0101011

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