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

Как Шеннон сконструировал свои безупречные коды? На самом деле ответ очень прост: он этого не делал. Когда мы встречаем такую сложную конструкцию, как код Хэмминга, то, разумеется, склонны думать, будто код с исправлением ошибок представляет собой некий особый код, который сначала разрабатывают, затем вносят в него изменения, после чего пишут его снова – и так до тех пор, пока каждая пара кодовых слов не окажется осторожно разделенной, но при этом любые другие два кодовых слова не будут находиться слишком близко друг к другу. Гениальность Шеннона состояла в том, что он понял всю необоснованность подобных представлений. В кодах с исправлением ошибок нет ничего особенного. Шеннон доказал – это было не сложно, как только он понял, что именно нужно доказывать, – что почти все наборы кодовых слов обладают свойством исправления ошибок. Другими словами: совершенно случайный код, не имеющий никакой структуры, с очень большой вероятностью является кодом с исправлением ошибок.

Это было поразительное открытие, если не сказать больше. Представьте себе, что вам дали задание построить аппарат на воздушной подушке. Вряд ли вы начнете с того, что в беспорядке разбросаете на земле кучу резиновых трубок и деталей двигателя, рассчитывая, что то, что получилось, полетит.

Хэмминг в 1986 году посвятил Шеннону почти восторженные слова – даже сорок лет спустя его открытие производило на математиков огромное впечатление:

Храбрость – качество, которым Шеннон владел в полной мере. Достаточно вспомнить о его главной теореме. Он хочет создать метод кодирования, но не знает, что делать, поэтому создает случайный код. Затем он заходит в тупик. А после задает невероятный вопрос: «Что сделал бы обычный случайный код?» Позже он доказывает, что обычный код вполне хорош, а значит, должен существовать как минимум один хороший код. Кто кроме человека беспредельной храбрости посмел бы размышлять о чем-то подобном? Это и есть черта великих ученых: им свойственна храбрость. Они идут вперед при невообразимых обстоятельствах; они никогда не прекращают мыслить.

Но если случайный код с большой вероятностью может быть кодом с исправлением ошибок, в чем смысл кода Хэмминга? Почему просто не выбрать кодовые слова совершенно случайным образом, опираясь на знание – согласно теореме Шеннона, – что этот код, по всей вероятности, будет исправлять ошибки? Вот одна из проблем этого плана. Недостаточно, чтобы код в принципе был способен исправлять ошибки; он должен быть применимым на практике. Если в одном из кодов Шеннона используются блоки размером 50, тогда количество кодовых слов равно количеству строк из 0–1 длиной 50 бит, что составляет 2 в степени 50, немногим более квадриллиона. Большое число. Ваш космический корабль получает сигнал, который предположительно является одним из квадриллиона кодовых слов или как минимум близок к одному из них. Но какое именно кодовое слово? Не перебирать же квадриллион кодовых слов по одному! Снова происходит комбинаторный взрыв, и в данном контексте это влечет за собой еще один компромисс. Коды со сложной структурой, такие как коды Хэмминга, в большинстве случаев легко декодировать. Однако сугубо специальные коды оказались не столь эффективными, как совершенно случайные коды, которые изучал Шеннон! За прошедшие с тех пор десятилетия, вплоть до настоящего времени, математики пытались одолеть эту границу между структурой и случайностью, кропотливо работая над созданием оптимальных кодов – достаточно случайных, чтобы быть быстрыми, и достаточно структурированных, чтобы поддаваться декодированию.

Код Хэмминга прекрасно подходит для трансильванской лотереи, но он неэффективен в случае лотереи Cash WinFall. В трансильванской лотерее всего семь чисел, в лотерее штата Массачусетс их сорок шесть. Следовательно, нам понадобится код побольше. Лучший код, который мне удалось найти для этой цели, открыл в 1976 году Ральф Деннистон из Лестерского университета{199}. И это очень красивый код.

Деннистон составил список из 285 384 комбинаций шести чисел из сорока восьми. Этот список начинается так:

1 2 48 3 4 8

2 3 48 4 5 9

1 2 48 3 6 32