12.5. Определение числа информационных символов в непримитивных БЧХ-кодах

Хотя число информационных символов произвольного БЧХ-кода всегда может быть найдено в соответствии с леммой 12.12, во многих случаях счет удается значительно упростить путем сведения к задаче перечисления -ичных последовательностей. Для примитивных БЧХ-кодов такая редукция дается теоремой 12.23 и позволяет применять все теоремы разд. 12.3. Аналогичный результат для непримитивных БЧХ-кодов дает теорема 12.51.

12.51. Теорема. Пусть заданы числа мультипликативный порядок -ичная последовательность, координаты которой совпадают с коэффициентами -ичного представления числа последовательность, определенная последовательностью в соответствии с теоремой 12.38.

Тогда число равно числу -ичных последовательностей длины одновременно удовлетворяющих двум условиям.

1) W - сцепление субпоследовательностей для V, включая (возможно, пустую) окаймляющую субпоследовательность;

2) число делится на

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

равно числу целых чисел кратных и таких, что для всех , где число теперь определяется условиями: Так как между или между нет чисел, кратных то последние два условия эквивалентны неравенствам Так как -ичное представление числа есть циклический сдвиг -ичного представления числа то теорема 12.51 вытекает из теорем 12.38, 12.33 и 12.34.

Для пересчета -ичных последовательностей длины удовлетворяющих теореме 12.51, полезно ввести следующие обозначения:

12.52. Определение. Обозначим через число -ичных последовательностей длины являющихся сцеплением субпоследовательностей для V, которым соответствуют числа, сравнимые с

Пусть число субпоследовательностей для V, сравнимых с

При фиксированных и V теорема 12.53 дает рекурсивное правило вычисления для всех значений при соответствующих значениях Условимся, что все арифметические операции над верхним индексом чисел К выполняются по модулю

12.53. Теорема

Доказательство. При делении на пустая последовательность длины 0 дает остаток 0. При имеется способов выбора такой последней субпоследовательности в сцеплении, что ее длина равна к, а остаток при делении на равен х. Предшествующий ей -мерный вектор является сцеплением субпоследовательностей для Если это сцепление длины к имеет остаток I, то сцепление длины имеет остаток который равен тогда и только тогда, когда

12.54. Теорема. В предположениях теорем 12.51 и 12.53 и в обозначениях определения 12.52 имеет место равенство

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

При малых теоремы 12.51, 12.53 и 12.54 и определение 12.52 дают простой метод вычисления Для больших такое вычисление требует уже больших усилий.

12.55. Пример. Сколько информационных символов имеет БЧХ-код с блоковой длиной 1365 и конструктивным расстоянием 260?

Решение. (в двоичной записи), так что Субпоследовательностями для V являются 0, 10, 1100, так что в остальных случаях Выпишем (3) в виде таблиц:

Теперь можно вычислить :

Согласно теореме 12.54, .

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

разделим соответствующее число на и произведем округление. В данном примере Наименьшим сцеплением длины 12 ее суперпоследовательностей является последовательность 001100110011, равная так что расстояние Боуза равно 273.