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

Материал из testwiki
Перейти к навигации Перейти к поиску

Шаблон:Не путать

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

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

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

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

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

Si+ν+Λ1Si+ν−1+⋯+Λν−1Si+1+ΛνSi=0.

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

C(x)=CL xL+CL−1 xL−1+⋯+C2 x2+C1 x+1

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

C(x)=1+C1 x+C2 x2+⋯+CL−1 xL−1+CL xL.

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

Sn+C1 Sn−1+⋯+CL Sn−L

в итоге ноль:

Sn+C1 Sn−1+⋯+CL Sn−L=0,L≤n≤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-й итерации оно будет:

d=Sk+C1 Sk−1+⋯+CL Sk−L.

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

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

C(x)=C(x) − (d/b) xm B(x).

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

d=Sk+C1 Sk−1+⋯−(d/b)(Sj+B1 Sj−1+⋯).

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

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;

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

  • Задать требуемую последовательность битов s0,s1,...,sn−1.
  • Создать массивы b, t, c длины n, задать начальные значения b0←1, c0←1, N←0, L←0, m←−1.
  • Пока N<n:
    1. Вычислить d←sN⊕c1sN−1⊕c2sN−2⊕...⊕cLsN−L.
    2. Если d=0, то текущая функция генерирует выбранный участок sN−L,sN−L+1,...,sN последовательности; оставить функцию прежней.
    3. Если d=0:
      • Сохранить копию массива c в t.
      • Вычислить новые значения cN−m←cN−m⊕b0,cN−m+1←cN−m+1⊕b1,...,cn−1←cn−1⊕bn−N+m−1.
      • Если 2L⩽N, установить значения L←N+1−L, m←N и скопировать t в b.
    4. N←N+1.
  • В результате массив c — функция обратной связи, то есть cLsi⊕cL−1si+1⊕cL−2si+2⊕...⊕c0si+L=0 для любых i.

Примечания

Шаблон:Примечания

Литература

Ссылки

Реализация

  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 Шаблон:Wayback, IEEE Trans. Information Theory, IT-15 (1969), 122—127.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Алгоритм_Берлекэмпа_—_Мэсси&oldid=8234