12.2. АЛЬТЕРНАНТНЫЕ КОДЫ

Альтернантные коды тесно связаны с рассмотренными в § 10.8 обобщенными кодами Рида — Соломона — Для удобства напомним их определение. Пусть где различные элементы поля где ненулевые (но не обязательно различные) элементы из Тогда код состоит из всех векторов вида

где - любой многочлен с коэффициентами из степень которого не превосходит Код является -кодом МДР над для и его проверочная матрица равна:

где вектор таков, что и

Определение. Альтернантный код состоит из всех слов кода таких, что их компоненты лежат в поле иными словами, равен ограничению кода на подполе GF(q). Таким образом, состоит из всех векторов а над удовлетворяющих равенству для матрицы задаваемой условием (12.2).

Проверочная матрица элементы которой лежат в поле может быть получена заменой каждого элемента матрицы соответствующим вектором длины над GF(q) точно так же, как это было сделано для кодов БЧХ. Так как является ограничением кода на подполе, то из § 7.7 следует, что -код над параметры которого удовлетворяют условиям

(Свойства кода собраны на рис. 12.2). Приведенную оценку для можно получить непосредственно из проверочной матрицы.

Теорема 1. Минимальное расстояние кода не меньше чем

Доказательство. Предположим, что а — ненулевое слово кода вес которого не превосходит Тогда Положим Тогда так как матрица является диагональной и, следовательно, обратима. Таким образом, что невозможно, так как X — матрица Вандермонда (см. лемму 17 гл. 4).

Рис. 12.2 Свойства альтернантных кодов Пусть произвольная обратимая матрица. Тогда в равной степени хорошим заданием проверочной матрицы кода является матрица (см. упражнение (31)

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

Заметим, что из равенств (12 2) и (12.3) видно, что координаты кодового слова естественно занумеровать элементами

Это оказывается очень полезным при кодировании и декодировании.

Примеры (1). Выберем сначала где а — примитивный элемент поля Тогда проверочная матрица в форме (12.2) для альтернантного кода равна:

Заменяя каждый элемент матрицы соответствующим двоичным вектором длины 3, получаем:

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

Вторая строка матрицы избыточна, так как если

где равны нулю или единице, то

Таким образом, можно положить

и в этом случае представляет собой [7, 4, 3]-код Хэмминга. (В данном случае роль вектора у сводится к уменьшению минимального расстояния и увеличению числа информационных символов.)

(2). Другим примером альтернантных кодов являются коды БЧХ. Действительно, проверочная матрица кода БЧХ в общем виде задается равенством (см. уравнение (7.19))

и, следовательно, код является альтернантным.

Код, дуальный альтернантному.

Теорема 2. Дуальным альтернантному коду является код

Напомним, что согласно определению, данному в § 7.7, след произвольного кода над является кодом над состоящим из всех векторов вида

где

Доказательство. Утверждение вытекает из теоремы II гл. 7 и теоремы 4 гл. 10.

Примеры применения этой теоремы можно найти по аналогии с теоремой 11 гл. 7.

Длинные альтернантные коды являются хорошими.

Теорема Пусть числа заданы, и пусть некоторое число, делящее Тогда существует альтернантный код над GF(q) с параметрами удовлетворяющий условию

(b). Следовательно, существуют длинные альтернантные коды, лежащие на границе Варшамова — Гилберта.

Доказательство, (i) Пусть а — произвольный ненулевой вектор над GF(q). При фиксированных и а и переменном число кодов содержащих этот вектор а, равно самое большее Чтобы доказать это, заметим, что согласно (12.1) вектор а принадлежит коду тогда и только тогда, когда для всех для некоторого

многочлена степень которого меньше, чем Так как полностью определяется своими значениями в точках, то для определения достаточно задать самое большее величин Для каждой имеется способов такого задания.

(ii). Рассмотрим семейство альтернантных кодов являющихся ограничениями некоторых кодов на подполе где Тогда размерность каждого не меньше чем Согласно число различных кодов содержащих заданный вектор а, равно самое большее Следовательно, число кодов минимальное расстояние которых строго меньше чем равно самое большее

(iii). Мощность множества равна т. е. числу различных выборов вектора Таким образом, если это число превосходит значение (12.7), то найдется код размерность которого не меньше и минимальное расстояние которого не меньше Это доказывает утверждение (а). Асимптотически, когда велико, а отношение фиксировано, условие (12.6) совпадает с границей Варшамова — Гилберта (теорема 12 гл. 1, теорема 30 гл. 17).

Ясно, что теорема 3 не отвечает на вопрос, какой альтернантный код является наилучшим, а только гарантирует существование хорошего кода в этом классе. Так как класс альтернантных кодов очень велик, то полезно выделить в нем некоторые подклассы. В следующих параграфах мы описываем такие подклассы, известные как коды Гоппы, коды Сривэставы и обобщения Ченя — кодов БЧХ. Эти подклассы получаются путем наложения некоторых ограничений на вектор а, или вектор или сразу на оба вектора.

Упражнение. (1). Рассмотреть двоичный альтернантный код длины 6, у которого где а — примитивный элемент поля все равны Показать, что он является -кодом.