Просмотр кода страницы Алгоритм Берлекэмпа — Мэсси

{{не путать|Алгоритм Берлекэмпа|алгоритмом Берлекэмпа}}
[[Файл:Berlekamp–Massey algorithm.png|200px|thumb|Общая схема алгоритма Берлекэмпа — Мэсси для последовательностей ''q''-ичных алфавитов.]]
'''Алгоритм Берлекэмпа — Мэсси''' — алгоритм поиска кратчайшего [[Регистр сдвига с линейной обратной связью|регистра сдвига с линейной обратной связью]] для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной [[рекуррентная последовательность|рекуррентной последовательности]] над произвольным [[поле (алгебра)|полем]].

Алгоритм был открыт [[Берлекэмп, Элвин|Элвином Берлекэмпом]] в 1968 году<ref>''Elwyn R. Berlekamp'', Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0-89412-063-8.</ref>. Применение алгоритма к [[Линейный код|линейным кодам]] было найдено [[Мэсси, Джеймс|Джеймсом Мэсси]] в следующем году<ref>''J. L. Massey'', [http://crypto.stanford.edu/~mironov/cs359/massey.pdf Shift-register synthesis and BCH decoding] {{Wayback|url=http://crypto.stanford.edu/~mironov/cs359/massey.pdf |date=20110927154215 }}, IEEE Trans. Information Theory, IT-15 (1969), 122—127.</ref>. Это стало ключом для практического применения [[Код Рида — Соломона|кодов Рида — Соломона]].

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

:<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>

Умножение на x<sup>m</sup> — это, по сути, сдвиг коэффициентов 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 более чем на единицу.

==Пример кода==

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

<!-- Notes: notation changes from Massey:
Massey     Here
N          n       count 0 to n-1
x          m       count
D          x       formal variable
B(D)       B(x)    polynomial
C(D)       C(x)    polynomial
T(D)       T(x)    polynomial
-->
<source lang=C>
  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;
</source>

== Алгоритм для двоичных последовательностей ==
* Задать требуемую последовательность битов <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>:
*# Вычислить <math>d \leftarrow s_N \oplus c_1s_{N-1} \oplus c_2s_{N-2} \oplus ... \oplus c_Ls_{N-L}</math>.
*# Если <math>d=0</math>, то текущая функция генерирует выбранный участок <math>s_{N-L}, s_{N-L+1}, ..., s_N</math> последовательности; оставить функцию прежней.
*# Если <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>.
*# <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>.

== Примечания ==
{{примечания}}

== Литература ==
* {{Книга:Блейхут Р.: Теория и практика кодов}}
* ''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}}

== Ссылки ==
* {{PlanetMath|title=Berlekamp-Massey algorithm|urlname=BerlekampMasseyAlgorithm}}
* ''Weisstein, Eric W.'' [http://mathworld.wolfram.com/Berlekamp-MasseyAlgorithm.html Berlekamp-Massey Algorithm] — [[MathWorld]].

== Реализация ==
* [http://signalslab.marstu.net/?page_id=5621 Online Implementation of Reed-Sloane and Berlekamp-Massey Over GF(P) Algorithms]{{Недоступная ссылка|date=2018-05|bot=InternetArchiveBot }} on [https://web.archive.org/web/20120510012832/http://signalslab.marstu.net/?lang=ru SignalsLab]
* [http://code.google.com/p/lfsr/ GF(2) implementation in Mathematica]{{ref-en}}

[[Категория:Алгоритмы]]
[[Категория:Теория кодирования]]
[[Категория:Ряды и последовательности]]