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

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

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

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

Теорема 8.7.1. Пусть для некоторых и пусть некоторые целые числа, удовлетворяющие неравенству

Тогда существует альтернантный

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

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

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

Выберем над вектор веса Всего имеется векторов веса и

векторов веса меньше

(iii) Так как любые компонент кода Рида-Соломона полностью определяют кодовый вектор, то вектор веса может принадлежать не более чем определенным в альтернантным кодам. Действительно, при фиксированном в векторе можно независимо выбрать только компонент так, чтобы вектор принадлежал G.

(iv) Теперь скомбинируем Согласно число альтернантных кодов равно Максимальное число кодов, которые могут содержать вектор веса меньше равно Предположим, что

Тогда некоторый код с числом информационных символов имеет минимальное расстояние не меньше Это эквивалентно утверждению теоремы.

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

Пусть равно 2. Тогда теорема 8.7.1 утверждает существование двоичных альтернантных кодов, удовлетворяющих условию

Граница для левой части этого неравенства, но в противоположную сторону уже была получена в лемме 7.9.2. Ниже (в гл. 14) мы рассмотрим оценки биномиальных коэффициентов по формуле Стирлинга. Применяя оценку из теоремы 14.4.1, имеем

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

Очень важно, что это неравенство связывает только величины и что оно имеет ненулевые решения. Следовательно, нами

получено сильное утверждение о существовании асимптотически хороших альтернантных кодов.

Полученная форма границы эквивалентна границе, известной под названием границы Гилберта, которая была выведена на много лет раньше, чем были построены альтернантные коды. Гранина Гилберта утверждает существование хороших (в данном понимании) кодов, и, таким образом, альтернантные коды образуют класс кодов, реализующих это утверждение. Ситуация такова, что в настоящее время нет каких-либо определенных свидетельств существования двоичных кодов, асимптотически лучших, чем предписывает граница Гилберта. Следовательно, очень правдоподобно, что асимптотически оптимальные коды принадлежат классу альтернантных кодов. Однако класс альтернантных кодов весьма обширен, и, чтобы реализовать приведенную в теореме 8.7.1 границу, необходимо разработать конструктивные методы выделения хороших кодов. Хотя, согласно указанной в теореме 8.7.1 границе, альтернантные коды лучше введенных в § 7.9 кодов Юстесена, тем не менее коды Юстесена задаются точной конструкцией, а как точно указать хороший альтернантный код большой длины, пока еще неизвестно.