Даже если
Следовательно, производящая функция
удовлетворяет уравнению
где, так же как и в разд. 3.2, знак
употребляется для обозначения четной части, а знак
для обозначения нечетной части функции. Уравнение
для производящей функции, как будет сейчас показано, позволяет значительно упростить итеративный алгоритм.
7.61. Лемма. Пусть
взаимно обратные производящие функции в поле характеристики 2:
Равенство
выполняется тогда и только тогда, когда.
Доказательство. Разложение равенства
на четную и нечетную части дает:
Вычтем из первого равенства, умноженного на
второе, умноженное на 5. Тогда
откуда
В поле характеристики 2 имеем
тогда и только тогда, когда
или
Теорема. Если в поле характеристики 2 выполняется равенство
то величины, участвующие в алгоритме 7.4, удовлетворяют условиям
Доказательство. Применим индукцию по числу
Для
теорема справедлива. Мы утверждаем, что если
то
и, следовательно,
Не очевидно здесь только равенство
Для его доказательства рассмотрим сравнение
Умножив обе части на
согласно лемме 7.61, получим
Так как функция в левой части нечетная, то
7.63. Теорема.
Доказательство. Предположим, что
и
Равенство
выполняется только тогда, когда к нечетно, причем в этом случае
Отсюда следует, что
Согласно алгоритму
Так как слагаемые в правой части этого равенства имеют разные степени, то
. Легко проверить, что
. Так как
то, используя индукцию по к, получаем утверждение теоремы.
Теоремы 7.62 и 7.63 позволяют вычислить функции
с помощью сокращенного алгоритма, в котором не участвуют многочлены
, и нечетные части многочленов
и
7.64. Сокращенный алгоритм (для двоичных БЧХ-кодов). Сначала полагаем
Строим рекурсию следующим образом. Если величина
неизвестна, то вычисление останавливается; в противном случае полагаем величину
равной коэффициенту при
в произведении
Из этого алгоритма очевидно следует, что
Можно также упростить формулу для общего решения сравнения
при начальном условии
Согласно теореме 7.43,
После умножения на
получим
Эта функция является четной только тогда, когда
Указанные упрощения для двоичного случая основаны на свойствах матрицы
Следующей, достаточно утомительной, но необходимой задачей является доказательство равенства
где квадратные скобки обозначают наибольшее целое число, не превосходящее содержимого скобок
Доказательство этой теоремы вполне аналогично доказательству теоремы 7.51, если для
положить
Это доказательство мы предоставляем читателю.
Для иллюстрации алгоритма 7.64 рассмотрим следующий пример.
7.68. Пример. Рассмотрим двоичный БЧХ-код с блоковой длиной 31, исправляющий три ошибки. Будем полагать, что элементы поля совпадают с многочленами от а степени
где
Таблицы логарифмов и антилогарифмов для этого поля приведены в приложении А. Предположим, что
Эти вычисления можно подытожить следующим образом: