Так как все компоненты h отличны от нуля, то вектор Н обратим, X. е. существует вектор G (преобразование вектора {gt = hj, i = О, п - 1}), такой, что H*G представляет собой дельта-функцию. (Если / = О, то (H*G)j=l; в противном случае (H*G)y =0.)

Через многочлены эта свертка записывается так:

Н (х) G (х) 1 (mod X" - 1).

Если Н (х) - многочлен над малым полем GF {q), то и G (х) - многочлен над этим же полем. Для примитивных п это доказывается следующим образом. Многочлен Н (х) не имеет корней в поле GF (q"), так как Н (а-) = nhi Ф 0. Следовательно, И (х) взаимно прост с х"--1 = х""- - 1, и, согласно алгоритму Евклида, над GF (q) существуют такие G (х) и f (х), что

H(x)G{x) +{х"~- 1) F(x) = 1.

Следовательно,

Н (х) G (х) = 1 (mod х« - 1).

Альтернантные коды в частотной области можно определить следующим образом.

Определение 8.6.1. Пусть Н -фиксированный п-мерный вектор в частотной области, и пусть ]\ к t - фиксированные целые числа. Альтернантный код G (в частотной области) определяется как множество, содержащее каждый вектор с, преобразование С которого удовлетворяет следующим двум условиям:

1) S = 0, / = /о, .... /о -f- 2/ - 1,

2) Cft = Cgk)).

Первое из этих условий накладывает ограничение на свертку, которая в обычном определении во временной области задается в виде произведения многочленов; второе условие гарантирует GF ((7)-значность кодового слова во временной области. Вектор с компонентами:

ft=0

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

Из тесной взаимосвязи альтернантных кодов с кодами Рида- Соломона, очевидно, следует, что их минимальное расстояние не меньше конструктивного расстояния 2 -f- 1. Следующая теорема показывает, что их размерность также удовлетворяет условию kn ~ Шт.

Теорема 8.6.2. Пусть G представляет собой линейный (п, К, D)-Kod над GF (q"), а G является его ограничением на подполе OF (q) с параметрами (п, k, d). Тогда

D < d <: п и {п - К) <. {п ~ k) < т{п - К).

Доказательство. Нетривиальным является только последнее неравенство. Произвольное проверочное уравнение над OF (q), которому удовлетворяет код, приводит не более чем к т линейно независимым проверочным уравнениям над GF (q). Отсюда и вытекает последнее неравенство. □

Следствие 8.6.3. Размерность k альтернантного кода с конструктивным расстоянием 2t -f 1 удовлетворяет неравенству k >. п - 2to.*

Доказательство. Использовать теорему 8.6.2 и равенство п - К = 2t. □

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

Поучительно вывести границу БЧХ в частотной области для дистанционной структуры альтернантных кодов, наследуемой из кодов Рида-Соломона.

Теорема 8.6.4. Если вектор с содержит не более d - 1 ненулевых компонент и если профильтрованный спектр равен нулю в некоторых d - 1 последовательных компонентах (Т - О, k = = ko, ko d - 2), то Cj = О для всех i, где Т = Н*С, а Н - обратимый фильтр.

Доказательство. Многочлен локаторов Л {х) был определен таким образом, что компоненты его преобразования равны нулю, если Cj Ф 0. Тогда jCj = О и отсюда следует, что Л*С = = 0. Следовательно, Л* (Н * С) = Н * (Л * С) = 0. Но Л отличен от нуля только на блоке, длина которого не превышает d -~ \, а Н * С равно нулю на блоке длины d - 1. Поэтому Н * С = О, и, таким образом, С = 0. Следовательно, с - нулевой вектор.

8.7. ХАРАКТЕРИСТИКИ АЛЬТЕРНАНТНЫХ КОДОВ

Привлекательность альтернантных кодов объясняется тем, что в этом классе имеются хорошие коды большой длины. Под этим подразумевается, что существует последовательность кодов возрастающей длины, для которых скорость kin и нормированное минимальное расстояние d*ln отделены от нуля при бесконечном

ё.г. сАРАктЕРйстикй АльТЕРнАнтных кодов 267

Ёозрастании п. Докажем это. Метод доказательства сводится к демонстрации того, что число слов малого веса над GF (q) невелико и что каждое из них не может принадлежать слишком большому числу альтернантных кодов. А так как альтернантных кодов достаточно много, то какой-то из них не может содержать слов малого веса. Следовательно, этот код должен обладать большим минимальным расстоянием.

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

Теорема 8.7.1. Пусть п = q" - 1 для некоторых GF (q) и т, и пусть d и г - некоторые целые числа, удовлетворяющие неравенству

C)(9-iy<(r-ir-

Тогда существует альтернантный (п, п - тг, d)-Koh

Доказательство. Идея приводимого ниже доказательства состоит в подсчете числа альтернантных кодов некоторого определенного вида и последующем нахождении доли тех кодов, которые содержат заданный вектор v веса / < d. Оказывается, что векторов такого веса меньше, чем кодов рассматриваемого вида, так что некоторые из этих кодов не содержат векторов v веса / <d.

(i) Пусть G - код Рида-Соломона над GF (д") с конструктивным расстоянием г + I и К = п - г информационными символами, и пусть G (h) - альтернантный код над GF (q), порождаемый из G шаблоном h, где h - вектор над GF (q"), все компоненты которого отличны от нуля. Тогда

С (h) = {с С Of" (9): he ее},

где he- вектор с компонентами [hiCt, i = О, п- 1}. Поскольку hiO, то всего существует {q"-1)" таких кодов. Каждый из них представляет собой ограничение линейного кода {с GF"-{q"):hcG] на подполе GF (q), и, следовательно, согласно теореме 8.6,2, для каждого такого кода k п - тг.

(ii) Выберем над GF (q) вектор v веса / < d. Всего имеется

(у) (q - 1)/ векторов веса / и векторов веса меньше d.