Загрузка оЭной из

конфигураций, зайаюцих

йеоичное коЭовое слово

&.«. коды гоппы 271

Степень многочлена Гоппы равна гг ; число ошвойов равно

Спектральный регистр

Обратное преобразование Фурье

Регистр „ койоеого слова канол

Рис. 8.11. Частотный кодер для кода Гоппы.

одическим. После этого кодовое слово получается обратным преобразованием Фурье спектра.

Другое описание кодов Гоппы дается следующей теоремой.

Теорема 8.8.4. Код Гоппы в узком смысле над GF (д) длины п ~ д-1, задаваемый многочленом Гоппы G (х), состоит из

всех векторов с = (со.....c„ i) над GF (д), удовлетворяющих

условию

S С, П (л: - а-) = О (mod G {х)).

1=0 i<j=i

Доказательство. Перепишем условие теоремы в виде

d и {х- а-) = А {x)G(x).

Так как степень многочлена G (х) равна 2t, а степень многочлена в левой части этого равенства не превосходит п - 1, то степень многочлена А (х) не превосходит п ~ 2t - 1. Таким образом, Л] = О при f п - 2t, и - 1. Рассмотрим это неравенство в точке X = а-:

Сг П {a- - а-) = А (а") G {а-%

(а-)«-1 П (1 -«-(•-•))] = Л («-•) G («-),

272 гл. 8. КОДЫ; СПЕКТРАЛЬНЫЕ МЕТОДЫ ИЛИ

Сга« П (1 - а") Л (а-) G («-).

Определим теперь

Т{х)=Т1(1- а*)-1 хА {X) (mod х" - 1)

так, что

Т (а-) = П (1 - а*)-1 [а-А (а-)]

Ci = Т (cc-i) G (cc-i).

Наконец, заметим, что так как Aj - О при j - п - 2t, п - 1, то Tj = О по модулю п при t = п - 2t -\~ I, и, и, таким образом, условие теоремы эквивалентно условию, определяющему код Гоппы в узком смысле:

С(х) = Т (х) G (х) (mod х" - 1),

что и завершает доказательство теоремы. □

Описываемая теоремой 8.8.4 форма задания кода Гоппы допускает удлинение кода на один символ - до кода длины д"*. Надо просто добавить одну компоненту, приписывая ей локатор, равный нулевому элементу поля. Таким образом мы получаем следующее альтернативное определение.

Определение 8.8.5. Код Гоппы над GF (q) длины п = q, задаваемый многочленом Гоппы G (х), является множеством всех векторов с = (со, c„ i) над GF (q), удовлетворяющих условию

I Ci П {х- pfO = О (mode(4),

где пробегает все элементы поля GF {q).

Вернемся теперь к частному случаю двоичных кодов Гоппы, ограничиваясь только случаем, когда многочлен Гоппы не имеет кратных корней ни в одном расширении. Такие коды Гоппы называются сепарабельными. Как мы увидим, минимальное расстояние сепарабельных двоичных кодов Гоппы равно 2г + 1, где г - степень многочлена Гоппы. Это намного лучше, чем граница для произвольных кодов Гоппы, согласно которой d* г -\- I. Ключом к доказательству этого утверждения является следующая теорема, накладывающая ограничения на многочлен, взаимный

8.8 КОДЫ ГОППЫ 273

к локаторному многочлену. Многочлен, взаимный к локаторному, определяется равенством

где Pi - локатор i-й единицы в кодовом слове с, а v - число единиц в кодовом слове.

Теорема 8.8.6. Если определяющий двоичный код Гоппы в узком смысле многочлен ГоппыС (х) не имеет корней в поле GF (2"), то вектор с является кодовым словом тогда и только тогда, когда формальная производная (х) многочлена, взаимного к локаторному, делится на G (х).

Доказательство. Формальная производная многочлена, взаимного к локаторному, равна

ЛИ)= t П {X

Поскольку код является двоичным, то с. равны нулю или единице, так что это выражение для (х) следует из формулы, приведенной в теореме 8.8.4. □

Заметим, что в любом расширении поля GF (2) формальная производная произвольного многочлена является полным квадратом, так как нечетные степени в ней пропадают. Предположим, что имеется сепарабельный код Гоппы с многочленом G (х). Тогда не только G (л:) делит К (х), но и G (л:) должен делить Ас (х), так как (х) является полным квадратом. В самом деле, мы получим тот же самый код, если в качестве многочлена Гоппы выберем G (х) = G (х) вместо G (х). Но степень этого многочлена равна 2г, и, таким образом, d* 2г -\- I.

Хотя минимальное расстояние сепарабельного кода Гоппы не меньше 2г + 1, определение 8.8.1 вводит только г, а не 2г синдромов, и обычные методы декодирования непосредственно не применимы. Для данного случая можно было бы предложить специальный вариант алгоритма декодирования, использующего только г синдромов. Вместо этого мы модифицируем описание кода так, чтобы были непосредственно пригодньГопиеанные в гл .7 и 9 алгоритмы декодирования. Это можно сделать, не меняя самого кода, а только описывая его другим образом: вместо G (л:) в качестве многочлена Гоппы надо выбрать G (л:). Получится тот же самый код, но границы для характеристик преобразуются к следующему виду:

г -f 1 = 2г + 1