15. О ГРАНИЦАХ ВОЗМОЖНОГО В КОДИРОВАНИИ И СОВЕРШЕННЫХ КОДАХ
Одна из основных проблем теории кодирования (и, пожалуй, самая интригующая) формулируется следующим образом:
Каково максимальное число кодовых слов в двоичном коде длины п, если наименьшее расстояние между кодовыми словами равно й? (Для указанного числа, зависящего от значений п и й, будем применять обозначение М(п, й).)
Ответ на поставленный вопрос позволил бы во всех случаях выяснить, какой наименьшей длины должен быть код, чтобы можно было, во-первых, передать нужное число сообщений, и во-вторых, гарантировать исправление (или обнаружение) данного числа ошибок.
Однако здесь мы сталкиваемся с явлением весьма распространенным в математике, когда простая по формулировке задача оказывается далеко не столь простой для решения. И хотя указанной проблеме было посвящено немало интересных и глубоких исследований, хотя для ее решения были испытаны самые разнообразные математические методы (вплоть до весьма современных — таких, как линейное программирование), исчерпывающего решения пока не получено. Более того, сейчас, по-видимому, уже ясно, что едва ли удастся найти сколько-нибудь обозримую формулу для числа М(п, й). Более реальный, хотя тоже нелегкий путь, по которому и идут исследования, заключается в том, чтобы достаточно точно оценить это число.
Мы расскажем здесь о самых простых оценках для числа М(п, б), которые могут быть получены из несложной комбинаторики.
Будем называть шаром радиуса г с центром в слове х множество всех слов у, удаленных от х на расстояние, не большее г, т. е. таких, что р(х, (аналогия с обычным шаром).Во всяком шаре радиуса г содержится одно и то же количество двоичных слов, зависящее только от г, поскольку, как нетрудно проверить, оно совпадает с количеством слов шара юго же радиуса с центром в нулевом слове. Последний же шар содержит все те двоичные слова, у которых число единиц не превышает г. Число различных «-буквенных слов с I единицами равно числу сочетаний из « элементов по I (С;,). Поэтому, обозначив число всех слов в шаре радиуса г через Vг, получим:
содержащий максимальное число
Рассмотрим теперь код длины « с кодовым расстоянием
кодовых слов. Иными словами, это наибольший по ооъему код, исправляющии люоые I (и меньшее число) ошибок.
«Окружим» каждое кодовое слово шаром радиуса I. Очевидно, что эти шары попарно не пересекаются, и, следовательно, общее число слов во всех шарах равно Уг •М(п, й). Разумеется, оно не может превосходить числа всех п- буквенных двоичных слов, т. е. У1 •М(п, й)^.2п, откуда мы и получаем верхнюю оценку для максимального числа кодовых слов:
Эта граница, предложенная Хеммингом, называется его именем. Другое ее название — граница сферической упаковки — связано с тем, что равенство в (1) достигается в том случае, когда непересекающиеся шары (или сферы) радиуса I с центром в кодовых словах целиком заполняют все множество «-буквенных слов. Коды, обладающие таким свойством, называют совершенными или плотно упакованными, и к ним мы еще вернемся чуть позже.
Чтобы получить оценку снизу, рассмотрим для каждого кодового слова шар радиуса 21 с центром в этом слове. Из максимальности кода следует, что любое «-буквенное слово принадлежит хотя бы одному такому шару. Будь иначе, мы смогли бы добавить к нашему коду еще по крайней мере одно слово, не уменьшая кодового расстояния. Итак, объединение всех рассматриваемых шаров совпадает с множеством всех «-буквенных слов.
Произведение У21М{п, (I) есть число слов, содержащихся во всех этих шарах, Но при этом многие слова могут принадлежать не одному, а нескольким шарам, и значит, в произведении учитываются несколько раз. Поэтому справедливо неравенство которое дает теперь уже нижнюю оценку для максимального числа кодовых слов:
Оценки, аналогичные (1) и (2), справедливы и для недвоичных кодов. В случае произвольного основания ц они имеют вид:
На примерах можно убедиться, что указанные границы далеко отстоят одна от другой, т. е. являются весьма грубыми. Имеется много их уточнений, а также оценок другого рода, но это вопросы более специальные.
Скажем теперь несколько слов о совершенных кодах, с которыми связана целая эпоха в теории кодирования. Мы отмечали уже, что число кодовых слов М совершенного кода, исправляющего I ошибок, достигает наибольшей возможной величины (верхней границы Хемминга). В случае двоичного кода имеем, следовательно,
1ривиальным примером совершенного кода является код с повторением нечетной длины п=21+\. В этом случае верхняя гпаница П) равна
что совпадает с числом кодовых слов кода с повторением.
при этом число слов в шаре радиуса г вычисляется по формуле:
Более интересный класс совершенных кодов являют собой хорошо известные нам коды Хемминга длины 2т—1 с исправлением одиночных ошибок. Граница сферической упаковки для этих параметров (п=2т—1, 1~\) равна
Столько же кодовых слов имеет двоичный код Хемминга.
I, для которых
Из равенства (3) вытекает, что совершенные двоичные коды могут существовать лишь для таких параметров п и
является степенью двойки (так
именно и было в рассмотренных выше примерах).
Понятие плотно упакованного кода появилось уже в первых работах по теории кодирования, тогда же возникла проблема описания всех совершенных кодов. Поиск плотно упакованных кодов казался весьма заманчивой задачей, но лишь однажды он увенчался успехом. Новый совершенный двоичный код был открыт в 1949 г. американским ученым Голеем. Этим кодом (его так и называют — код Голея) оказался (23, 12)-код, исправляющий три ошибки. Как впоследствии выяснилось, этот код является циклическим с порождающим многочленом ц(Х)=Х11+Хй-+Х'1+Хъ.-\-Х-\-\ (мы уже знаем, что этот многочлен служит делителем многочлена X?8—1).
Дальнейшие поиски совершенных кодов к удаче не привели. Это не значит, однако, что не появлялось интересных работ о совершенных кодах. Самой значительной и глубокой из них была опубликованная в 1957 г. статья Ллойда, в которой на изучение проблемы были брошены мощные средства теории функций комплексного переменного и дифференциальных уравнений. В результате вопрос существования совершенного кода с теми или иными параметрами был сведен к чисто алгебраической задаче, связанной со свойствами корней некоторого многочлена.
Под влиянием этой и ряда других работ стало складываться впечатление, что иных двоичных линейных совершенных кодов, кроме перечисленных, и не существует. Это предположение оказалось справедливым, но доказано оно было лишь в начале семидесятых годов финскими учеными А. Тиетявяйненом и А. Перко и независимо от них советскими учеными В. А. Зиновьевым и В. К. Леонтьевым. Решению проблемы предшествовала многотрудная подготовка, в которую внесли вклад многие специалисты, и немалую роль здесь сыграли результаты и методы упоминавшейся выше работы Ллойда.
Что касается кода Голея, то он является во многих отношениях важным и замечательным кодом и остается источником многих идей и исследований в теории кодирования (см. 112]).Задачи и дополнения
1. Убедиться, что не существует кода длины 20, содержащего 1000 кодовых слов и исправляющего любые комбинации из трех и менее ошибок.
2. Использовать верхнюю оценку Хемминга для доказательства следующего утверждения:
Для всякого д-ичного линейного (п, к)-кода с кодовым расстоянием й = 2/+) величина 1о§?У/ служит нижней границей для числа т праве- ппчных символов:
3. Для оценки «качества» линейного кода можно пользоваться так называемой границей Варшамова — Гильберта. Применительно к двоичным кодам указанная оценка основывается на следующем утверждении:
Бели выполняется неравенство
то существует линейный (и, к)-код с кодовым расстоянием, не меньший й, имеющий не более т проверочных символов.
Для доказательства достаточно построить матрицу Н порядка тХп, в которой любые й—1 столбцов линейно независимы; ока и будет служить проверочной матрицей искомого кода (см. § 11, дополнение 4). В качестве первого столбца Н можно взять любой ненулевой вектор длины т. Пусть уже выбрано столбцов, любые й—1 из которых линейно независимы. Всевозможных линейных комбинаций этих столбцов, содержащих ровно слагаемых, имеется не более С\, и, следовательно, число всех линейных комбинаций, содержащих й—2 или меньше столбцов. не ппевогхопит числя
Но в силу (4) это число меньше величины 2"»—1, т. е. общего количеств; ненулевых столбцов. Поэтому мы можем добавить по крайней мере ещ( один столбец, не равный ни одной из указанных линейных комбинаций В получившейся при этом системе из х+1 векторов любые (1—1 векторо! по-прежнему будут линейно независимы. Продолжая эту процедуру при соединения столбцов, мы и построим искомую матрицу Н.
Мы получили границу, называемую верхней границей Плоткина.
4. Утверждение, доказанное в дополнении 3, обобщается на слу чай линейного кода над произвольным полем из элементов; неравен ство (4) заменяется при этом на следующее неравенство:
5. Можно указать еще одну простую оценку для кодового расстояния. Поскольку суммарный вес ненулевых кодовых слов д-ичного линейного (и, /г)-кода есть 1) (см. §11, дополнение 3), то средний вес ненулевых кодовых слов равен —1 )/(</''—1). Ясно, что он не может быть меньше минимального веса, совпадающего с кодовым расстоянием й. Таким образом,
Оценка (5) обобщается на случай произвольного 9-ичного кода длины п, содержащего М кодовых слов. В этом случае
6. Из оценки Хемминга (1) также можно получить границу для кодового расстояния. Пусть код длины п, исправляющий I и меньшее
Неравенство (7) дает верхнюю границу для 1, а значит, и для кодового расстояния й=21-\-1.
Граница Хемминга точнее границы Плоткика для кодов, избыточность которых не слишком велика (отношение числа проверочных символов к общему числу символов не превосходит 0,6). В остальных случаях точнее граница Плоткина.
Например, для двоичного (16,5)-кода оценка (5) дает е*<8, а из оценки (7) получается 1<А, т. е. с/с9.
7. Имеются и нелинейные совершенные коды, но их также немного. Во всяком случае известно, что любой нетривиальный совершенный код над любым полем должен иметь те же самые параметры (длину, кодовое расстояние и число кодовых слов), что и один из кодов Хемминга или Голея. Все же полное описание нелинейных совершенных кодов, исправляющих одиночные ошибки, пока не получено (см. по этому поводу [12], задача 6.6).