{q - 1)"- I ("] (q - Предположим, что

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

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

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

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

мы рассмотрим оценки биномиальных коэффициентов по формуле Стирлинга. Применяя оценку из теоремы 14.4.1, имеем

I (:)<(;) 2"[-<)-<(т,

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

- idin) log {din) - (1 - din) log (1 - din) <l~R.

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

(iii) Так как любые п - г компонент кода Рида-СоЛомо)на полностью определяют кодовый вектор, то вектор v веса / может принадлежать не более чем (д™ - 1)"- определенным в п. (i) альтернантным кодам. Действительно, при фиксированном v в векторе h можно независимо выбрать только п - г компонент так, чтобы вектор hv принадлежал G.

(iv) Теперь скомбинируем п. (i), (ii) и (iii). Согласно (i), число альтернантных кодов равно (q" - 1)". Максимальное число кодов, которые могут содержать вектор веса меньше d, равно

коды гоппУ 2бд

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

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

8.8. КОДЫ ГОППЫ

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

Определение 8.8.1. Кодом Гоппы с конструктивным расстоянием d называется альтернантный код с конструктивным расстоянием d, у которого обращение частотного шаблона G имеет ширину d. Иначе говоря, обращение частотногошаблона задается многочленом G (х) степени d-1, который называется многочленом Гоппы. Кодом Гоппы в узком смысле называется код Гоппы с 2t проверочными частотами с локаторами а"-2+, а«-2+2, ао.

Теорема 8.8.2. Вектор с является кодовым для кода Гоппы с многочленом Гоппы G (х) тогда и только тогда, когда

Е Ci [ai/G(а-)] = 0, j = О, ..., 2t - I.

Доказательство вытекает непосредственно из теоремы о свертке. □

Теорема 8.8.3. Минимальное расстояние d* и размерность k кода Гоппы с многочленом Гоппы степени 2t удовлетворяют неравенствам d* 2t \ , k п - 2tm.

) Это утверждение, конечно, не следует из того, что коды Гоппы являются подклассом класса альтернантных кодов, а нуждается в отдельном доказательстве; такое доказательство можно найти, например, в статье: Гоппа В. Д. На неприводимых кодах достигается пропускная способность ДСК. - Проблемы передачи информации, 1974, вып. 1, с. 111-112 и в монографии: Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки.- М.: Связь, 1979, с. П\-П2. ~ Прим. перев.

Доказательство вытекает непосредственно из следствия 8.6.S. Q

Как следует из определения 8.8.1, длинами кодов Гоппы могут быть только те числа, которые являются делителями q - 1. Однако все укорочения и удлинения кодов Гоппы также принято называть кодами Гоппы. Для построения кодов Гоппы с длинами, равными q и д"" + 1, можно использовать описанную в § 8.4 процедуру удлинения кода, согласно которой с каждой стороны кодового слова дописывается по одному д-ичному символу. В принципе можно строить и более длинные коды Гоппы, приписывая с каждой стороны кодового слова "-ичные представления символов так, как это делалось в § 8.5 при расширении кодов БЧХ.

Будучи по;5,классом класса альтернантных кодов, класс кодов Гоппы сохраняет то свойство, что он содержит много кодов, минимальное расстояние которых много больше d Однако так же, как и в общем случае альтернантных кодов, мало что ;Известно о построении хороших кодов Гоппы. Аналогично в случае общих кодов Гоппы не известны ни хорошие алгоритмы кодирования, ни хорошие адгоритмы декодирования, реализующие минимальное расстояние кода. Известные коды Гоппы интересны прежде всего тем, что позволяют дополнить код БЧХ в узком смысле (/о = 1) еще одним информационным символом, а другие коды расширить даже на большее число символов. Иначе говоря, известные хорошие коды Гоппы хороши не в смысле описываемых теоремой 8.7.1 возможностей, а в некотором ином смысле.

В частотной области коды Гоппы допускают описание с помощью изображенного на рис. 8.11 устройства с регистром сдвига. Вместо стандартного введения информации во временную область информация вводится в частотную область - или в спектр или в профильтрованный спектр, как показано на рис. 8.11, причем в обоих случаях необходимо обеспечить выполнение ограничений сопряженности. Какие-либо общие методы практической реализации таких ограничений не известны, но для кодов умеренной мощности можно составить и решить систему алгебраических уравнений, описывающих эти ограничения. Ниже приводится пример такого решения. Содержащий информацию профильтрованный спектр пропускается через фильтр с конечным импульсным откликом, веса в отводах которого задаются многочленом Гоппы. Фильтр работает циклически: обращение ко входу является пери-