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

Формальные математические модели не охватывают все детали того феномена, который описывают, они и не должны этого делать. Например, существуют вопросы о случайности – на них теория вероятностей не дает ответа. В понимании некоторых людей проблемы, остающиеся вне досягаемости математики, представляют собой самые интересные вопросы. Но в наши дни было бы ошибкой размышлять о случае, не опираясь на теорию вероятностей. Если не верите мне, спросите Джеймса Харви. Или, что еще лучше, спросите об этом у людей, чьи деньги он выиграл.

Появится ли когда-либо математическая теория сознания? Общества? Эстетики? Кто-то наверняка пытается создать такие теории, но пока безуспешно. Заявления такого рода должно каждый раз подвергать сомнению, полагаясь на интуицию. Но также следует помнить, что в конечном счете они могут правильно интерпретировать некоторые вещи.

На первый взгляд код с исправлением ошибок не кажется революционным математическим методом. Ведь мы всегда повторяем сказанное, когда находимся в шумном месте, – и таким образом решаем проблему! Но у данного решения есть своя цена. Если вы будете повторять каждый бит информации три раза, для передачи сообщения понадобится в три раза больше времени. Вряд ли это послужит препятствием на громогласной вечеринке, но может стать настоящей проблемой, если вам необходимо, чтобы спутник включил правый двигатель в данную секунду. В своей работе, положившей начало теории информации, Шеннон описал негативный побочный эффект, с которым инженеры борются до сих пор: чем более устойчивым к помехам вы хотите сделать свой сигнал, тем медленнее будут передаваться биты. Присутствие шума ограничивает длину сообщения, которое ваш канал связи может безопасно передать за определенное количество времени. Шеннон обозначил этот предел термином пропускная способность канала. Подобно тому как труба пропускает только определенное количество воды, канал связи также передает только определенный объем информации.

Однако для исправления ошибок не обязательно сокращать пропускную способность канала связи, как того требует протокол «повторить три раза». Шеннон знал, что их можно исправить более эффективно, поскольку Ричард Хэмминг, его коллега по Bell Labs, уже понял, как решить данную проблему.

У Хэмминга, молодого ветерана Манхэттенского проекта, в 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

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

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