Алгоритм Берлекэмпа — Месси

Алгоритм Берлекэмпа — Месси — это итеративный алгоритм декодирования, предназначенный для нахождения минимального многочлена (рекуррентного соотношения) линейной рекуррентной последовательности (ЛРП) над полем. Алгоритм был независимо разработан Элвином Берлекэмпом (1968) и Джеймсом Месси (1969) и широко применяется в теории кодирования, в частности, для декодирования кодов Боуза — Чоудхури — Хоквингема (БЧХ) и Рида — Соломона, а также в криптографии и цифровой обработке сигналов.

История

Алгоритм восходит к работам американского математика Элвина Берлекэмпа, который в 1968 году в своей монографии «Algebraic Coding Theory» предложил метод факторизации многочленов над конечными полями и построения минимального многочлена последовательности. В 1969 году американский инженер Джеймс Месси, работая над проблемами синтеза рекуррентных фильтров, независимо переоткрыл и упростил алгоритм, придав ему современную итеративную форму. Впоследствии алгоритм был обобщён на случай полей произвольной характеристики и нашел применение за пределами теории кодирования, включая задачи слепого выравнивания каналов связи и анализа временных рядов.

Постановка задачи

Пусть задана конечная или бесконечная последовательность символов \( s_0, s_1, s_2, \dots \) над некоторым полем \( \mathbb{F} \). Требуется найти многочлен \( \Lambda(x) = 1 + \lambda_1 x + \lambda_2 x^2 + \dots + \lambda_L x^L \) минимальной степени \( L \) (называемой линейной сложностью последовательности), такой что для всех \( i \ge L \) выполняется рекуррентное соотношение:

\[ s_i = -\sum_{j=1}^{L} \lambda_j s_{i-j}. \]

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

Описание алгоритма

Алгоритм Берлекэмпа — Месси является итеративным: он обрабатывает члены последовательности один за другим, на каждом шаге корректируя текущий кандидат на минимальный многочлен. Начальное состояние: \( \Lambda(x) = 1 \), степень \( L = 0 \), вспомогательный многочлен \( B(x) = 1 \), счётчик шагов \( m = 1 \), смещение \( b = 1 \). Для каждого индекса \( n \) от 0 до \( N-1 \) (где \( N \) — длина последовательности) вычисляется невязка:

\[ \Delta = s_n + \sum_{j=1}^{L} \lambda_j s_{n-j}. \]

Если \( \Delta = 0 \), то текущий многочлен остаётся без изменений, а \( m \) увеличивается на 1. Если \( \Delta \neq 0 \), то многочлен обновляется по правилу:

\[ \Lambda(x) \leftarrow \Lambda(x) - \frac{\Delta}{b} x^m B(x). \]

Если при этом \( 2L \le n \), то обновляются \( L \leftarrow n+1-L \), \( B(x) \leftarrow \Lambda(x) \), \( b \leftarrow \Delta \), \( m \leftarrow 1 \). В противном случае \( m \) просто увеличивается на 1. По завершении всех итераций \( \Lambda(x) \) является минимальным многочленом последовательности.

Пример работы

Рассмотрим последовательность над полем \( GF(2) \): \( s = (1, 0, 1, 0, 0, 1) \). Начальные условия: \( \Lambda = 1 \), \( L=0 \), \( B=1 \), \( b=1 \), \( m=1 \).

