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

Алгоритм Берлекэмпа-Мэсси - данный алгоритм позволяет находить закон рекурсии для линейной реккурентной последовательности.

Основные определения

Если существуют константы ${}f_0,\dots,f_m-_1$ такие что: ${}u(i+m) = \sum_{j=0}^{m-1} {f_j u(i+j)}$ То последовательность u будем называть линейной реккурентной последовательностью (ЛРП) порядка m. Поскольку u-ЛРП, то полином ${}F(x) = {x^j}-\sum_{j=0}^{m-1} {f_j x^j}$ будем называть характеристическим полиномом для ЛРП u. Характеристический полином, имеющий наименьшую степень, называется минимальным многочленом, а его степень- линейной сложностью рассматриваемой ЛРП. Обозначим u(0,…,l-1)={u(0),…,u(l-1)} -начальный отрезок рассматриваемой ЛРП. Будем говорить, что многочлен : ${}G(x) = {x^m}-\sum_{j=0}^{m-1} {b_j x^j}$ вырабатывает отрезок u(0,…,l-1), если для любого i принадлежащего [0,l-m-1] выполнено: ${}u(i+m) = \sum_{j=0}^{m-1} {b_j u(i+j)}$ то есть, если данный отрезок последовательности является отрезком некоторой ЛРП с характеристическим полиномом G(x). Определим операцию умножения многочлена на последовательность: пусть ${}H(x) = \sum_{j=0}^{n} {h_j x^j}$ произвольный многочлен, а ν-последовательность. Тогда результатом произведения будет последовательность w(i) , такая, что: $H(x)u=w$ a w(i) выражаются следующим образом: ${}w(i) = \sum_{j=0}^{n} {h_j v(i+j)}$ Для нормированного полинома G(x) определим параметры: 1)${}k_u (G)$ -количество лидирующих нулей последовательности G(x)u или ∞ ,если эта последовательность нулевая. 2)${}l_u (G) = {k_u (G)+deg(G)}$

Очевидно, ${}l_u (G)$ максимальная длина начального отрезка u, вырабатываемого полиномом G(x).

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

Задача ставится следующим образом: имеется последовательность u, и число l , нужно найти минимально необходимый полином G , вырабатывающий отрезок u(0,…,l-1). Будем строить последовательность полиномов G_0 (x),G_1 (x),… в соответствии со схемой алгоритма Берлекэмпа-Мэсси , представленной на рисунке, который находится по адресу, указанному ниже. Таким образом, построенный набор полиномов G_0 (x),G_1 (x),… , отражает реккурентную закономерность в последовательности u.

Литература

• V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, A. A. Nechaev. Linear recur-ring sequences over rings and modules. // I. of Math. Science. Contemporary Math. and it's Appl. Thematic surveys, vol. 10, 1994, I. of Math. Sciences, vol. 76, № 6, 1995.