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

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

Общая схема алгоритма Берлекэмпа — Мэсси для последовательностей 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 1$, $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$.

Пример кода на C#

byte[] b, c, t, s;
int N, L, m;
 
public void BerlekampRegistryTester(int sequenceLength)
{
    b = new byte[sequenceLength];
    c = new byte[sequenceLength];
    t = new byte[sequenceLength];
    s = new byte[sequenceLength];
    for (int i = 0; i < sequenceLength; i++) 
        b[i] = c[i] = t[i] = 0;
    b[0] = c[0] = 1;
    N = L = 0;
    m = -1;
}
 
private void runTest() 
{
    int d;
    while (N < s.Length)
    {
        d = 0;
        for (int i = 0; i <= L; i++) 
            d += s[N-i] * c[i];
        d = d % 2;
 
        if (d != 0)
        {
            t = (byte[])c.Clone();
            for (int i = 0; i <= s.Length + m - 1 - N; i++)
                c[N - m + i] = (byte)(c[N - m + i] ^ b[i]);
            if (L <= (N / 2))
            {
                L = N + 1 - L;
                m = N;
                b = (byte[])t.Clone();
            }
        }
        N++;
    }
}

Примечания

1. ↑ Elwyn R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0894120638.
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 с.