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

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

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

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

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

Алгоритм Б.М. — это альтернативный метод решения СЛАУ, который может быть описан так:

\text{[math]}

S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.

В примерах кода ниже, C(x) представляет Λ(x). Локатор ошибки C(x) для L ошибок определён как:

\text{[math]}

C(x)=C_{L}\ x^{L}+C_{L-1}\ x^{L-1}+\cdots +C_{2}\ x^{2}+C_{1}\ x+1

или задом наперёд:

\text{[math]}

C(x)=1+C_{1}\ x+C_{2}\ x^{2}+\cdots +C_{L-1}\ x^{L-1}+C_{L}\ x^{L}.

Цель алгоритма — определить минимальное L и соответствующее ему C(x), которое даёт во всём синдроме ошибки

\text{[math]}

S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{n-L}

в итоге ноль:

\text{[math]}

S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{n-L}=0,\qquad L\leq n\leq N-1.

Алгоритм: C(x) инициализирован величиной 1, L обозначает текущее количество найденных ошибок на данный момент, и инициализирован нулём. N — общее количество элементов синдрома ошибки. n — главный счётчик, он же индекс элементов синдрома от 0 до (N-1). B(x) — копия последнего C(x) на момент обновления L, и инициализируется 1. b — копия последнего расхождения d (см.ниже) опять же, на момент обновления L и инициализируется 1. m — номер итераций, прошедших с обновления L, B(x), and b и тоже инициализирован единицей.

На каждой итерации вычисляется расхождение d. На k-й итерации оно будет:

\text{[math]}

d=S_{k}+C_{1}\ S_{k-1}+\cdots +C_{L}\ S_{k-L}.

Если d равно нулю, это значит C(x) и L на данный момент верны, достаточно инкрементировать m и продолжить итерации.

Если d ненулевое, алгоритм поправляет C(x) так, чтобы его обнулить d:

\text{[math]}

C(x)=C(x)\ -\ (d/b)\ x^{m}\ B(x).

Умножение на x^m — это, по сути, сдвиг коэффициентов B(x) на m, т. е. каждый коэффициент занимает место на m более старшего, чтобы соответствовать синдрому для b. Если в последний раз L обновляли на итерации j (а сейчас у нас k-я итерация), то m = k - j, а пересчитанное расхождение имеет вид:

\text{[math]}

d=S_{k}+C_{1}\ S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}\ S_{j-1}+\cdots ).

То есть, подставляя, увидим, что оно обращается в нуль:

\text{[math]}

d=d-(d/b)b=d-d=0.\

Также величину L (число найденных ошибок) иногда надо поправлять. Если L равно действительному числу ошибочных символов, то по ходу итераций расхождения обнулятся раньше, чем n станет более или равно (2 L). В противном случае L обновляется и алгоритм обновляет B(x), b, само L (увеличивается), а m сбрасывается в 1. Выражение L = (n + 1 - L) ограничивает L до количества доступных элементов синдрома, использованных для вычисления расхождений, и заодно решает задачу увеличения L более чем на единицу.

Пример кодаПравить

Алгоритм из Massey (1969, p. 124):

  polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */
  /* connection polynomial */
  polynomial(field K) C(x) = 1;  /* coeffs are c_j */
  polynomial(field K) B(x) = 1;
  int L = 0;
  int m = 1;
  field K b = 1;
  int n;

  /* steps 2. and 6. */
  for (n = 0; n < N; n++)
    {
      /* step 2. calculate discrepancy */
      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};

      if (d == 0)
        {
          /* step 3. discrepancy is zero; annihilation continues */
          m = m + 1;
        }
      else if (2 * L <= n)
        {
          /* step 5. */
          /* temporary copy of C(x) */
          polynomial(field K) T(x) = C(x);

          C(x) = C(x) - d b^{-1} x^m B(x);
          L = n + 1 - L;
          B(x) = T(x);
          b = d;
          m = 1;
        }
      else
        {
          /* step 4. */
          C(x) = C(x) - d b^{-1} x^m B(x);
          m = m + 1;
        }
    }
  return L;

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

Задать требуемую последовательность битов $\text{[math]}$ $\text{[math]}$ $s_{0},s_{1},...,s_{n-1}$ .
Создать массивы $\text{[math]}$ $\text{[math]}$ $b$ , $\text{[math]}$ $\text{[math]}$ $t$ , $\text{[math]}$ $\text{[math]}$ $c$ длины $\text{[math]}$ $\text{[math]}$ $n$ , задать начальные значения $\text{[math]}$ $\text{[math]}$ $b_{0}\leftarrow 1$ , $\text{[math]}$ $\text{[math]}$ $c_{0}\leftarrow 1$ , $\text{[math]}$ $\text{[math]}$ $N\leftarrow 0$ , $\text{[math]}$ $\text{[math]}$ $L\leftarrow 0$ , $\text{[math]}$ $\text{[math]}$ $m\leftarrow -1$ .
Пока N < n :
1. Вычислить $\text{[math]}$ $\text{[math]}$ $d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{N-L}$ .
2. Если $\text{[math]}$ $\text{[math]}$ $d=0$ , то текущая функция генерирует выбранный участок $\text{[math]}$ $\text{[math]}$ $s_{N-L},s_{N-L+1},...,s_{N}$ последовательности; оставить функцию прежней.
3. Если d ≠ 0 :
  - Сохранить копию массива $\text{[math]}$ $\text{[math]}$ $c$ в $\text{[math]}$ $\text{[math]}$ $t$ .
  - Вычислить новые значения $\text{[math]}$ $\text{[math]}$ $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}$ .
  - Если $\text{[math]}$ $\text{[math]}$ $2L\leqslant N$ , установить значения $\text{[math]}$ $\text{[math]}$ $L\leftarrow N+1-L$ , $\text{[math]}$ $\text{[math]}$ $m\leftarrow N$ и скопировать $\text{[math]}$ $\text{[math]}$ $t$ в $\text{[math]}$ $\text{[math]}$ $b$ .
4. $\text{[math]}$ $\text{[math]}$ $N\leftarrow N+1$ .
В результате массив $\text{[math]}$ $\text{[math]}$ $c$ — функция обратной связи, то есть $\text{[math]}$ $\text{[math]}$ $c_{L}s_{i}\oplus c_{L-1}s_{i+1}\oplus c_{L-2}s_{i+2}\oplus ...\oplus c_{0}s_{i+L}=0$ для любых $\text{[math]}$ $\text{[math]}$ $i$ .

ПримечанияПравить

↑ Elwyn R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0-89412-063-8.
↑ J. L. Massey, Shift-register synthesis and BCH decoding Архивная копия от 27 сентября 2011 на Wayback Machine, IEEE Trans. Information Theory, IT-15 (1969), 122—127.

ЛитератураПравить

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, A. A. Nechaev. Linear recurring 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. MR: 1365809

СсылкиПравить

Berlekamp-Massey algorithm (англ.) на сайте PlanetMath.
Weisstein, Eric W. Berlekamp-Massey Algorithm — MathWorld.

РеализацияПравить

Online Implementation of Reed-Sloane and Berlekamp-Massey Over GF(P) Algorithms (недоступная ссылка) on SignalsLab
GF(2) implementation in Mathematica (англ.)

[1] Elwyn R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0-89412-063-8.

[2] J. L. Massey, Shift-register synthesis and BCH decoding Архивная копия от 27 сентября 2011 на Wayback Machine, IEEE Trans. Information Theory, IT-15 (1969), 122—127.

[1]

[2]