Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
9. До сих пор мы говорили о кодовом расстоянии кода и максимальном числе t исправляемых ошибок как об основных показателях корректирующей способности кода. Однако ясно, что более весомым показателем является величина t/n, показывающая, какова доля числа ошибочных символов от общего числа символов принятого слова, при которой возможно еще правильное декодирование (исправление ошибок). С другой стороны, отношение k/n (k — число информационных символов) характеризует избыточность кода: чем меньше это отношение,-тем, очевидно, больше избыточность,
,76 И лот здесь коды БЧХ обнаруживают некоторый изъян. Оказывается, при заданной корректирующей способности, т, е. заданной величине tin, коды БЧХ большой длины имеют слишком высокую избыточность. Более того: если отношение tin фиксировано, а л-»-оо, то ft/n->-0.
Стремление исправить этот недостаток привело к появлению таких кодовых конструкций, как коды-произведения (см. дополнение 12 к §11) и их обобщение — каскадные коды. Строящиеся, как правило, на базе кодов БЧХ, они в значительной степени сохраняют их достоинства, но одновременно избавлены от упомянутого выше дефекта.
15. О ГРАНИЦАХ ВОЗМОЖНОГО
В КОДИРОВАНИИ И СОВЕРШЕННЫХ КОДАХ
Одна из основных проблем теории кодирования (и, пожалуй, самая интригующая) формулируется следующим образом:
Каково максимальное число кодовых слов в двоичном коде длины п, если наименьшее расстояние между кодовыми словами равно d? (Для указанного числа, зависящего от значений п и сі, будем применять обозначение М(п, а).)
Ответ на поставленный вопрос позволил бы во всех случаях выяснить, какой наименьшей длины должен быть код, чтобы можно было, во-первых, передать нужное число сообщений, и во-вторых, гарантировать исправление (или обнаружение) данного числа ошибок.
Однако здесь мы сталкиваемся с явлением весьма распространенным в математике, когда простая по формулировке задача оказывается далеко не столь простой для решения. И хотя указанной проблеме было посвящено немало интересных и глубоких исследований, хотя для ее решения были испытаны самые разнообразные математические методы (вплоть до весьма современных — таких, как линейное программирование), исчерпывающего решения пока не получено. Более того, сейчас, по-видимому, уже ясно, что едва ли удастся найти сколько-нибудь обозримую формулу для числа М(п, d). Более реальный, хотя тоже нелегкий путь, по которому и идут исследования, заключается в том, чтобы достаточно точно оценить это число.
Мы расскажем здесь о самых простых оценках для числа M (п, d), которые могут быть получены из несложной комбинаторики.
Будем называть шаром радиуса г с центром в слове х множество всех слов у, удаленных от х на расстояние, не большее г, т. е. таких, что р(х, у)^г (аналоґия с обычным шаром).
,77 Во всяком шаре радиуса г содержится одно и то же количество двоичных слов, зависящее только от г, поскольку, как нетрудно проверить, оно совпадает с количеством слов шара того же радиуса с центром в нулевом слове. Последний же шар содержит все те двоичные слова, у которых число единиц не превышает г. Число различных «-буквенных слов с і единицами равно числу сочетаний из п элементов по і (Cil). Поэтому, обозначив число всех слов в шаре радиуса г через Vr, получим:
Vf = I +С\ + Cl + ...+Crn= І Cf1.
і= о
Рассмотрим теперь код длины п с кодовым расстоянием d=2t+\, содержащий максимальное число М(п, d) = = М(п, 2/+1) кодовых слов. Иными словами, это наибольший по объему код, исправляющий любые t (и меньшее число) ошибок.
«Окружим» каждое кодовое слово шаром радиуса і. Очевидно, что эти шары попарно не пересекаются, и, следовательно, общее число слов во всех шарах равно Vi •М(п, d). Разумеется, оно не может превосходить числа всех п-буквенных двоичных слов, т. е. Vt-M(n, d)^2n, откуда мы и получаем верхнюю оценку для максимального числа кодовых слов:
(1)
Эта граница, предложенная Хеммингом, называется его именем. Другое ее название — граница сферической упаковки — связано с тем, что равенство в (1) достигается в том случае, когда непересекающиеся шары (или сферы) радиуса t с центром в кодовых словах целиком заполняют все множество «-буквенных слов. Коды, обладающие таким свойством, называют совершенными или плотно упакованными, и к ним мы еще вернемся чуть позже.
Чтобы получить оценку снизу, рассмотрим для каждого кодового слова шар радиуса 21 с центром в этом слове. Из максимальности кода следует, что любое «-буквенное слово принадлежит хотя бы одному такому шару. Будь иначе, мы смогли бы добавить к нашему коду еще по крайней мере одно слово, не уменьшая кодового расстояния. Итак, объединение всех рассматриваемых шаров совпадает с множеством всех /z-буквенных слов.
Произведение VstM(n, d) есть число слов, содержащихся во всех этих шарах. Но при этом многие слова могут при-
,78 надлежать не одному, а нескольким шарам, и значит, в произведении учитываются несколько раз. Поэтому справедливо неравенство
V2iM(n, d)> 2",
которое дает теперь уже нижнюю оценку для максимального числа кодовых слов:
