3.4. Распределение весов

Рассмотрим -ичный линейный -код, содержащий кодовых векторов веса Совокупность чисел

называется распределением весов, а многочлен

— нумератором весов кода С.

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

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

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

Вероятность ошибочного декодирования равна вероятности того, что вектор ошибок в канале принадлежит смежному классу с минимальным весом или менее (или, другими словами, смежному классу, лидер которого имеет вес или менее), но не является лидером этого смежного класса. Рассмотрим совокупность векторов веса находящихся на расстоянии от вектора веса Число таких векторов обозначим через

Очевидно, что не зависит от того, какие компоненты у равны 1. Для простоты в качестве возьмем вектор, у которого все компоненты с 1-й по равны 1, а остальные равны 0. Заметим, что если I — число равных единице компонент вектора и с номерами от 1 до то Поэтому

Введем многочлен Легко проверить, что

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

Отсюда в свою очередь следует, что общее число векторов веса да, принадлежащих смежным классам с минимальным весом и менее, равно

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

Для удобства расчета последней вероятности часто используется многочлен

Из определения непосредственно следует, что

Многочлен является суммой первых членов вида (степени следующего многочлена:

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

Так как то, зная с помощью формул (3.9) и (3.11) можно найти Это показывает, что нумератор весов является одной из важнейших характеристик кода. Однако нумераторы весов не дают полной информации о распределении весов лидеров смежных классов веса и более. Более того, существуют коды с одним и тем же нумератором весов, имеющие, однако, различные распределения весов лидеров смежных классов [9].

Для некоторых классов кодов, например разделимых кодов с максимально достижимым расстоянием, БЧХ-кодов, исправляющих -кратные ошибки (только при и ряда других, известны общие формулы для распределения весов [9, 18—26]. Однако определение распределения весов произвольного кода является непростой задачей. Конечно, для кодов с небольшим числом информационных символов, используя вычислительную машину, с помощью порождающей матрицы можно механически породить все кодовые слова и найти таким образом распределение весов. При небольших значениях числа проверочных символов для нахождения распределения весов можно воспользоваться следующим тождеством Мак-Вильямс [17].

Теорема 3.3. Пусть С представляет собой -ичный линейный код, двойственный к С, а и соответственно нумераторы весов кодов Тогда

Доказательство. Множество векторов, у которых фиксированные компонент равны 0, очевидно, является подпространством. Выбирая различными способами положение этих компонент,

можно построить таких подпространств

Обозначим через подпространство, двойственное к состоит из векторов, фиксированные компонент которых (дополнительные к нулевым фиксированным компонентам векторов из равны 0. Положим если вектор принадлежит в противном случае. Если вектор имеет вес то для подпространств которые определяются выбором компонент из нулевых компонент вектора имеем для всех остальных подпространств Следовательно,

Но тогда

Аналогично получаем

С другой стороны, из утверждения 2.35 следует, что

Из формул (3.12) и (3.13) имеем

Заметим, что в последнем равенстве является произвольным целым числом из интервала Умножим обе части (3.15) на и просуммируем по При этом в левой части получим следующую сумму:

В то же время сумма в правой части будет равна

Разделив обе части получающегося в результате равенства на получим

Замена переводит последнее равенство в тождество Мак-Вильямс.

Если часть параметров и известна, то для нахождения оставшихся можно воспользоваться тождествами Плесс [8, 9, 27], представляющими собой модифицированные тождества Мак-Вильямс.

Понятие двойственного кода может быть обобщено на случай нелинейных кодов. При этом также удается получить аналог тождества Мак-Вильямс [28].

Утверждение 3.11 [8]. Пусть матрица размера с элементами из поля все столбцы которой являются различными и ненулевыми. Тогда все ненулевые кодовые векторы двоичного линейного -кода, для которого матрица является порождающей, имеют вес

Краткое доказательство. Пусть строки Рассмотрим линейную комбинацию

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

Задача 3.12. Обобщить предыдущее утверждение на случай произвольного

Утверждение 3.13. Нумератором весов кода, двойственного к коду из утверждения 3.11, является многочлен

(Для доказательства этого утверждения следует воспользоваться утверждением 3.11 и тождеством Мак-Вильямс.)