8.3. МИНИМАЛЬНЫЕ ИДЕАЛЫ, НЕПРИВОДИМЫЕ КОДЫ И ПРИМИТИВНЫЕ ИДЕМПОТЕНТЫ

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

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

В частности, единственный ненуль многочлена равен и

Точная формула для может быть получена с помощью формулы обращения из леммы 7 гл. 7. Теорема 6.

где

Доказательство. Согласно лемме 7 гл. 7 имеем:

Например, для коэффициенты многочленов равны:

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

Упражнения. (5). Используя таблицу поля на рис. 4.5, показать, что

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

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

Теорема 7. Примитивные идемпотенты удовлетворяют условиям:

(ii).    , если

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

(iv). Любой идемиотент может быть записан в виде для некоторых Наоборот, всякий многочлен такого вида является идемпотентом.

Доказательство, (i). Согласно лемме 6 гл. 7 имеем:

(ii). Пусть и — минимальные идеалы с идемпотентами и Идеал является собственным подыдеалом в и поэтому равен нулю. Так как то

Из вытекает, что

где лежит в идеале, порожденном идемпотентом

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

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

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

Упражнения. (7). Используя таблицу поля GF(24) на рис. 4.2, показать, что примитивные идемпотенты для равны:

(8). Аналогично показать, что примитивные идемпотенты для равны (выписаны только показатели степеней ненулевых членов многочлена):

Примитивные идемпотенты для приведены на рис. 8.1. Здесь идемпотенты выписаны в двоично-восьмиричной системе,

Рис. 8.1 Примитивные идемпотенты для

причем слева расположены элементы наименьших степеней, например

(9). Найти примитивные идемпотенты кольца для .

(10). Если идемпотент идеала идемпотент идеала идемпотент идеала идемпотент идеала (наименьшего идеала, содержащего

(11). Если идемпотент кода равен то все ненули кода исчерпываются элементами для Если идемпотент кода равен то все нули кода исчерпываются элементами а для

(12). Показать, что идемпотент кода Хэмминга равен и что идемпотент -кода БЧХ, исправляющего две ошибки, равен

(13). Исследовать [9, 6, 2] неприводимый код с идемпотентом Найти все слова кода и показать, что его распределение весов имеет вид:

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

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

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

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

(15). (Лемпель.) (i). Пусть Доказать, что

где сумма по всем нечетным степеням переменной х, содержащимся в

В условиях теоремы 6 доказать, что где если четно, и если нечетно. (Напомним, что

(16). Доказать, что всего имеется минимальных идеалов, эквивалентных коду (и такое же число циклических кодов, эквивалентных коду где функция Эйлера, определенная в упражнении (8) гл. 4.

(17). Пусть некоторый делитель многочлена Пусть идемпотент идеала с порождающим многочленом Доказать, что

где производная от если - многочлен четной степени, и 1, если степень нечетна. Иными словами, доказать, что

где [Указание. Показать, что . Затем доказать, что если если

Вырожденные циклические коды. Циклический код, состоящий из нескольких повторений кода с меньшей блоковой длиной, называется вырожденным. Например, код с повторением вырожден, так как он состоит из нескольких повторений кода

Упражнение. (18). Проверить, что при многочлены являются идемпотентами вырожденных идеалов. Найти размерности этих идеалов.

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

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

Наоборот, пусть наименьшее целое число такое, что делит Тогда делит так как в противном случае делит где Следовательно,

Тогда каждое кодовое слово имеет вид где по теореме 1 гл.

Упражнение. (19). Показать, что для или 7 код состоит из 0 и всех циклических сдвигов многочлена С другой стороны, код состоит из векторов вида где кодовое слово -кода с общей проверкой на четность. Алгебраически код состоит из всех элементов вида где

Замечание. Теперь у нас есть метод, позволяющий сказать, примитивен ли неприводимый многочлен степени (см. § 3.2, 4.4). Построим идемпотент где (упражнение (17)). Если все циклические сдвиги этого идемпотента различны, то многочлен примитивен; в противном случае код, порожденный многочленом вырожден.

Упражнения. (20). Проделать эти операции для многочлена

(21). Доказать, что:

(а). Если то размерность идеала равна и он невырожден.

(b). Если то идеал вырожден, его размерность делит и может быть равной

Если взаимно просто с то идеал состоит из кодовых слов для

(22). Пусть — линейный код, в котором ни одна из координат не равна постоянно нулю и в котором имеется только один ненулевой вес. Доказать, что существует минимальный идеал такой, что эквивалентен коду

Изоморфизм минимального идеала и поля. Теорема 9. Минимальный идеал размерности изоморфен полю

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

Предположим, что Пусть

Множество является идеалом. Так как минимален и то либо либо Согласно теореме 1 имеем: следовательно, Таким образом,

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

Лемма 10. Изоморфизм между задается формулой где примитивный корень степени из единицы и является ненулем кода (Конечно, различные выборы задают различные отображения).

Например, рассмотрим -код и с идемпотентом Используя рис. 4.5, можно выбрать или Соответствующие отображения кода на поле показаны на рис. 8.2.

Рис. 8.2. Три отображения кода на поле

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

Покажем, что обратно отображению Обозначим правую часть равенства (8.3) через Покажем сначала, что

Таким образом, за исключением случая, когда следовательно, Отсюда сразу же вытекает, что

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

Идемпотент идеала отображается в единицу поля Если то элементы являются в взаимно обратными. (В кольце естественно, элементы обратных не имеют.) Заметим также, что

Идемпотенты циклических кодов над GF(q). Пусть циклический код длины над где взаимно просты. Элемент кольца (кольца называется идемпотентом, если

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

(24). Доказать, что если идемпотент в то идемпотент в

(25). Доказать, что существует множество примитивных идемпотентов таких, что

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

(26). Доказать, что минимальный идеал размерности порожденный многочленом изоморфен полю