5.5. КОДЫ ХЭММИНГА КАК ЦИКЛИЧЕСКИЕ КОДЫ

Порождающий многочлен -кода Хэмминга, использованного в начале главы, равен Корнем этого многочлена является примитивный элемент а поля и, следовательно, все кодовые слова удовлетворяют равенству с Аналогично, чтобы получить код Хэмминга с примитивной длиной выберем так, чтобы примитивный элемент а поля был его корнем, а имепио положим равным минимальному многочлену элемента а, используемому для построения ноля Тогда так как с то с для каждого кодового слова. Это эквивалентно равенству где

Для больших алфавитов также существуют коды Хэмминга. В § 3.4 мы видели, что для каждого существует код Хэмминга над полем В данном параграфе мы покажем, что многие из этих кодов (хотя и не все) являются циклическими, выписав их порождающие многочлены.

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

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

где многочлен содержит не более одного ненулевого коэффициента, так что или Целое число маркирует позицию, в которой произошла ошибка. Для маркировки ошибочных позиций мы будем также использовать поле Элемент поля а соответствует компоненте с номером Так как то и все степени а от 0 до различны. Таким образом, по величине сразу определяется позиция ошибки, за исключением случая соответствующего отсутствию ошибки. Следовательно, рассматриваемый код является исправляющим одиночную ошибку кодом над с о на самом деле это код Хэмминга над

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

Теорема 5.5.1. Минимальное расстояние кода с проверочной матрицей где равно по меньшей мере 3 тогда и только тогда, когда взаимно просты, что возможно тогда и только тогда, когда взаимно просты.

Доказательство. Предположим, что два столбца матрицы линейно зависимы: где элемент у принадлежит Тогда элемент принадлежит полю следовательно, является корнем уравнения Но ненулевые элементы поля можно представить через примитивный элемент а поля в виде первых степеней элемента так как все такие степепи различны и

Тогда для некоторого меньшего имеем

Далее, так как то

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

Покажем теперь, что взаимно просты тогда и только тогда, когда также взаимно просты. Но

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

так что взаимно прости тогда и только тогда, когда взаимно просты.

Согласно доказанной теореме, коды Хэмминга над длины являются циклическими, если взаимно просты. В § 3.4 мы рассматривали, однако, некоторые коды Хэмминга, для которых не взаимно просты. Для этих кодов такое циклическое построение не работает. Простейшим их примером является -код Хэмминга над Этот код нельзя описать через порождающий многочлен. Однако большинство представляющих интерес кодов Хэмминга являются циклическими.

В качестве примера циклического кода Хэмминга рассмотрим -код над для которого выпишем порождающий многочлен. Это построение реализуется в поле и сводится к нахождению минимального многочлена над элемента Элементами порядка 3 в поле являются только так что в поле поле таково:

Множеством сопряженных элементов, содержащих относительно поля является

Но нам нужны сопряженные относительно поля элементы, а они образуют множество

Следовательно, искомый порождающий многочлен равен

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

логарифмов для умножения в поле (в обоих случаях вычисления займут примерно час), находим

Наконец, поскольку мы уже оставили работу в поле то заменим обозначения на более естественные для поля и получим

Это и есть искомый порождающий многочлен -кода Хэмминга над полем