15.4. ПОДКОДЫ РАЗМЕРНОСТИ 2m В КОДАХ R(2, m)* И R(2, m)

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

Теорема 14. Пусть В — симплектическая матрица ранга Тогда множество всех двоичных -векторов таких, что для всех образует пространство размерности

Доказательство. Пусть В — матрица, описанная в теореме 4, и положим Тогда

Так как матрица имеет вид

то

Эта величина равна тождественно нулю для всех и тогда и только тогда, когда

Таким образом, векторы образуют пространство размерности

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

где I представляет собой -вектор, соответствующий элементу Согласно уравнению (15.4) значения соответствующей симплектической формы задаются равенством

Мы увидим, что обычно может быть записана в виде где линеаризованный многочлен. Тогда в силу теоремы 14

где ядро определяется как подпространство таких элементов что

Малые подкоды кода . В этом разделе будет найден спектр весов циклического кода с порождающим идемпотентом где для произвольного Он представляет собой подкод кода . В частности, код с порождающим идемпотентом является дуальным к коду БЧХ, исправляющему две ошибки.

Наш метод вычисления весового спектра состоит в следующем. Сначала выписывается многочлен Мэттсона-Соломона для типичного кодового слова и, следовательно, булева функция описывающая это слово. Эта функция является квадратичной, так как код представляет собой подкод Затем мы находим соответствующую симплектическую форму ее ранг (см. используя теорему 5, вычисляем возможные веса в коде. Наконец, применяя методы гл. 6, находим спектр весов.

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

Порождающий идемпотент кода равен

Случай (I), нечетно: Этот случай легко анализируется с помощью результата, доказательство которого мы предоставляем читателю.

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

(Ь). Доказать, что являются единственными нечетными числами в циклотомическом классе и что циклотомический класс содержит элементов.

Найдем спектр весов подкода кода порожденного идемпотентом Ненулевые слова кода записываются в одной из форм: где некоторые целые числа. Вес слов первых двух видов равен и они не представляют трудностей.

Слова третьего типа являются циклическими сдвигами кодового слова МС-многочлен слова а определяется так (см. § 8.6):

Пусть булева функция, описывающая вектор а. Тогда согласно теореме 20 гл. 8 для всех

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

Воспользуемся уравнением (15.21) для вычисления симплектической формы, соответствующей тому смежному классу кода по который содержит вектор а. Эта формула согласно (15.21) равна:

Поскольку и

форма переписывается в виде

Теперь мы воспользуемся равенством (15.20) для вычисления ранга формы Форма равна нулю при всех значениях

где (по теореме 8 гл. 4). Таким образом, размерность пространства элементов таких, что для всех равна Из равенства (15.20) получаем, что ранг матрицы В равен Из теоремы 5 заключаем, что вес кодовых слов вида равен .

Наконец, так как дуальный код представляет собой подкод кода Хэмминга, то 3. Поэтому, используя теорему 2 гл. 6, находим спектр весов кода который приведен на рис. 15.2. Рисунок 15.2 обобщает результаты теоремы 34 гл. 8.

Рис. 15.2. Спектр весов кода с порождающим идемпотентом где нечетно

Отметим, что код с порождающим идемпотентом представляет собой ортогональный коду БЧХ, исправляющему две ошибки. В этом случае и спектр весов кода приведен на рис. 15.3. (Это было использовано в § 9.8 для доказательства квазисовершенности кода БЧХ, исправляющего две ошибки).

Рис. 15 3. Спектр весов кода, дуального коду БЧХ длины исправляющего две ошибки, нечетно

Примеры. Для коды и являются -кодами; для и являются -кодами; для и являются -кодами. Спектры весов этих кодов совпадают с теми, которые приведены на

рис. 8.7. Для код является -кодом, и его спектр имеет вид:

Случай (II). четно. Этот случай вызывает большие затруднения, так как число часто оказывается не взаимно простым с

Мы начнем рассмотрение этого случая с частного случая -кода с порождающим идемпотентом являющегося дуальным к коду БЧХ, исправляющему две ошибки.

В рассматриваемом случае 3 делит так как четно и слово кода в общем случае записывается в виде Его МС-многочлен равен (см. § 8.6)

Соответствующая булева функция по теореме 20 гл. 8 для всех принимает значения

Симплектическая форма равна:

Таким образом, задача сводится к определению размерности пространства нулей функции

где

Далее является корнем для (15.22) тогда и только тогда, когда равно нулю или

Сколько имеется в различных элементов , удовлетворяющих этому уравнению?

Если — примитивный элемент поля то для всех

Обратно, если то

Следовательно, в имеется элементов у, удовлетворяющих уравнению (15.23).

Если элемент у имеет вид для некоторого то (15.22) имеет в четыре корня и ранг матрицы В равен

Вес соответствующего кодового слова равен или Если элемент у не имеет такого вида, то нулем функции (15.22) является только а вес соответствующего кодового слова равен

Минимальное расстояние дуального кода равно 5, и, используя опять теорему 2 гл. 6, находим спектр весов кода указанный на рис. 15.4.

Рис. 15.4. Спектр весов кода, дуального коду БЧХ, исправляющему две ошибки; четно

Теперь рассмотрим общий случай кода с порождающим идемпотентом где (Случай проанализирован в гл. 8.)

Слова кода записываются в одной из форм или Вес слова первого вида всегда равен для других получаем симплектическую форму

Следовательно, надо найти число элементов таких, что

или, что эквивалентно, число ненулевых таких, что

Число решений уравнения (15.25) дается ниже в упражнении (7). Из этого упражнения следует, что если то (15.24) имеет в поле точно решений при произвольном выборе у. Следовательно, в этом случае код содержит слова только трех весов: и спектр кода равен спектру кода для нечетного выписанному на рис. 15.2.

С другой стороны, если то (15.24) имеег либо 1, либо решений в зависимости от выбора у, и в этом

случае код имеет пять весов, а именно: Согласно упражнению (8) минимальное расстояние дуального кода не меньше чем 5, и, используя опять теорему 2 гл. 6, получаем спектр весов, приведенный на рис. 15.5.

Рис. 15.5. Спектр весов кода с порождающим идемпотентом где

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

равно:

(8). Используя обобщение Хартманна-Тзенга для границы БЧХ (упражнение (24) гл. 7), доказать, что минимальное расстояние кода равно по меньшей мере 5.

(9). Доказать, что числа взаимно просты тогда и только тогда, когда Если то числа имеют нетривиальный общий делитель.

(10). Показать, что код, дуальный расширенному коду БЧХ, исправляющему две ошибки, имеет параметры