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

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

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

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

• Задать требуемую последовательность битов .

• Создать массивы , ,  длины , задать начальные значения , , , , .

• Пока :

  1. Вычислить .

  2. Если , то текущая функция генерирует выбранный участок  последовательности; оставить функцию прежней.

  3. Если :

     • Сохранить копию массива  в .

     • Вычислить новые значения .

     • Если , установить значения ,  и скопировать  в .

  4. .

• В результате массив  — функция обратной связи, то есть  для любых .

Пример кода на 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++;
 }
}

Пример кода на Ruby:

s = [0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
b = Array.new(s.size){ |index| 0 }
c = Array.new(s.size){ |index| 0 }
t = Array.new(s.size){ |index| 0 }
b[0] = 1
c[0] = 1
N = 0
L = 0
m = -1
 
while N < s.size do
 d = 0
 0.upto(L) do |i|
 d += s[N - i] * c[i]
 end
 d %= 2
 
 if (d != 0)
 t = c.clone
 0.upto(s.size + m - 1 - N) do |i|
 c[N - m + i] = c[N - m + i] ^ b[i]
 end
 if (L <= (N / 2))
 L = N + 1 - L
 m = N;
 b = t.clone
 end
 end
 N = N.next
end

Лит.: Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes — М.: Мир, 1986. — 576 с.