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

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

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

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

Если существуют константы: {}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.



Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Алгоритм Берлекэмпа" в других словарях:

  • Алгоритм Берлекэмпа — Мэсси — Общая схема алгоритма Берлекэмпа Мэсси для последовательностей q ичных алфавитов. Алгоритм Берлекэмпа Мэсси алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход алгоритма требуемой генерируемой… …   Википедия

  • Алгоритм Берлекампа — Алгоритм Берлекампа  данный алгоритм предназначен для факторизации полиномов, позволяет разлагать полиномы на неприводимые сомножители. Алгоритм был разработан Элвином Берлекэмпом в 1967 году. Следует различать алгоритм Берлекэмпа и алгоритм …   Википедия

  • Код Рида — Коды Рида Соломона (англ. Reed–Solomon codes) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… …   Википедия

  • Код Рида — Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код коррекции ошибок Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Коды Рида-Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код Рида Соломона является …   Википедия

  • РС код — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код Боуза — Коды Боуза  Чоудхури  Хоквингхема (БЧХ коды)  в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с… …   Википедия

  • Мэсси, Джеймс — Мэсси Джеймс (англ. James Lee Massey; 1934, Ваузен, Огайо) выдающийся американский ученый, внесший значительный вклад в теорию информации и криптографию. Является профессором эмиритом цифровых технологий в Швейцарской высшей технической… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»