Шаг 3. Покажем, что полученное на втором шаге выражение для Ml позволяет разрешить рекуррентное соотношение, выведенное на первом шаге:

Это и завершает доказательство. □

Следствие 14.1.3. Распределение весов (п, к)-кода над GF (q) с максимальным расстоянием дается соотношениями Ло = 1, Л, = О при I = 1, d* - \ и

Л=(П Т {-\)i[\]{q-*+--\)

при 1 d*.

Доказательство. Воспользуемся тождеством

(Г)+(;:;

и перепишем доказываемое равенство в виде I-,

А=(:) д(-1)(Г)+(;:;)](---)-=(:)[Т(-1)(7)(«---)-

i-d*+i -1

- Т (-1)--(; ,)(9-*+---1)

=(;)¥(-!)( 7 )(?-1)?---

Последнее равенство вытекает из теоремы 14.1.2.

l-d*

□

Рис. 14.1. Распределение весов (31, 15)-кода Рида-Соломона.

Следствие 14.1.3 полезно при нахождении распределения весов кодов Рида - Соломона, например распределения весов (31, 15)-кода Рида-Соломона, приведенного на рис. 14.1. Даже для таких кодов Рида - Соломона небольшой мощности число кодовых слов веса I может быть очень большим. Вот почему, вообще говоря, практически невозможно найти распределение весов кода простым перебором кодовых слов.

В случае кодов, не являющихся кодами с максимальным расстоянием, не существует правила, аналогичного теореме 14.1.2,

При небольших п распределение весов может быть найдено поиском на ЭВМ, но с ростом п этот метод быстро становится непрактичным.

В настоящее время наиболее сильным инструментом являются выражения, устанавливающие связь между распределением весов линейного кода и распределением весов его дуального кода - так называемые тождества Мак-Вильямс. Тождества Мак-Вильямс справедливы для любого линейного кода; они вытекают из векторной структуры линейного кода и из того факта, что дуальный коду код является ортогональным дополнением Прежде чем переходить к выводу тождеств Мак-Вильямс, мы должны вернуться к изучению абстрактных конечномерных векторных пространств, начатому в § 2.6. Необходимо ввести понятия пересечения и прямой суммы двух подпространств и доказать их некоторые свойства.

Пусть и а V - подпространства пространства FK Тогда и V называется пересечениси U и V и означает множество векторов, принадлежащих и U, и V; UQ)V называется прямой суммой и и V и означает множество всех линейных комбинаций аи + bv, где и и v принадлежат соответственно U и V, а а и b - скаляры. Как U С\ V, так и U®V являются подпространствами в F".

Теорема 14.1.4.

dim [и П V] + dim [U ф V] = dim lU] -f dim [V].

Доказательство. Базис подпространства U [] V состоит из dim lU n У]"векторов. Этот базис может быть расширен до базиса и добавлением dim [U] - dim [U f] V] базисных векторов и до базиса V добавлением dim IV] - dim [U fl V] базисных векторов. Все эти базисные векторы в совокупности образуют базис подпространства U @ V. Таким образом,

dim [U @ V] = dim lU Г\ V] +

+ dim W] - dim lU П V] + dim IV] - dim lU f] V],

откуда следует теорема. □

Теорема 14.1.5.

f/J- П = (f/ ©

Доказательство. Подпространство U содержится в U @ V, и поэтому (U ф содержится в U--. Аналогично (U @ V)- содержится в V-. Следовательно, (U © V) содержится в (] [] V-.C другой стороны, запишем элемент из U @ V как аи + bv и обозначим через w любой элемент из U->- [] V. Тогда w-(ai\ + + bv) = О, и, следовательно, П содержится в ([/ ф У)-Отсюда следует, что эти два множества совпадают. □