15. О границах возможного в кодировании и совершенных кодах

Одна из основных проблем теории кодирования (и, пожалуй, самая интригующая) формулируется следующим образом:

Каково максимальное число кодовых слов в двоичном коде длины n, если наименьшее расстояние между кодовыми словами равно d? (Для указанного числа, зависящего от значений n и d, будем применять обозначение М(n, d).)

Ответ на поставленный вопрос позволил бы во всех случаях выяснить, какой наименьшей длины должен быть код, чтобы можно было, во-первых, передать нужное число сообщений, и во-вторых, гарантировать исправление (или обнаружение) данного числа ошибок.

Однако здесь мы сталкиваемся с явлением весьма распространенным в математике, когда простая по формулировке задача оказывается далеко не столь простой для решения. И хотя указанной проблеме было посвящено немало интересных и глубоких исследований, хотя для ее решения были испытаны самые разнообразные математические методы (вплоть до весьма современных - таких, как линейное программирование), исчерпывающего решения пока не получено. Более того, сейчас, по-видимому, уже ясно, что едва ли удастся найти сколько-нибудь обозримую формулу для числа М(n, d). Более реальный, хотя тоже нелегкий путь, по которому и идут исследования, заключается в том, чтобы достаточно точно оценить это число.

Мы расскажем здесь о самых простых оценках для числа М(n, d), которые могут быть получены из несложной комбинаторики.

Будем называть шаром радиуса r с центром в слове х множество всех слов y, удаленных от х на расстояние, не большее r, т. е. таких, что ρ(х, y) ≤ r (аналогия с обычным шаром).

Во всяком шаре радиуса r содержится одно и то же количество двоичных слов, зависящее только от r, поскольку, как нетрудно проверить, оно совпадает с количеством слов шара того же радиуса с центром в нулевом слове. Последний же шар содержит все те двоичные слова, у которых число единиц не превышает r. Число различных n-буквенных слов с i единицами равно числу сочетаний из n элементов по i(Cⁱ_n). Поэтому, обозначив число всех слов в шаре радиуса r через V_r, получим:

Рассмотрим теперь код длины n с кодовым расстоянием d = 2t + 1, содержащий максимальное число М(n, d) = М(n, 2t + 1) кодовых слов. Иными словами, это наибольший по объему код, исправляющий любые t (и меньшее число) ошибок.

"Окружим" каждое кодовое слово шаром радиуса t. Очевидно, что эти шары попарно не пересекаются, и, следовательно, общее число слов во всех шарах равно V_t · M(n, d). Разумеется, оно не может превосходить числа всех n-буквенных двоичных слов, т. е. V_t · М(n, d) ≤ 2ⁿ, откуда мы и получаем верхнюю оценку для максимального числа кодовых слов:

Эта граница, предложенная Хеммингом, называется его именем. Другое ее название - граница сферической упаковки - связано с тем, что равенство в (1) достигается в том случае, когда непересекающиеся шары (или сферы) радиуса t с центром в кодовых словах целиком заполняют все множество n-буквенных слов. Коды, обладающие таким свойством, называют совершенными или плотно упакованными, и к ним мы еще вернемся чуть позже.

Чтобы получить оценку снизу, рассмотрим для каждого кодового слова шар радиуса 2t с центром в этом слове. Из максимальности кода следует, что любое n-буквенное слово принадлежит хотя бы одному такому шару. Будь иначе, мы смогли бы добавить к нашему коду еще по крайней мере одно слово, не уменьшая кодового расстояния. Итак, объединение всех рассматриваемых шаров совпадает с множеством всех n-буквенных слов.

Произведение V_2t M(n, d) есть число слов, содержащихся во всех этих шарах. Но при этом многие слова могут принадлежать не одному, а нескольким шарам, и значит, в произведении учитываются несколько раз. Поэтому справедливо неравенство

которое дает теперь уже нижнюю оценку для максимального числа кодовых слов:

Оценки, аналогичные (1) и (2), справедливы и для недвоичных кодов. В случае произвольного основания q они имеют вид:

при этом число слов в шаре радиуса r вычисляется по формуле:

На примерах можно убедиться, что указанные границы далеко отстоят одна от другой, т. е. являются весьма грубыми. Имеется много их уточнений, а также оценок другого рода, но это вопросы более специальные.

Скажем теперь несколько слов о совершенных кодах, с которыми связана целая эпоха в теории кодирования. Мы отмечали уже, что число кодовых слов М совершенного кода, исправляющего t ошибок, достигает наибольшей возможной величины (верхней границы Хемминга). В случае двоичного кода имеем, следовательно,

Тривиальным примером совершенного кода является код с повторением нечетной длины n = 2t + 1. В этом случае верхняя граница (1) равна

что совпадает с числом кодовых слов кода с повторением.

Более интересный класс совершенных кодов являют собой хорошо известные нам коды Хемминга длины 2^m - 1 с исправлением одиночных ошибок. Граница сферической упаковки для этих параметров (n = 2^m - 1, t = 1) равна

Столько же кодовых слов имеет двоичный код Хемминга.

Из равенства (3) вытекает, что совершенные двоичные коды могут существовать лишь для таких параметров n и t, для которых ∑^t_i=0 Cⁱ_n является степенью двойки (так именно и было в рассмотренных выше примерах).

Понятие плотно упакованного кода появилось уже в первых работах по теории кодирования, тогда же возникла проблема описания всех совершенных кодов. Поиск плотно упакованных кодов казался весьма заманчивой задачей, но лишь однажды он увенчался успехом. Новый совершенный двоичный код был открыт в 1949 г. американским ученым Голеем. Этим кодом (его так и называют - код Голея) оказался (23, 12)-код, исправляющий три ошибки. Как впоследствии выяснилось, этот код является циклическим с порождающим многочленом g(X) = X¹¹ + X⁹ + X⁷ + X⁵ + X + 1 (мы уже знаем, что этот многочлен служит делителем многочлена X²³ - 1).

Дальнейшие поиски совершенных кодов к удаче не привели. Это не значит, однако, что не появлялось интересных работ о совершенных кодах. Самой значительной и глубокой из них была опубликованная в 1957 г. статья Ллойда, в которой на изучение проблемы были брошены мощные средства теории функций комплексного переменного и дифференциальных уравнений. В результате вопрос существования совершенного кода с теми или иными параметрами был сведен к чисто алгебраической задаче, связанной со свойствами корней некоторого многочлена.

Под влиянием этой и ряда других работ стало складываться впечатление, что иных двоичных линейных совершенных кодов, кроме перечисленных, и не существует. Это предположение оказалось справедливым, но доказано оно было лишь в начале семидесятых годов финскими учеными А. Тиетявяйненом и А. Перко и независимо от них советскими учеными В. А. Зиновьевым и В. К. Леонтьевым. Решению проблемы предшествовала многотрудная подготовка, в которую внесли вклад многие специалисты, и немалую роль здесь сыграли результаты и методы упоминавшейся выше работы Ллойда.

Что касается кода Голея, то он является во многих отношениях важным и замечательным кодом и остается источником многих идей и исследований в теории кодирования (см. [12]).