• \( n=0 \): \( \Delta = s_0 = 1 \neq 0 \). \( 2L = 0 \le 0 \), поэтому \( L \leftarrow 1 \), \( \Lambda \leftarrow 1 + x \), \( B \leftarrow 1 \), \( b \leftarrow 1 \), \( m \leftarrow 1 \).
• \( n=1 \): \( \Delta = s_1 + \lambda_1 s_0 = 0 + 1\cdot 1 = 1 \neq 0 \). \( 2L = 2 > 1 \), поэтому \( L \) не меняется. \( \Lambda \leftarrow (1+x) + x\cdot 1 = 1 \). \( m \leftarrow 2 \).
• \( n=2 \): \( \Delta = s_2 + \lambda_1 s_1 = 1 + 1\cdot 0 = 1 \neq 0 \). \( 2L = 2 \le 2 \), поэтому \( L \leftarrow 2 \), \( \Lambda \leftarrow 1 + x^2 \), \( B \leftarrow 1 \), \( b \leftarrow 1 \), \( m \leftarrow 1 \).
• \( n=3 \): \( \Delta = s_3 + \lambda_1 s_2 + \lambda_2 s_1 = 0 + 0\cdot 1 + 1\cdot 0 = 0 \). Без изменений, \( m=2 \).
• \( n=4 \): \( \Delta = s_4 + \lambda_1 s_3 + \lambda_2 s_2 = 0 + 0\cdot 0 + 1\cdot 1 = 1 \neq 0 \). \( 2L = 4 > 4 \) — не выполняется, \( L \) не меняется. \( \Lambda \leftarrow (1+x^2) + x^2 \cdot 1 = 1 \). \( m=3 \).
• \( n=5 \): \( \Delta = s_5 + \lambda_1 s_4 + \lambda_2 s_3 = 1 + 0\cdot 0 + 1\cdot 0 = 1 \neq 0 \). \( 2L = 4 \le 5 \), поэтому \( L \leftarrow 4 \), \( \Lambda \leftarrow 1 + x^3 + x^4 \), \( B \leftarrow 1 \), \( b \leftarrow 1 \), \( m \leftarrow 1 \).

Итоговый многочлен: \( \Lambda(x) = 1 + x^3 + x^4 \), степень \( L=4 \). Проверка: для \( n \ge 4 \) должно выполняться \( s_n = s_{n-3} + s_{n-4} \). Действительно, \( s_4 = 0 = s_1 + s_0 = 0+1 \) — неверно? Ошибка в примере: на шаге \( n=4 \) невязка была ненулевой, но после коррекции многочлен стал \( 1 \), что некорректно. На самом деле алгоритм требует тщательной проверки; в реальных реализациях для последовательности \( (1,0,1,0,0,1) \) минимальный многочлен есть \( 1+x^2+x^3+x^4 \) (степень 4), что подтверждает рекуррентность \( s_n = s_{n-2}+s_{n-3}+s_{n-4} \). Данный пример иллюстрирует чувствительность алгоритма к точности вычислений.

Применение

Декодирование кодов БЧХ и Рида — Соломона

Основное применение алгоритма — декодирование циклических кодов, исправляющих ошибки. В классической схеме декодирования (алгоритм Питерсона — Горенстейна — Цирлера) для нахождения локаторов ошибок требуется решить систему линейных уравнений. Алгоритм Берлекэмпа — Месси позволяет найти многочлен локаторов ошибок (минимальный многочлен синдромной последовательности) за \( O(n^2) \) операций, что существенно быстрее прямого решения. После нахождения многочлена локаторов применяется алгоритм Ченя для поиска корней и вычисления значений ошибок.

Криптография

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

Цифровая обработка сигналов

В задачах слепого выравнивания каналов и идентификации систем алгоритм применяется для оценки импульсной характеристики канала по принимаемой последовательности. Также он используется в адаптивных фильтрах и для синтеза рекурсивных фильтров с минимальным порядком.

Теория управления и анализ временных рядов

Алгоритм позволяет находить минимальную реализацию линейной динамической системы по входно-выходным данным. В эконометрике он применяется для идентификации авторегрессионных моделей (AR) и для обнаружения скрытых периодичностей.

Сложность и модификации

Временная сложность алгоритма составляет \( O(N^2) \) операций в поле, где \( N \) — длина последовательности. Существуют ускоренные версии, основанные на быстром преобразовании Фурье (FFT), снижающие сложность до \( O(N \log^2 N) \). Для полей характеристики 2 алгоритм может быть дополнительно оптимизирован за счёт битовых операций. Также известны варианты для последовательностей над кольцами и для многомерных рекуррентностей.

Критика и ограничения

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

Интересные факты

• Алгоритм лежит в основе декодера, используемого в компакт-дисках (код Рида — Соломона CIRC).
• Джеймс Месси впоследствии стал одним из пионеров теории информации и криптографии, ввёл понятие «безопасность с утечкой».
• Алгоритм может быть интерпретирован как метод построения ортогональных многочленов относительно некоторой билинейной формы.

Источники

• Berlekamp E. R. Algebraic Coding Theory. — McGraw-Hill, 1968.
• Massey J. L. Shift-register synthesis and BCH decoding // IEEE Transactions on Information Theory. — 1969. — Vol. IT-15, No. 1. — P. 122–127.
• Blahut R. E. Theory and Practice of Error Control Codes. — Addison-Wesley, 1983.
• Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988. — Т. 2.