Русская Википедия:Алгоритм Берлекэмпа — Мэсси

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

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

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

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

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

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

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

<math> S_{i + \nu} + \Lambda_1 S_{i+\nu-1} + \cdots + \Lambda_{\nu-1} S_{i+1} + \Lambda_{\nu} S_i = 0. </math>

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

<math> C(x) = C_{L} \ x^{L} + C_{L-1} \ x^{L-1} + \cdots + C_2 \ x^2 + C_1 \ x + 1 </math>

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

<math> C(x) = 1 + C_1 \ x + C_2 \ x^2 + \cdots + C_{L-1} \ x^{L-1} + C_{L} \ x^{L}. </math>

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

<math> S_{n} + C_1 \ S_{n-1} + \cdots + C_L \ S_{n-L}</math>

в итоге ноль:

<math> S_{n} + C_1 \ S_{n-1} + \cdots + C_L \ S_{n-L} = 0,\qquad L\le n\le N-1.</math>

Алгоритм: 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-й итерации оно будет:

<math> d = S_{k} + C_1 \ S_{k-1} + \cdots + C_L \ S_{k-L}.</math>

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

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

<math>C(x) = C(x) \ - \ (d / b) \ x^m \ B(x).</math>

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

<math> d = S_{k} + C_1 \ S_{k-1} + \cdots - (d/b) (S_{j} + B_1 \ S_{j-1} + \cdots ).</math>

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

<math> d = d - (d/b)b = d - d = 0. \ </math>

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

Пример кода

Алгоритм из Шаблон:Harvtxt: 

  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;

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

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

Примечания

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

Литература

Ссылки

Реализация

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  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.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Берлекэмпа_—_Мэсси&oldid=8939972