Как не ошибаться. Сила математического мышления - читать онлайн книгу. Автор: Джордан Элленберг cтр.№ 101

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

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

Хэмминг в 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

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

000011101111111111111111111111111111111111111110

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

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

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

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