для m = о, п. Во второй части мы докажем, что это равенство эквивалентно утверждению теоремы.

Часть 1. Для заданного т разобьем целые числа от О до п - 1 на два непересекающихся подмножества Тт и Тт, где подмножество r„j состоит из т элементов. Пусть V образует т-мерное подпространство векторного пространства GF" (q), состоящее из всех векторов с нулевыми компонентами в позициях с номерами из Тогда является (п - /п)-мерным подпространством, состоящим из всех векторов с нулевыми компонентами в позициях с номерами из Т„.

В силу теоремы 14.1.5

{W П y)J- =g-L ©1/-L;

поэтому

dim [-L © = п - dim [W П V]. С другой стороны, по теореме 14.1.4

dim [-L ф = {n-k) + in-m)- dim [J- П У]-

Из этих равенств следует, что

dim[gJ- П V-L] = dim[ {\V] + n-k-m.

Теперь заметим, что при каждом выборе Г„ существует qA{&{]V] векторов вё [\Ум q" "Il векторов в П У-

Пусть Ai, I = О, п, и Bi, / = О, п, представляют собой распределения весов линейного кода и его дуального кода соответственно. Определим нумераторы весов кода равенствами

Л (X) = S Aix и В{х)= ti BixK

1=0 1=0

Следующая теорема связывает эти два многочлена и позволяет вычислить один из них, если известен другой.

Теорема 14.1.6. Нумератор весов А (х) линейного (п, к)-кода над OF (q) и нумератор весов В (х) дуального ему кода связаны соотношением

qBix) = [l+iql)xrA{ ,.4-). )

Доказательство. Рассмотрим код W и дуальный ему код W. Доказательство состоит из двух частей. В первой части мы докажем, что

Аналогично можно сосчитать векторы в П V. Тогда предыдущее равенство переходит в равенство

Так как т произвольно, первая часть доказательства завершена.

Часть 2. Исходя из выводов первой части, запишем тождество для многочленов

Переменим порядок суммирования

i=0 m=0 /=0 т=0

ассмотрим {Tj,,} - совокупность всех таких Г. Пересчитаем екторы в каждом W [] V, которые могут быть получены из некоторого подмножества Т™, принадлежащего совокупности \Т}. Число пересчитанных векторов равно Т {т)Я" \ причем многие из них входят в подсчет несколько раз. Аналогично пересчитав все векторы в каждом П V, которое получается из принадлежащего {Т}, имеем

Чтобы завершить первую часть доказательства, необходимо оценить две суммы, входящие в это равенство. Для этого сосчитаем, сколько раз вектор веса /, принадлежащий W, появится в множестве W [] V. Указанный вектор принадлежит W [] V тогда и только тогда, когда эти его / позиций входят в число тех т позиций принадлежащих V векторов, в которых допускаются ненулевые компоненты, или, что эквивалентно, если п - т позиций, в которых принадлежащие V векторы должны содержать нулевые компоненты, попадают в « - / позиций кодового слова, содержащие нулевые компоненты. Выбрать п - т позиций,

которые содержат нулевые компоненты, можно спосо-

бами; поэтому данное кодовое слово веса / входит в мно-

жеств. Существует Aj кодовых слов веса /. Поэтому

(п-{ \ j = О, если т > п - L Используя формулу

бинома Ньютона, имеем

S Б, (1 + г/)"- = <7«- S Aj (y/qni + д/у)-/. Наконец, сделав подстановку у = 1/х - 1, получим

1=0 /=0

д 2 Вгх = (1 -Ь (Я - 1) X)" t ir+Wy

г=0 /=0

ЧТО завершает доказательство теоремы. □

В заключение параграфа укажем на простое применение этой теоремы. Из табл. 1.1 следует, что распределение весов (7,4)-кода Хэмминга равно

(Ло, Ах, Л,) = (1, О, О, 7, 7, О, О, 1),

так что нумератор весов имеет вид

А (х) = ~Ь 7x* +7x= + 1.

Соответствующий дуальный код - это двоичный циклический код, известный под названием симплексного. Корнями его порождающего многочлена

g(x) = х+х +х + 1

являются а" и а. Согласно теореме 14.1.6, нумератор весов В (х) симплексного кода удовлетворяет равенству

2*5 (х) = (I -f Л) Л [(1 - х)/{1 +х)] =

= {1-ху +7 (1 + хУ (1 -хУ +7 {I + xY (1 - xf +

+ (1 + х)\

откуда следует, что

В (х) = 7х + 1.

Симплексный (7,3)-код имеет одно кодовое слово веса О и семь кодовых слов веса 4.