8.8. КОДЫ ГОППЫ

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

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

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

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

Теорема 8.8.3. Минимальное расстояние и размерность кода Гоппы с многочленом Гоппы степени 21 удовлетворяют неравенствам

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

Как следует из определения 8.8.1, длинами кодов Гоппы могут быть только те числа, которые являются делителями Однако все укорочения и удлинения кодов Гоппы также принято называть кодами Гоппы. Для построения кодов Гоппы с длинами, равными можно использовать описанную в § 8.4 процедуру удлинения кода, согласно которой с каждой стороны кодового слова дописывается по одному у-ичному символу. В принципе можно строить и более длинные коды Гоппы, приписывая с каждой стороны кодового слова <ут-ичные представления символов так, как это делалось в § 8.5 при расширении кодов БЧХ, Будучи подклассом класса альтернантных кодов, класс кодов Гоппы сохраняет то свойство, что он содержит много кодов, минимальное расстояние которых много больше Однако так же, как и в общем случае альтернаитных кодов, мало что известно о построении хороших кодов Гоппы. Аналогично в случае общих кодов Гоппы не известны ни хорошие алгоритмы кодирования, ни хорошие алгоритмы декодирования, реализующие минимальное расстояние кода. Известные коды Гоппы интересны прежде всего тем, что позволяют дополнить код БЧХ в узком смысле еще одним информационным символом, а другие коды расширить даже на большее число символов. Иначе говоря, известные хорошие коды Гоппы хороши не в смысле описываемых теоремой 8.7.1 возможностей, а в некотором ином смысле.

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

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

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

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

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

Так как степень многочлена равна а степень многочлена в левой части этого равенства не превосходит то степень многочлена не превосходит . Таким образом, при Рассмотрим это неравенство в точке

или

или

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

так, что

и

Наконец, заметим, что так как при то по модулю при таким образом, условие теоремы эквивалентно условию, определяющему код Гоппы в узком смысле:

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

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

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

где пробегает все элементы поля

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

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

где локатор единицы в кодовом слове число единиц в кодовом слове.

Теорема 8.8.6. Если определяющий двоичный код Гоппы в узком смысле многочлен Гоппы не имеет корней в поле то вектор с является кодовым словом тогда и только тогда, когда формальная производная многочлена, взаимного к локаторному, делится на

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

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

Заметим, что в любом расширении поля формальная производная произвольного многочлена является полным квадратом, так как нечетные степени в ней пропадают. Предположим, что имеется сепарабельный код Гоппы с многочленом Тогда не только делит но и должен делить так как является полным квадратом. В самом деле, мы получим тот же самый код, если в качестве многочлена Гоппы выберем вместо Но степень этого многочлена равна и, таким образом,

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

и

где - степень многочлена Теперь для того же кода и тех же характеристик мы имеем проверочных частот, и можно непосредственно использовать все известные алгоритмы декодирования.

Наименьшим кодом Гоппы является двоичный -код Гоппы. Выберем Корни этого многочлена различны и лежат в или в некотором расширении следовательно, не могут лежать в Таким образом, может быть выбран для построения кода Гоппы длины 8 по меньшей мере с двумя информационными символами и с минимальным расстоянием, равным по меньшей мере 5. Ниже мы увидим, что число информационных символов равно в точности двум. Для описания этого кода сначала воспользуемся определением 8.8.1, а затем дадим его описание в частотной области, основанное на теореме 8.8.2.

Так как и то Далее, и Многочлены и можно вычислить по многочленам и при помощи алгоритма Евклида.

Проверочными частотами являются и и выполняются равенства Вместе с уравнением

это дает

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

Рис. 8.12. Кодер для -кода Гоппы.

Если положить в качестве выбрать произвольные элементы поля а символ удлинения взять равным сумме то все уравнения будут удовлетворяться. Таким образом, имеются в точности два информационных символа. Кодер для такого кода в частотной области показан на рис. 8.12.

Согласно теореме 8.8.2, тот же самый код можно получить кодированием во временной области. Проверочная матрица кода задается элементами так что

где первый столбец дописан для построения расширенного -кода. Заменяя каждый элемент поля его -битовым представлением, получаем

Так как строки этой матрицы линейно независимы то она задает -код.

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

Согласно теореме 8.8.2, выбор в качестве многочлена Гоппы или приводит к -коду Гоппы или расширенному -коду Гоппы. -код Гоппы ничем не лучше -кода БЧХ, за исключением того, что его можно расширить до -кода, гогда как код БЧХ расширить нельзя Квадрат многочлена равен и обращения многочленов Гонны соответственно равны

В рассматриваемом примере введем информацию непосредственно в спектр. Тогда профильтрованный спектр дается равенствами

а проверочными частотами являются частоты с индексами к Выписывая эти равенства совместное граничными синдромами получаем

Любые над удовлетворяющие условиям сопряженности выписанным уравнениям.

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

(см. скан)

Рассмотрим решение этой системы во всех подробностях. Сначала возведем в квадрат третье уравнение и разрешим его относительно

(см. скан)

Воспользуемся этим равенством, чтобы исключить из остальных пяти уравнений:

(см. скан)

Четвертое уравнение совпадает со вторым и может быть отброшено. Сложим второе уравнение, третье уравнение и возведенное в квадрат третье уравнение. Это дает

Подставляя это значение для получаем следующие четыре уравнения:

Возведем последнее уравнение в четвертую степень и сравним результат со вторым уравнением. Это показывает, что и что четвертое уравнение можно отбросить. Прибавим восьмую степень третьего уравнения к третьему уравнению. Это дает в точности второе уравнение, так что его можно отбросить. Итак, остались два уравнения:

Возводя первое уравнение в шестнадцатую степень, получаем

Подстановка этого выражения в последнее уравнение дает

Возведение этого равенства в шестнадцатую степень приводит к уравнению

из которого следует, что равно нулю или единице.

Итак, мы пришли к следующему правилу: и являются произвольными элементами поля являются произвольными элементами поля определяются следующими уравнениями:

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