Пусть Ai - ЧИСЛО КОДОВЫХ слов веса / линейного (п, )-кода. Распределением весов кода называется (п + 1)-мерный вектор с компонентами Ai, 1 = 0, п. Очевидно, что если минимальное расстояние кода равно d *, то Ло = 1, Ль Ad*-i равны нулю, а Ad отлично от нуля. Более глубокая характеристика кода требует дополнительного анализа.

Аналитическое описание распределения весов кода - трудная задача, но для важного случая кодов Рида - Соломона (или любого кода с максимальным расстоянием) аналитическое решение известно. Настоящий параграф служит введением в эту задачу. В нем получена формула числа кодовых слов каждого веса для кода с максимальным расстоянием. В случае произвольного линейного кода такую формулу мы дать не сможем, но некоторые общие соображения приведем. Будет выведено тождество Мак-Вильямс, связывающее распределение весов кода с распределением весов дуального кода. Тождество Мак-Вильямс полезно в тех случаях, когда дуальный код достаточно мал, так что его распределение весов можно найти на ЭВМ.

Начнем с точного решения задачи для кодов с максимальным расстоянием.

Теорема 14.1.1. В коде с максимальным расстоянием любое множество k позиций может быть выбрано как множество информационных позиций; значения символов в них выбираются произвольным образом в GF (q). В оставшихся п - k позициях выбор символов определяется правилом кодирования.

Доказательство. Код с минимальным расстоянием d * может восстанавливать любые d * - 1 стертых символов. Так как для кодов с максимальным расстоянием d*= п - k -\- \, то теорема доказана. □

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

Для кодов с максимальным расстоянием легко вычислить число кодовых слов веса d *. Разобьем множество целых чисел от О до п - 1 на два непересекающихся подмножества Td* и

Td*, где Td* состоит из d* целых чисел. Существует ( ] способов такого разбиения. Рассмотрим все кодовые слова, имеющие нули в тех позициях, которые принадлежат Т. Любое множество k = п -d* + \ позиций в слове кода с максимальным расстоянием однозначно определяет это кодовое слово. Выберем в качестве п -d* + \ информационных позиций п - d* позиций, принад-

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

Теорема 14.1.2. Распределение весов (п, к)-кода над GF (q) с максимальным расстоянием определяется формулами Ло = 1. Ai = О при /=*=!, .... d* - I и

Ai=("){ql) L(-iy(/)9-"-

при 1 d*.

Доказательство. При / < d* теорема очевидна. Дальнейшее доказательство распадается на три шага.

Шаг 1. Разобьем совокупность целых чисел от О до п - 1 на два непересекающихся подмножества Т\ и Тр где Т, состоит из / целых чисел, и будем рассматривать лишь те кодовые слова, которые содержат нулевые компоненты в позициях с номерами из Т\ и ненулевые компоненты во всех других позициях. Пусть Mi - число таких кодовых слов веса /. Для произвольного кода

Ai=[]]Mi;

поэтому необходимо лишь доказать, что

Mi = {q- 1) 2 {-\)l[-)q--l.

Чтобы доказать это равенство, установим одно неявное соотношение, связывающее Mi и Mf при меньших/, и/, больших d*.

лежащих Г,, плюс одну дополнительную позицию. В этой дополнительной позиции символ может принимать одно из q значений, и тогда символы в оставшихся d* - 1 позициях определены. Следовательно, существует точно q кодовых слов, у которых в заданных п - d* позициях стоят нули. Одно из них - нулевое кодовое слово, aq - 1 слов имеют вес, равный d*. Так как п - d* нулевых позиций, принадлежащих Т,, могут быть выбраны

[ ) способами, то получим

S (;,)Мр = <7~+1-1.

l=d»

Это неявное соотношение рекуррентно связывает Md*+\ с М.,*, Md*-f-2 с Md* и Md*-fi и т. д. Разрешив это рекуррентное соотношение, мы получим явную формулу дляМг.

Шаг 2. Запишем равенства в формулировке теоремы в более удобном для доказательства виде. Чтобы с суммой, входящей в последнее из этих равенств, можно было бы обращаться как с многочленом, будем рассматривать q как неопределенную переменную. Введем оператор f ]:

n=-Ni

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

= (<7-1)

Дополнительные слагаемые, включенные в эту сумму, соответствуют отрицательным степеням 9 и не вносят вклад в Mi. Свернем ее, используя формулу бинома Ньютона:

М, = (<7-1) [<7<-"(7-1)-1-

Выберем совокупность п - d* -\- I информационных компонент следующим образом: будем считать информационными все п - I компонент, расположенных в принадлежащих Т\ позициях, а также любые I - d* + 1 компонент, расположенных в принадлежащих Ti позициях. Напомним, что компоненты, расположенные в позициях, принадлежащих равны нулю. Произвольным образом приписывая значения оставшимся I - d* -\- \ компонентам, получим q-*+ - 1 ненулевых кодовых слов, вес которых не превышает /.

В множестве / позиций, принадлежащих Т/, можно выбрать любое подмножество / позиций. Число кодовых слов веса / с ненулевыми компонентами в этих I позициях равно Mf. Следовательно,