14.4. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ БЛОКОВЫХ КОДОВ

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

Мы проведем лишь асимптотический анализ. При фиксированном объеме алфавита введем обозначение

где максимум берется по всем кодам с длиной и, и скоростью равно

и представляет собой минимальное расстояние кода Функция определяет наибольшее минимальное расстояние среди всех кодов над со скоростью и длиной Если не считать

области малых значений функция неизвестна. Определим, далее,

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

Хотя знать функции было бы весьма желательно, в настоящее время они не известны. Все что мы знаем — это их нижние и верхние границы; некоторые из них выводятся в данном параграфе. Остановимся лишь на тех границах, которые можно получить, не прилагая больших усилий; в частности, мы получим границы, известные как нижняя граница Гилберта и верхняя граница Элайса.

Чтобы получить эти границы, воспользуемся методом исчерпывания и оцепим композиции типичных кодовых слов. Композицией -ичного кодового слова назовем -мерный вектор компонента которого определяет, сколько раз в кодовом слове встречается 1-я буква. Относительной частотой -ичного кодового слова называется -мерный вектор где Выразим границы минимального расстояния через полиномиальные коэффициенты где означает произведение Функция энтропии определяется как

Мы хотим доказать асимптотически справедливое при больших равенство

и сделать это как можно короче. Этому условию удовлетворяет доказательство, использующее формулу Стирлинга

Теорема 14.4.1.

где

Доказательство.

Замена доказывает правую часть неравенства. Левая часть доказывается тем же способом.

Теперь можно приступить к доказательству границы Гилберта. Мы проведем его, подсчитав число кодовых слов внутри сферы с центром в произвольной точке пространства (не обязательно представляющей кодовое слово) и затем усреднив это число. Число точек внутри сферы радиуса назовем объемом сферы; оно равно

Теорема 14.4.2. Пусть V — число точек внутри сферы радиуса с центром в некоторой точке векторного пространства Для заданного кода мощности среднее число кодовых слов внутри сферы радиуса с центром в произвольной точке пространства равно

Доказательстве. Опишем сферы радиуса вокруг каждой точки пространства. Подсчитаем число кодовых слов внутри каждой сферы и затем просуммируем по всем сферам. Так как на расстоянии, не превышающем вокруг кодового слова находится V точек, это слово лежит внутри V таких сфер. Поэтому сумма числа кодовых слов внутри всех сфер равна следовательно, в среднем на сферу приходится кодовых слов.

Теорема 14.4.3. Над существуют коды со скоростью и минимальным расстоянием для которых

где V — объем сферы радиуса

Доказательство. Воспользуемся теоремой 14.4.2 и будем считать, что Если это не так, то можно взять любую точку, у которой на расстоянии, не превышающем нет кодовых слов, и объявить ее кодовым словом, тем самым расширив код. Следовательно,

или

откуда следует утверждение теоремы.

Теорема 14.4.4 (граница Гилберта). Функция для всех значений в, которые удовлетворяют неравенству

Доказательство. Объем V представляет сумму слагаемых, из которых последнее является наибольшим. Поэтому

Используя теорему 14.4.1 и сделав подстановку получим

где стремится к нулю при стремящемся к бесконечности. Далее,

Подставив это неравенство в неравенство, доказанное в теореме 14.4.3 и опустив в асимптотике член о (1), завершим доказательство.

Для двоичных кодов граница Гилберта принимает вид

где

Графически эта граница изображена на рис. 14.7.

Рис. 14.7. Некоторые известные границы функции при

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

На расстоянии от каждого кодового слова находится всего

слов; это число равно количеству слов, расположенных на сфере радиуса

Теорема 14.4.5. Пусть число кодовых слов на сфере радиуса с центром в любой точке векторного пространства Для заданного кода мощности среднее число кодовых слов на сфере с центром в произвольной точке пространства равно

Доказательство. Так как на расстоянии от кодового слова располагается точек, оно лежит на таких сферах. Поэтому сумма числа кодовых слов, расположенных на всех таких сферах, равна и среднее число кодовых слов на сфере равно

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

Таким образом получим сферу радиуса с центром в начале координат, на которой лежит кодовых слов, где не меньше . В дальнейшем величина будет выбрана так, чтобы было достаточно большим и удовлетворяло нашим целям. Следующий шаг — оценка расстояния между двумя кодовыми словами, находящимися на сфере. Чтобы получить ее, оценим среднее расстояние между такими кодовыми словами

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

Напомним, что это совместная композиция кодовых слов с и с. Упростим суммирование по с и с. Пусть равно единице, если в позиции с стоит I, а с имеет в этой позиции в противном случае оно равно нулю. Пусть число кодовых слов на сфере, имеющих I в позиции. Тогда

Введем теперь величину

равную доле кодовых слов на сфере, имеющих I в позиция. Общее расстояние между такими кодовыми словами равно

где равно единице, если и нулю в противном случае. Значения нам неизвестны, но мы знаем, что они удовлетворяют двум следующим ограничениям:

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

Лемма 14.4.6. Пусть где равно единице, если и нулю с противном случае. Если для к имеют место ограничения

то

Доказательство. Прежде всего заметим, что из указанных ограничений вытекает соотношение

Пусть

при всех Убедимся, что эти значения максимизируют Заметим, что

Поэтому при которые удовлетворяют нашим ограничениям, включая

Раскрыв скобки проведя упрощения в левой части этого равенства, получим

Достаточно показать, что величина в левой части этого равенства неположительна. Введем обозначение

и заметим, что Необходимо доказать, что при любом I

Но при любом

Доказательство леммы завершается вычислением значения

Теорема 14.4.7 (граница Элайса). Пусть

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

Доказательство. Выберем величину в теореме 14.4.5 так, чтобы было больше единицы. Тогда существует сфера, на

которой число кодовых слов больше единицы. Среднее расстояние между этими кодовыми словами удовлетворяет неравенству

Для завершения доказательства необходимо применить лемму 14.4.6 и воспользоваться тем, что хотя бы два кодовых слова должны располагаться друг от друга на расстоянии, не меньшем среднего.

Следствие 14.4.8 (граница Элайса). В двоичных кодах со скоростью относительное минимальное расстояние асимптотически удовлетворяет неравенству

при любых для которых

Доказательство. Положим в теореме 14.4.7 и перепишем неравенство теоремы 14.4.7 в виде

где

По условиям следствия величина 6 положительна; поэтому стремится к единице, когда стремится к бесконечности. Следствие доказано.