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

Общая схема алгоритма Берлекэмпа — Мэсси для последовательностей q-ичных алфавитов.

Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход алгоритма требуемой генерируемой последовательности.

Алгоритм был открыт Элвином Берлекэмпом (англ.) в 1968 году. Применение алгоритма к линейным кодам было найдено Джеймсом Мэсси в следующем году. Это стало ключом для практического применения кодов Рида — Соломона.

Алгоритм для двоичных последовательностей

• Задать требуемую последовательность битов $~s_0, s_1, ..., s_{n-1}$.
• Создать массивы $~b$, $~t$, $~c$ длины $~n$, задать начальные значения $b_0 \leftarrow 1$, $c_0 \leftarrow 1$, $N \leftarrow 0$, $L \leftarrow 0$, $m \leftarrow -1$.
• Пока $~N < n$:
  1. Вычислить $d \leftarrow s_N \oplus c_1s_{N-1} \oplus c_2s_{N-2} \oplus ... \oplus c_Ls_{N-L}$.
  2. Если $~d=0$, то текущая функция генерирует выбранный участок $~s_{N-L}, s_{N-L+1}, ..., s_N$ последовательности; оставить функцию прежней.
  3. Если $~d \not = 0$:
     • Сохранить копию массива $~c$ в $~t$.
     • Вычислить новые значения $~c_{N-m} \leftarrow c_{N-m} \oplus b_0, c_{N-m+1} \leftarrow c_{N-m+1} \oplus b_1, ..., c_{n-1} \leftarrow c_{n-1} \oplus b_{n-N+m-1}$.
     • Если $2L \leqslant N$, установить значения $L \leftarrow N+1-L$, $m \leftarrow N$ и скопировать $~t$ в $~b$.
  4. $N \leftarrow N+1$.
• В результате массив $~c$ — функция обратной связи, то есть $c_Ls_i \oplus c_{L-1}s_{i+1} \oplus c_{L-2}s_{i+2} \oplus ... \oplus c_0s_{i+L} = 0$ для любых $~i$.

Литература

• Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.

Реализация

• Online Implementation of Reed–Sloane and Berlekamp–Massey Over GF(P) Algorithms on SignalsLab