7.3. ПОРОЖДАЮЩИЙ МНОГОЧЛЕН

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

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

Следующая теорема содержит доказательство этого факта и других основных свойств циклических кодов.

Теорема 1. Пусть ненулевой идеал кольца т. е. циклический код длины

В имеется единственный нормированный многочлен наименьшей степени.

(b). , т. е. порождающий многочлен идеала

делит

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

Если то порождается (как подпространство в строками порождающей матрицы

(Здесь использованы очевидные обозначения.)

Доказательство (а). Предположим, что оба многочлена нормированы и имеют минимальную степень Тогда многочлен имеет более низкую степень, что приводит к противоречию, за исключением случая .

(b). Пусть Воспользуемся в равенством где . В силу линейности кода так что Следовательно, .

(c). Воспользуемся в равенством где это означает, что что приводит к противоречию, за исключением случая

(d), (е). Согласно любой многочлен равен многочлену Следовательно, в кольце

где

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

Теперь дадим несколько примеров циклических кодов.

Двоичные коды Хэмминга. Напомним, что в § 1.7 проверочная матрица двоичного кода Хэмминга длины определялась как матрица, столбцами которой являются все различных ненулевых -векторов. Если теперь а — примитивный элемент поля и § 4.2), то все элементы различны и могут быть представлены как различные ненулевые двоичные -векторы.

Таким образом, проверочная матрица двоичного кода Хэмминга с параметрами может быть представлена в виде

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

где корень уравнения

Вектор принадлежит коду

где

Согласно свойству гл. 4 вектор тогда и только тогда, когда делит Таким образом, код состоит из всех кратных многочлена или, иными словами, верна следующая теорема.

Теорема 2. Определенный ранее код Хэмм инга является циклическим кодом с порождающим многочленом

Согласно теореме 1 порождяющзя мятриця кодз равна

Например, для

Упражнение (6). Проверить, что строки матрицы (7.4) ортогональны строкам матрицы (7.6).

Коды БЧХ, исправляющие две ошибки. Код исправляющий две ошибки, длины был определен соотношением (3.11) как код с проверочной матрицей

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

по свойству где минимальный многочлен элемента тогда и только тогда, когда Но согласно свойству неприводимы и согласно упражнению (15) гл. 4. различны. Поэтому окончательно имеем: тогда и только тогда, когда Таким образом, может быть сформулирована следующая теорема.

Теорема 3. Код БЧХ, исправляющий две ошибки, имеет параметры и является циклическим кодом с порождающим многочленом

Доказательство. Равенство следует из упражнения (15) гл. 4. Минимальное расстояние было найдено в гл. 3. (Другое доказательство приведено ниже в теореме 8.)

Упражнение. (7). Показать, что порождающий многочлен кода БЧХ длины 15 с исправлением двух ошибок, определенного в § 3 гл. 3, равен (использовать § 4.4). Выписать порождающую матрицу кода.

Замечание. До сих пор ничего не было сказано о минимальном расстоянии циклического кода. Это объясняется тем, что определить в общем случае очень трудно. Граница БЧХ (доказываемая ниже теорема 8) дает нижнюю границу для случая, когда известны корни многочлена . В гл. 8 мы увидим,

что в некоторых случаях минимальное расстояние может быть найдено с помощью многочлена Мэттсона — Соломона.

- Упражнения. (8). (Недвоичные коды Хэмминга.) (а). Код - Хэмминга над полем GF(q) задается проверочной матрицей размерности столбцами котррой являются все ненулевые -векторы над первая ненулевая координата которых равна 1. Код 6 из гл. 1 является кодом Доказать, что код является совершенным с параметрами

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

(9). Укороченные циклические коды. Иногда, практические ограничения, накладываемые на кодовые длины, таковы, что для требуемых кодовых длин не существует хороших циклических кодов. В этом случае можно использовать укороченный циклический код который получается из циклического кода путем выбора всех кодовых слов, начинающихся последовательными нулями и отбрасыванием этих нулей. Результирующий код уже, конечно, не будет циклическим. Докажите, однако, что найдется такой многочлен что является идеалом кольца многочленов по модулю многочлена и наоборот, что каждый идеал такого кольца является укороченным циклическим кодом.