13.4. Граница Плоткина для малых скоростей (граница среднего расстояния)

Минимальное расстояние между любыми двумя кодовыми словами не может превышать среднего расстояния по всевозможным парам кодовых слов. Это замечание, принадлежащее Плоткину, лежит в основе вывода другой границы для минимального расстояния. Для метрики Ли эта граница впервые была получена Грэхемом и Вайнером [1968].

Предположим, что код состоит из К слов , где Тогда полное расстояние по всем

парам кодовых слов задается формулой

Обозначим через число появлений 7-й буквы алфавита среди букв Тогда вероятностный вектор характеризует координату случайно выбранного из кода слова. Имеем

где элемент на пересечении строки и столбца в матрице 3 расстояний между буквами входного алфавита. Например, для в метрике Ли

а в метрике Хэмминга

В любом случае полное расстояние задается формулой

Это полное расстояние содержит сумму по всем парам кодовых слов. Среди них К пар содержат одинаковые слова, а пар — различные слова. Среднее расстояние по всем

парам различных кодовых слов удовлетворяет соотношению

где «лучший» из возможных векторов Так как минимальное расстояние не превышает среднего расстояния, то

Соотношение (13.41) называется границей Плоткина для минимального расстояния.

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

Легко проверить, что Хрдля всех к Легко также проверяется ортогональность собственных векторов, т. е. тот факт, что если (Здесь вектор, комплексно сопряженный с

В общем случае величина комплексно сопряжена с Если — симметричная матрица, то все ее собственные числа вещественны. В этом случае вместо комплексно сопряженных собственных векторов можно использовать вещественные собственные векторы но это дает весьма малые преимущества.

Собственные числа матрицы 3 легко вычислить и в случае метрики Хэмминга, и в случае метрики Ли. Полагая в случае метрики Хэмминга, получим, что при

и

главное собственное число, т. е. собственное число с максимальным модулем.

Для вычисления в метрике Ли рассмотрим сумму

или

При нечетных неглавные собственные числа матрицы в метрике Ли задаются формулой Так как то при используя (13.44), получим

Главное собственное число равно

Для четных неглавные собственные числа матрицы 3 в метрике Ли определяются формулой

а главное собственное число — формулой

Из равенс в (13.42), (13.45) и (13.47) следует, что все неглавные собственные чиста матрицы 3 неположительны и в метрике Хэмминга, и в метрике Ли. Поэтому квадратичная форма выпуклая функция от вектора т. е., если то

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

Так как собственные векторы ортогональны и то Предположение о выпуклосш квадратичной формы при этом сводится к утверждению, что

Так как выпуклая функция от то для всех Так как все собственные числа, кроме главного, неположительны, то

для всех выпуклая функция вектора

В силу выпуклости квадратичной формы стационарная точка являемся точкой лбсо потною максимума, а ввиду симметрии вектор задает стационарную точку. Таким образом, наибольшее значение функции из (13 41) можно оиреде из уравнений Мы получили

13.49. Теорема Минимальное расстояние произвольного кода с блоковой длиной и К кодовыми словами над алфавитом из букв удовлетворяет неравенству

где постоянная задается формулой