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

Код БЧХ длины над представляет собой ограничение на подполе кода Рида-Соломона над нолем Иными словами, код БЧХ состоит из всех -значных слов кода Рида-Соломона. Поэтому минимальное расстояние кода БЧХ по меньшей мере равно минимальному расстоянию исходного кода Рида-Соломона. К сожалению, коды БЧХ большой длины с большим минимальным расстоянием не содержат нужного нам числа кодовых слов. Точнее говоря, в любой последовательности кодов БЧХ растущей длины с ограниченной скоростью (все коды последовательности удовлетворяют условию для некоторого фиксированного нормированное минимальное расстояние стремится к нулю с ростом Исходный код

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

Альтернантные коды представляют собой класс линейных кодов, которые строятся из кодов БЧХ таким образом, чтобы при фиксированной скорости получить (хотя бы в принципе) большее минимальное расстояние. Пусть Выберем и зафиксируем над -мерный вектор с ненулевыми компонентами и назовем его шаблоном (во временнбй области). Выберем также код Рида-Соломона над с конструктивным расстоянием Альтернативный код состоит из всех -значных векторов с, таких, что вектор с компонентами является словом кода Рида—Соломона.

Чтобы определить этот же код иначе, допустим, что все отличны от нуля, и положим Для каждого кодового слова с кода Рида-Соломона образуем вектор с компонентами Если вектор с является -значным, то он принадлежит альтернантному коду. Альтернантный код определяется как множество всех -значных слов, которые могут быть получены таким способом

Обычно выбирается шаблон все компоненты которого отличны от нуля; но если какие-то компоненты шаблона равны нулю, то и кодовое слово содержит нуль в этих компонентах. Нулевые компоненты кодового слова не содержат никакой информации и просто не передаются Если алгоритм декодирования основан на полном слове, то в случае необходимости декодер может восстановить эти пропущенные нулевые компоненты.

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

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

Так как все компоненты отличны от нуля, то вектор обратим, т. е. существует вектор G (преобразование вектора такой, что представляет собой дельта-функцию. (Если , то в противном случае

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

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

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

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

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

и

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

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

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

Теорема 8.6.2. Пусть С представляет собой линейный -код над а С является его ограничением на подполе с параметрами Тогда

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

Следствие 8.6.3. Размерность альтернантного кода с конструктивным расстоянием удовлетворяет неравенству

Доказательство. Использовать теорему 8.6.2 и равенство

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

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

Теорема 8.6.4. Если вектор с содержит не более ненулевых компонент и если профильтрованный спектр равен нулю в некоторых последовательных компонентах для всех где обратимый фильтр.

Доказательство. Многочлен локаторов был определен таким образом, что компоненты его преобразования равны нулю, если Тогда — 0 и отсюда следует, что Следовательно, Но отличен от нуля только на блоке, длина которого не превышает равно нулю на блоке длины Поэтому таким образом, Следовательно, с — нулевой вектор.