4.7. Коды Гоппы

4.7.1. Определение

Коды Гоппы представляют собой очень широкий класс линейных кодов, включающий все БЧХ-коды. Известно, что среди этих кодов есть коды, лежащие на границе Варшамова — Гилберта. Однако такие коды не задаются конструктивно. Для кодов Гоппы в области «конструктивных расстояний» известны алгебраические методы декодирования, подобные методам декодирования БЧХ-кодов. Коды Гоппы — это один из важнейших классов линейных кодов, не являющихся, вообще говоря, циклическими,

При рассмотрении кодов Гоппы будем следовать работе [53], ограничившись случаем двоичных кодов. Пусть множество элементов поля Обозначим через V -мерное векторное пространство над Вектору сопоставим рациональную функцию переменного будет принимать значения в

Пусть многочлен от с коэффициентами из среди корней которого нет элементов из Код Гоппы, задаваемый парой определяется следующим образом:

Многочлен называется многочленом Гоппы. Очевидно, что введенный код является линейным. Пусть множество индексов компонент вектора равных единице. Пусть

Тогда, как указывалось в разд. 2.6.6, можно представить в виде

где производная

Для любого справедливо следующее соотношение:

Заметим, что правая часть последнего уравнения является многочленом степени степень многочлена

Используя (4.47), условие из (4.44) можно переписать в следующем виде:

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

следующего равенства:

Пусть Без ограничения общности будем считать, что Приравнивая суммы коэффициентов при в (4.48) нулю, получим систему из линейных уравнений относительно Матрица коэффициентов этой системы имеет вид

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

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

В частности, если элемент порядка поля то

Если заменить на и поменять порядок следования строк на противоположный, то можно легко увидеть, что эта матрица является не чем иным, как проверочной матрицей БЧХ-кода с . Следовательно, класс кодов Гоппы включает БЧХ-коды с .

Пусть - многочлен минимальной степени, являющийся полным квадратом [т. е. имеющий вид ], такой, что Если вектор, принадлежащий коду Гоппы, то, согласно формулам (4.44) и (4.46),

Поэтому

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

Так как то из последнего соотношения получаем оценку снизу для минимального веса

Если все корни различны, то и в этом случае

Для задания кода Гоппы нужно задать Однако код Гоппы можно также определить, если вместо задать произвольным образом вектор . Действительно, в этом случае многочлен минимальной степени, такой, что определяется единственным образом. Матрица Я кода Гоппы,

задаваемого этим многочленом, имеет вид

Утверждение 4.27 [53]. Пусть элемент порядка поля и пусть Если код Гоппы, определяемый этим множеством является циклическим, то он представляет собой БЧХ-код.

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

Так как при всех вектор является кодовым вектором, то из формулы (4.52) получаем

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

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

Пример 4.15 [56]. Пусть а — примитивный элемент . В этом случае длина кода равна и многочлен Гоппы не имеет корней в . В частности, рассмотрим случай, когда является неприводимым многочленом над степени Корни в этом случае принадлежат Из формул (4.51) и (4.55) имеем

Аналогичные оценки имеют место и для параметров примитивных БЧХ-кодов длины однако длина кодов Гоппы на единицу больше.

Предположим, что для представления кодового вектора используется многочлен над такой, что

Далее вместо векторного представления будем использовать представление многочленами (для простоты многочлен будем обозначать через Используя проверочную матрицу (4.50), получаем

Рассмотрим расширение этого кода Гоппы. Обозначим добавленный символ индексом Полагая имеем

Если условиться, что в формуле при то можно считать, что X в (4.56) пробегает все элементы Но тогда, согласно равенству (4.57),

Из формул (4.56) и (4.58) имеем

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

в случае согласно утверждению 2.12, произвольный неприводимый многочлен может быть получен из любого другого неприводимого многочлена с помощью аффинного преобразования (с точностью до постоянного множителя), то все расширенные коды Гоппы с параметрами попарно эквивалентны. Без ограничения общности (см. утверждение 2.10) будем считать, что Если у — корень уравнения то также являются корнями этого уравнения. Следовательно, код инвариантен относительно аффинных преобразований

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

то

Следовательно, необходимым условием того, что имеет стационарную точку, является принадлежность собственных

значений и матрицы с полю Итак, согласно вышеизложенному, чтобы показать, что является циклическим преобразованием, следует доказать, что где X — собственное значение матрицы является корнем уравнения и принадлежит Пусть у — элемент порядка и пусть как то Если записать равенство в виде

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

Утверждение 4.28. Необходимым условием существования среди элементов множества решения уравнения является принадлежность корня уравнения

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

Но тогда, как следует из утверждений 2.10 и 2.11, если одно из уравнений имеет корень в то и другое также имеет корень в

Утверждение 4.29 [54]. Рассмотрим подкласс кодов Гоппы длины для которых а многочлены Гоппы неприводимые многочлены над Для любого любого целого в этом подклассе существует код Гоппы с любым наперед заданным минимальным расстоянием , удовлетворяющим неравенству

Идея доказательства. Доказательство почти аналогично доказательству утверждений 3.19 и 3.20.