7.3. Эвристическое решение ключевого уравнения

Нам надо решить ключевое уравнение

относительно многочленов и при заданном многочлене Разобьем эту тяжелую задачу на ряд этапов. Рассмотрим последовательность уравнений

и для каждого найдем многочлены, удовлетворяющие этим уравнениям. В общем случае они могут иметь много решений. Так как степень равна числу ошибок, то хороший декодер должен попытаться найти решение с «малыми» степенями

Если уравнения (7.301) уже решены, то та же пара многочленов вообще говоря, не удовлетворяет сравнению

Однако

где — коэффициент при в произведении

Если то, очевидно, можно положить

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

При этом, конечно, желательно, чтобы степени многочленов и были малыми. Определим последовательности с помощью вспомогательных многочленов равенствами

Легко видеть, что многочлены удовлетворяют сравнению

если и решения сравнения (7.302), а и решения сравнения (7.303).

Существуют два очевидных способа задания многочленов Либо

либо

Если удовлетворяют сравнению (7.302), а удовлетворяют (7.303), то многочлены (7.306) и (7.307) удовлетворяют сравнению

Если то выражения (7.307) не определены и нужно использовать формулы (7.306). Если то выбор между (7.306) и (7.307) должен основываться на минимизации степеней Степени многочленов задаются следующими соотношениями:

Степень многочлена может случайно увеличиться, если и старшие коэффициенты мпогочленов равны. Для того чтобы избежать таких случаев, мы при выборе между (7.306) и (7.307) будем учитывать не степени многочленов и а некоторую числовую функцию которую определим следующим образом:

В силу соотношений (7.308), (7.312) и (7.313) можно дать следующее рекурсивное определение функции

Легко видеть, что если и то . Аналогично, если .

Для того чтобы обеспечить неравенства , введем следующее правило выбора между (7.306) и (7.307):

Если то либо (7.306), либо (7.307) приведет к многочленам степень каждого из которых В случае сомнения в выборе между (7.306) и (7.307) его следует отложить до проведения дальнейших рассуждений.

Начальные уравнения имеют вид

Эти уравнения могут быть решены при следующих очевидных начальных условиях:

Отметим, что а Таким образом, на первом шаге мы получаем даже усиление неравенств:

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

Если при и мы сделали правильный выбор между (7.306) и (7.307) и если хорошо определена, то можно гарантировать выполнение условий (7.317) и (7.318) для всех к. Из (7.310) и (7.311) следует, что правильный выбор состоит в следующем:

На этом эвристическое исследование алгоритма заканчивается. Подведем итог. Мы исходим из начальных условий (7.316) и

ределяем используя формулу используя используя (7.305) и используя (7.314). Затем в соответствии с (7.315) и (7.319) определяем с помощью (7.306) или (7.307), а в соответствии с формулой (7.320). Как будет показано, многочлены, определенные этими рекурсивными правилами, удовлетворяют уравнениям (7.301), (7.302), (7.312), (7.313), (7.317) и (7.318).

Точная формулировка алгоритма имеет следующий вид.