1.4. Границы для кодов

Значительная часть всех работ по теории кодирования посвящена исследованию различных границ для кодов. Существует два класса границ: границы для кодового расстояния и границы для кодовых характеристик. Для получения границ для кодового расстояния нужно рассматривать те или иные структурные свойства кодов. Наиболее важными и полезными границами для кодового расстояния являются граница Хемминга (которая уже

рассматривалась), граница Плоткина и граница Гилберта. Границы Хемминга и Плоткина показывают, насколько большим может быть кодовое расстояние кода с заданными длиной и скоростью, в то время как граница Гилберта является границей существования и дает нижнюю оценку для кодового расстояния «наилучшего» кода. Границы для кодового расстояния часто используются при выяснении того, насколько построенные коды близки к оптимальным.

Определение всех границ для характеристик кода основано на рассуждениях, связанных со случайным кодированием. Эти рассуждения показывают, что вероятность ошибки при использовании «среднего» или «типичного» кода экспоненциально убывает с возрастанием длины кода. Отсюда, конечно, вытекает, что существуют коды, которые оказываются лучше «типичных». Хотя рассуждения, касающиеся случайного кодирования, показывают, что вероятность ошибки может убывать экспоненциально с ростом из них не следует, как нужно выбирать коды с такими свойствами. Кроме того, эти границы обычно являются сравнительно бесполезными при исследовании параметров конкретных кодов, поскольку вероятность ошибки, достигаемая при использовании хорошего кода, существенно меньше, чем предсказываемая границами. Однако эти границы оказываются полезными при исследовании зависимости характеристик от уровня шума или модели канала.

1.4.1. Границы для кодового расстояния

В этом подразделе приведем границы для кодового расстояния и обсудим область их применимости. Мы попытаемся дать строгие доказательства, при которых во многих случаях нужно использовать свойства кодов, которые будут описаны в гл. 2. Наша цель в этом подразделе — дать представление об этих границах и о том, почему их можно применять. Читатель, которого интересуют подробные доказательства и обсуждение некоторых других границ, может обратиться к превосходным книгам Питерсона и Уэлдона [1], Берлекэмпа [2], Галлагера [3], Мак-Вильямс и Слоэна [8].

Граница Хемминга уже обсуждалась в связи с построением таблицы декодирования. Ее можно сформулировать в виде (1.4), указывающем на наибольшее число кодовых слов, возможных при данных или как границу для избыточности, необходимой при заданных значениях и

Обобщение этой границы на недвоичные коды имеет вид

где число символов кодового алфавита.

Граница Плоткина также является верхней границей для кодового расстояния при заданных В основе вывода границы

Плоткина лежит тот факт, что минимальный вес ненулевого кодового слова группового кода не превышает среднего веса всех ненулевых кодовых слов. Можно показать, что если записать все кодовые слова двоичного группового -кода в виде строк матрицы, то каждый столбец будет содержать ровно ненулевых элементов. Поскольку общее число столбцов матрицы равно сумма весов всех кодовых слов линейного равна Поскольку общее число ненулевых кодовых слов равно а минимальный вес ненулевого кодового слова не может превышать среднего веса ненулевого кодового слова, получаем следующее неравенство:

Граница Плоткина для недвоичных кодов имеет вид

Неравенства (1.48) и (1.49) являются простейшими выражениями границы Плоткина. Они удобны для получения максимально возможного значения при данных но не очень удобны для получения максимального значения при данных Другая форма границы Плоткина записывается в виде

для двоичного случая и

для недвоичного случая.

Граница Хемминга обычно близка к оптимальной для высокоскоростных кодов (т. е. для больших значений а граница Плоткина — для низкоскоростных кодов.

Согласно границе Гилберта (называемой также границей Варшамова — Гилберта) при

существует -код с кодовым расстоянием, не меньшим и с числом проверок на четность, не превышающим В недвоичном случае граница Гилберта имеет вид

Приведем пример использования этих границ. Предположим, что нам нужно найти код длиной 63 с кодовым расстоянием 5 и наибольшим возможным значением Примером кода с который можно построить алгебраическими методами, является -код Боуза — Чоудхури — Хоквингема (Такие коды будут рассматриваться в подразд. 2.3.1.) Для оценки того, насколько хорошим является этот код, используем границы

Хемминга и Гилберта. Из определения границы Хемминга следует, что

или

Таким образом, наименьшее число проверок на четность, удовлетворяющее (1-54), равно 11. Граница Гильберта «утверждает», что

или

Наименьшее число проверок на четность, для которого справедливо неравенство (1.55), равно 16. Таким образом, из границы

Хемминга следует, что не существует кодов с а граница Гилберта «гарантирует» существование кодов с Отсюда можно сделать вывод, что -код является хорошим и дальнейшие поиски могут привести лишь к незначительному улучшению.

Таблица 1.4. (см. скан) Максимальные, минимальные и достижимые значения для различных кодов длиной 31

В табл. 1.4 приведены и нижние границы для при различных значениях Значения получены с помощью границы Хемминга, за исключением случаев, отмеченных звездочкой, когда лучшие результаты дает применение границы Плоткина. В таблицу включены также параметры некоторых известных кодов БЧХ.