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

Не следует путать с Алгоритм Берлекэмпа — Мэсси.

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

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

Если существуют константы: ${}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), \dots$ в соответствии со схемой алгоритма Берлекэмпа, представленной на рисунке^{[уточнить]}, который находится по адресу, указанному ниже. Таким образом, построенный набор полиномов $G_0 (x),G_1 (x), \dots ,$ отражает реккурентную закономерность в последовательности 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.

Для улучшения этой статьи по математике желательно?: Проверить достоверность указанной в статье информации. Исправить статью согласно стилистическим правилам Википедии. Викифицировать статью.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.