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).