Как не ошибаться - Страница 109

109

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

...

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

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

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

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

1 2 48 3 4 8

2 3 48 4 5 9

1 2 48 3 6 32

В первых двух билетах четыре общие числа: 2, 3, 4 и 48. Однако (в этом и заключается поразительная особенность системы Деннистона) среди всех этих 285 384 лотерейных билетов вы не найдете пяти совпадающих чисел. Систему Деннистона можно перевести в код, как мы сделали это с плоскостью Фано, – заменив числа каждого билета строкой из 48 единиц и нулей, в которой 0 стоит на позициях, соответствующих числам вашего билета, а 1 – на позициях, соответствующих числам, которых в билете нет. Таким образом, первый билет из приведенных выше можно представить в виде такого кодового слова:

000011101111111111111111111111111111111111111110

Проверьте сами: тот факт, что среди всех этих лотерейных билетов нет двух билетов с пятью совпадающими числами из шести, означает, что этот код, подобно коду Хэмминга, не содержит два кодовых слова, разделенных расстоянием Хэмминга, меньшим четырех.

Это можно сформулировать так: каждая комбинация из пяти чисел присутствует в максимум одном из билетов Деннистона. На самом деле все даже лучше: по существу, каждая комбинация из пяти чисел присутствует ровно в одном билете.

Можете представить, какой тщательности требует выбор комбинаций чисел, входящих в список Деннистона? Деннистон включил в свою работу компьютерную программу на языке алгол, которая проверяет список на предмет того, действительно ли он обладает заявленным магическим свойством – для 1970-х годов жест довольно прогрессивный. Тем не менее Деннистон настаивает, что роль компьютера в этой работе следует расценивать как вторичную по отношению к его собственной: «На самом деле я хотел бы заявить, что все объявленные здесь результаты были получены без использования компьютера, хотя я допускаю, что их можно проверить с помощью компьютеров».

В лотерее Cash WinFall всего сорок шесть чисел, поэтому, чтобы сыграть в нее по методу Деннистона, придется немного нарушить красивую симметрию его системы, выбросив из его списка все билеты с числами 47 и 48. После этого у вас все еще останется 217 833 лотерейных билета. Предположим, вы достанете из тайника 435 666 долларов и решите поиграть в числа. Что произойдет?

В розыгрыше лотереи выпадает по шесть чисел – скажем, 4, 7, 10, 11, 34 и 46. Если произойдет маловероятное событие, эти числа совпадут с числами в одном из ваших лотерейных билетов – и вы получаете джекпот. Но даже если этого не произойдет, вы все равно сможете выиграть кучу денег по тем лотерейным билетам, в которых совпадут пять из шести чисел. Есть ли у вас билет с числами 4, 7, 10, 11, 34? В одном из билетов Деннистона такие числа есть, а значит, единственный случай, когда у вас не окажется такого билета, – если в нем были числа 4, 7, 10, 11, 34, 47 или 4, 7, 10, 11, 34, 48, поэтому вы его выбросили.

109