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

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

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

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

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

  • Задать требуемую последовательность битов ~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.

Примечания[править | править исходный текст]

  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, 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. MR1365809

Ссылки[править | править исходный текст]

Реализация[править | править исходный текст]