6.6. ВЕСОВОЙ СПЕКТР КОДА, ПОЛУЧЕННОГО В РЕЗУЛЬТАТЕ СДВИГА

В этом разделе мы изучим весовой спектр кода, полученного в результате сдвига из любого -кода Пусть произвольный вектор из число векторов веса в коде Конечно, если линейный код, то представляет собой смежный класс кода содержащий Преобразование Мак-Вильямс спектра согласно (5.31) имеет следующий вид:

где представляет собой код, записанный как элемент групповой алгебры (см. гл. 5).

Когда весовой спектр кода и Заметим, что (см. упражнения (18) и (19) гл. 5)

что равно нулю, когда

Теорема 15. Преобразования спектров ортогональны:

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

Далее,

Если то что доказывает первую часть теоремы. Если то в силу соотношения (5.36)

Следствие 16. Равенство выполняется тогда и только тогда, когда условие влечет условие для всех

Доказательство. Утверждение вытекает из теоремы 7 гл. 5 и уравнения (6.15).

Как и в § 5.3, пусть

Лемма 17. Если вектор и из имеет вес то

многочлен Кравчука. Доказательство. По определению

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

Введем аннулирующий многочлен кода

где представляют собой те индексы для которых Заметим, что для значений 0 либо либо Поэтому по следствию 16 условие для некоторого вектора влечет

Представление в виде линейной комбинации многочленов Кравчука

называется разложением по Кравчуку, а числа а называются коэффициентами Кравчука. Последним членом этого разложения является так как многочлен имеет степень и поэтому Кроме того (по теореме 20 гл. 5), имеем, что

Лемма 18.

Доказательство. Для того чтобы доказать равенство этих двух элементов групповой алгебры, достаточно (согласно упражнению (16) гл. 5) показать, что значения характеров на этих двух элементах совпадают для всех Согласно упражнению (12) гл. 5

Если вектор имеет вес то по лемме 17

Если равно одному из то по определению в противном случае по теореме 7 гл. 5. Таким образом, в любом случае, если то

Если теперь то

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

Лемма 19. Если сумма

такова, что

то аннулирующий многочлен кода делит многочлен

Упражнение. (9). Доказать лемму 19.

Теорема 20. Для каждого числа однозначно определяются числами

Доказательство, (i). Вначале покажем, что следующим образом может быть выражено через

(Напомним, что Для доказательства этого вычислим

где

так как равно числу кодовых слов находящихся на расстоянии от Тогда

и поэтому

что и доказывает требуемое равенство (6.18).

(ii). Если мы выпишем разложение

то из доказательства леммы 18 следует, что

и, следовательно,

что дает выражение для Чтобы получить выражение для надо разложить по многочленам Кравчука функцию

Замечание. Чтобы получить разложение из разложения оказывается полезной рекуррентная формула для многочленов Кравчука (теорема 19 гл. 5).

Пример. (1). Так как код Хэмминга длины с расстоянием является совершенным, то для такого кода имеется только два типа смежных классов, а именно: сам код и смежных классов, лидеры которых имеют вес, равный 1. Если то Если же то так что Для см. рис. 6.1.

Рис. 6.1. Весовые спектры смежных классов кода Хэмминга длины 7

Проиллюстрируем теперь теорему 20, проверив вторую строку этой таблицы.

Для рассматриваемого кода поэтому а Следовательно,

Так как

Рекуррентная формула из теоремы 19 гл. 5 дает:

т. е.

Далее Следовательно, откуда Затем

откуда

что дает тем самым проверка второй строки рис. 6.1 окончена.

Пример. (2). Код Нордстрома-Робинсона (см. § 2.8) имеет следующий спектр расстояний: причем преобразование Мак-Вильямс этого спектра совпадает с ним самим, т. е. Поэтому аннулирующий многочлен равен:

и далее

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

Пример. (3). (Смежные классы кодов БЧХ, исправляющих две ошибки.) Пусть — код БЧХ, исправляющий две ошибки с параметрами где нечетное, В § 15.4 будет показано, что дуальный код имеет только 3 ненулевых веса, а именно Следовательно, аннулирующий многочлен (6.16) кода равен:

Для наших целей нам необходимо найти лишь величину

Коэффициент при равен

Рис. 6.2 Весовые спектры кодов, полученных сдвигами кода а коэффициент при в многочлене Кравчука

равен Следовательно,

Таким образом, из соотношения (6.18) следует, что в смежном классе кода с минимальным весом 3 имеет место равенство

Поэтому все смежные классы с минимальным весом 3 имеют одинаковые весовые спектры. Уравнение (6.18) показывает также, что все смежные классы должны иметь минимальный вес 0, 1, 2 или 3. Так как этот код исправляет две ошибки, то имеется один смежный класс с весом классов с весом классов с весом 2. Минимальный вес в остальных смежных классах равен 3. Таким образом, код является квазисовершенным кодом (см. § 1.5).

Для четных значений код БЧХ длины исправляющий две ошибки, по-прежнему является квазисовершенным, как мы

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

Теорема 21. Для любого вектора найдется кодовое слово, находящееся на расстоянии не более чем от

Доказательство. Из уравнения (6.18) следует, что не могут равняться нулю все числа при

Пример. Для кода Хэмминга в самом деле, так как код совершенный, то любой вектор из находится на расстоянии не более чем 1 от некоторого кодового слова.

Замечание. Можно определить радиус покрытия для кода как число

Таким образом, представляет собой истинное внешнее расстояние кода, т. е. параметр равен наибольшему из минимальных весов всех кодов, полученных в результате сдвига кода Теорема 21 говорит о том, что Как мы увидим в упражнении (11), параметр может быть и меньше чем

Определим два других метрических параметра кода диаметр

и радиус

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

Упражнения. (10). Показать, что

(11). (i). Показать, что для симплексного -кода параметр [Указание. Воспользоваться границей Плоткина.]

(ii). Показать, что для этого кода таким образом, .

(iii). Показать также, что .

(iV). Вывести отсюда, что имеется бесконечно много кодов, для которых в правой части (6.20) выполняется равенство; показать то же самое для левой части (6.20).

Задача (нерешенная). (6.2). Для произвольного кода найти оценки его радиуса покрытия и хороший метод его вычисления.

Теорема 22. Пусть -двоичный линейный -код и пусть Для значений обозначим через элемент групповой алгебры, представляющий все

векторы из находящиеся на расстоянии от некоторого кодового слова из т. е. объединение всех смежных классов кода с лидерами веса Пусть обозначает число векторов веса в множестве Тогда

Доказательство. Представим в виде

Согласно упражнениям (16) и (14) гл. 5 получаем, что

(последнее равенство имеет место согласно упражнению (13) гл. 5). Следовательно, левая часть выражения (6.21) равна:

С другой стороны, правая часть этого выражения равна:

что равно (6.22) в соответствии с равенствами (5.9) и (5.11).

Упражнение. (12). Предположим, что код имеет минимальное расстояние и рассмотрим для этого кода неполный алгоритм декодирования (§ 1.5), исправляющий любые ошибок (но не более) для некоторого фиксированного Показать, что вероятность правильного декодирования равна

а вероятность того, что декодер примет неправильное решение, равна