9.3. ЧИСЛО ИНФОРМАЦИОННЫХ СИМВОЛОВ КОДОВ БЧХ

Предположим, что 9 — код БЧХ над GF(q) длины с конструктивным расстоянием Мы видели, что согласно теореме 1 число информационных символов, которое мы обозначим через равно по меньшей мере Но точное значение этого числа зависит от степени порождающего многочлена так

Степень многочлена По определению многочлен наименьшей степени, имеющий своими корнями где а — примитивный элемент поля Если корень многочлена то корнями являются также и все его сопряженные, т. е. элементы Число различных элементов, сопряженных с равно наименьшему целому числу такому, что . В обозначениях равно мощности циклотомического класса, содержащего

Имеется легкий способ определения числа Выпишем разложение числа по основанию

где

Тогда т. е. умножение на приводит к сдвигу -последовательности

Например, предположим, что Тогда для получаем -последовательность (0001), период которой равен 4; таким образом, имеются циклические сдвиги следовательно, Мощность циклотомического класса равна 4. С другой стороны, имеет период 2: следовательно, Соответственно

Если достаточно мало по сравнению с то

Теорема 7. Если то циклотомические классы различны и содержат каждый по элементов при условии, что

(где обозначает наименьшее целое число, большее чем х). Таким образом, если удовлетворяет условию (9.5), то

Доказательство, (i). Докажем прежде всего, что эти циклотомические классы различны. Рассмотрим класс Двоичное

разложение числа записанное в виде -последовательности, имеет вид:

где равно 0 или 1 Может ли существовать циклический сдвиг последовательности (9.6), который также начинается нулями и кончается единицей? Очевидно, нет. Следовательно, не может существовать нечетного такого, что

Число элементов в циклотомическом классе равно числу различных циклических сдвигов -последовательности, задаваемой двоичным разложением числа Легко видеть, что если то все циклических сдвигов различны.

Пример. Несколько первых циклотомических классов имеют вид:

Как и было предсказано теоремой, все классы различны, и мощность их равна 6. Эта теорема имеет непосредственное следствие.

Следствие 8. Пусть двоичный код БЧХ длины с конструктивным расстоянием где Тогда

Это следствие применимо к кодам с маленьким конструктивным расстоянием Для произвольного верна следующая теорема.

Теорема 9. Степень многочлена равна числу целых чисел лежащих в диапазоне —1, и таких, что некоторый циклический сдвиг последовательности, задаваемой -разложением числа приводит к числу, не превосходящему

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

Например, рассмотрим двоичный код БЧХ длины 15 и конструктивным расстоянием 5. Корнями являются Разложения показателей по основанию 2 имеют вид:

и степень многочлена равна 8, что подтверждает лемму. Число информационных символов равно:

Но если то имеет дополнительные корни соответственно с

Упражнения. (1). Чему равно число информационных символов двоичных кодов БЧХ длины 63 с ?

(2). Решить ту же задачу для кодов БЧХ над длины 80 с и 11.

Конструктивное расстояние В остальной части этого параграфа находится верхняя граница для частного случая, когда Заметим, что при

где

Наибольший отрезок последовательных нулей в -последовательности назовем серией. Будем различать линейные и круговые серии. Например, последовательность имеет две линейные серии длины 2 и одну длины 1, а также по одной круговой серии длин 3 и 2.

Из теоремы 9 теперь вытекает следующее утверждение.

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

Доказательство. Число не превосходит тогда и только тогда, когда тогда и только тогда, когда начинается с серии, длина которой равна по меньшей мере

Зафиксируем теперь Пусть обозначает число -последовательностей с элементами из множества содержащих линейные серии, длина которых равна по меньшей мере пусть обозначает число -последовательностей, содержащих круговые серии, длина которых равна по меньшей мере и не содержащих ни одной такой линейной серии. Тогда согласно лемме 10

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

Таким образом, задача сводится к чисто комбинаторной задаче определения причем можно опустить:

(см. упражнение (3) в конце этого параграфа). Не составляет труда вывести рекуррентное уравнение для

Лемма 11.

Доказательство. Равенства (9.10) очевидны. Для доказательства уравнения (9.11) заметим, что «-последовательность, входящая в оцениваемое множество мощности содержит серию длины в последних позициях (соответствующих младшим членам разложения), либо имеет вид

где и последние позиций не содержат серии длины

Если мы положим то

и по лемме 11

Общее решение рекуррентного соотношения (9.14) дается формулой

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

Далее все корни уравнения (9.16) удовлетворяют условию Для действительных корней это очевидно. Для комплексных корней при это также очевидно. Предположим теперь, что Используя неравенство треугольника, из (9.16) получаем:

С другой стороны, из (9.16) также вытекает:

что противоречит неравенству (9.17).

Итак, мы доказали следующую теорему.

Теорема 12. (Манн) Число информационных символов кода БЧХ (в узком смысле) над полем GF(q) длины с конструктивным расстоянием удовлетворяет неравенству

где величины зависят от (и не зависят от и выполняется условие

Этот результат будет использован в § 9.5

Упражнение (3). (Манн) Показать, что точное значение может быть найдено следующим образом:

(ii). Следовательно, для неравенство (9.12) можно заменить равенством

(iii). Корни (9 16) удовлетворяют условию является действительным числом, лежащим в интервале для

(iv) Коэффициенты в равенстве (9.15) задаются формулами

(v). Наконец, после некоторых преобразований для больших получаем, что