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

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

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

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

Однако для исправления ошибок не обязательно сокращать пропускную способность канала связи, как того требует протокол «повторить три раза». Шеннон знал, что их можно исправить более эффективно, поскольку Ричард Хэмминг, его коллега по 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.