8.2. ИДЕМПОТЕНТЫ

В § 8.2-8.4 мы ограничимся случаем двоичных кодов длины где нечетное число.

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

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

Ясно, что если идемпотент, то также идемпотент.

Теорема Циклический код, или идеал содержит единственный идемпотент такой, что Кроме того, для некоторого многочлена тогда и только тогда, когда .

(ii). тогда и только тогда, когда

может содержать несколько идемпотентов, но только один из них порождает

Доказательство. Пусть где взаимно просты. Легко доказываемое следствие из алгоритма Евклида (следствие 15 гл. 12) состоит в том, что тогда существуют многочлены такие, что в кольце

Положим Тогда из (8.1) следует, что

т. е. в кольце так что идемпотент. Корень степени из единицы является корнем только одного из многочленов или Из (8.1) следует, что многочлены взаимно просты. Поэтому если какой-то корень степени из единицы является корнем многочлена то он также должен быть и корнем Так как не вводит новых нулей, то согласно лемме 5 гл. 7 многочлены порождают один и тот же код.

Для доказательства заметим, что из равенства очевидно, следует, что Обратно, если то

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

Например, для [7, 4, 3]-кода Хэмминга имеем:

Таким образом, идемпотент этого кода равен

Упражнение. (1). Убедитесь, что действительно порождает этот код.

Лемма является идемпотентом тогда и только тогда, когда или 1 для всех

Доказательство. Предположим, что идемпотент. Тогда так что согласно теореме 8 гл. 4 эта величина равна 0 или 1. Для доказательства обратного утверждения предположим, что

Так как равна 0 или 1, то Согласно формуле обращения из леммы 7 гл. 7

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

Следствие 3. Размерность равна числу элементов а, для которых и равна числу элементов а, для которых

Упражнение. (2). Доказать, что где обозначает наибольший общий делитель чисел

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

Лемма 4. Если — идемпотент, то — также идемпотент.

Доказательство. Если то

Теорема 5. Пусть код с идемпотентом Тогда код имеет идемпотент

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

— корнями многочлена Но согласно теореме 4 гл. 7 эти же элементы являются нулями кода

Упражнения. (3). Доказать, что является идемпотентом кода с порождающим многочленом

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