4.2.2. Итеративный алгоритм Берлекэмпа

Опишем итеративный алгоритм Берлекэмпа в модификации, предложенной Месси [17]. Пусть последовательность элементов поля Последовательность элементов того же поля, удовлетворяющую условию

назовем порождающей последовательностью длины для последовательности Порождающую последовательность минимальной длины будем называть минимальной порождающей последовательностью.

Утверждение 4.8. Пусть . При порождающей последовательности не существует. При порождающая последовательность существует и ее минимальная длина равна

Идея доказательства. В случае если то при равенство (4.7) не может иметь места. Если же предположить, что то равенство (4.7) при не справедливо ни при каких . В то же время, полагая получаем порождающую последовательность длины

Следующая лемма устанавливает связь между последовательностями введенными в разд. 4.2.1.

Лемма 4.1. Последовательность является единственной минимальной порождающей последовательностью для последовательности

Доказательство. Положим Из формул (4.5) и (4.7) следует, что порождающая последовательность для последовательности Предположим, что существует другая порождающая последовательность длины меньшей или

равной Тогда

Однако это противоречит тому, что матрица является невырожденной.

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

Если порождающая последовательность не существует, будем полагать

По определению

Лемма 4.2 [17]. Если то

Доказательство. Предположим, что

По определению

Отсюда и из формул (4.8) — (4.10) получаем

но это противоречит предположению.

Основываясь на вышеизложенном, рассмотрим следующий итеративный алгоритм построения минимальной порождающей последовательности для последовательности

Обозначим чарвз подпоследовательность последовательности Можно, очевидно, ограничиться рассмотрением случая, когда среди символов имеется хотя бы один, отличный от нуля. Пусть минимальное значение такое, что Из утверждения 4.8, следует, что

1) если то порождающей последовательности не существует;

1) если то для существует минимальная порождающая последовательность длины а именно

В этом случае

Для удобства положим

2) Предположим, что для найдена порождающая последовательность Введем следующие величины:

Кроме того, предположим, что

если Справедливость равенства (4.12) при очевидна. Так как то существует целое , такое, что

При этом либо либо Если то Допустим, что Тогда порождающая последовательность для но это противоречит (4.13). Следовательно,

Лемма 4.3. Многочлен

где определяет порождающую последовательность для Если с то

Доказательство. Согласно соотношениям (4.12) и (4.13),

Если то Если то, полагая

из формулы (4.15) получаем, что Из (4.14) в свою очередь следует, что

где Из определения и того, что имеем

Если меняется между то меняется от до . Тогда, так как (это следует из (4.15) и (4.16)), то . Если то, согласно определению

Поскольку это равенство справедливо также при Из формул получаем

т. е. задаёт порождающую последовательность длины для Согласно лемме 4.2 и равенству (4.16), длина является минимальной и определяется равенством

Из этой леммы следует, что определяет минимальную порождающую последовательность для

Пример 4.8. Рассмотрим случай исправления трех ошибок кодом из примера 4.7. Здесь

Сначала положим Из утверждения имеем

При этом, согласно соотношению (4.11),

Поэтому если то . В то же время, так как то из формулы (4.14) и равенства имеем

Далее, если и то и

Из формулы (4.14) имеем

Таким образом,

В случае используя вместо системы уравнений (4.5) равенства Ньютона [20], связывающие величины с элементарными симметрическими функциями переменных можно определить по Питерсон [15] использовал именно этот метод. В этом случае можно применить такой же рекуррентный метод решения, как и ранее, и снизить таким образом число шагов с до [3, 4].

Методы декодирования, описанные в разд. 4.2.1 и 4.2.2, предназначены для исправления ошибок, вес которых не превосходит где конструктивное расстояние даже в том случае, если фактическое минимальное расстояние кода больше конструктивного. Были разработаны алгоритмы декодирования ошибок более высокой кратности, но их эффективность оказалась не очень высокой [21].