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

Не путать с алгоритмом Берлекампа .

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

Элвин Берлекамп изобрел алгоритм декодирования кодов Бозе-Чаудхури-Хоквенгема (BCH) . Джеймс Мэсси осознал его применение к регистрам сдвига с линейной обратной связью и упростил алгоритм. Мэсси назвал этот алгоритм алгоритмом синтеза LFSR (итеративный алгоритм Берлекэмпа). но теперь он известен как алгоритм Берлекэмпа – Мэсси.

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

Алгоритм Берлекэмпа – Мэсси является альтернативой декодеру Рида – Соломона Петерсона для решения системы линейных уравнений. Его можно резюмировать как поиск коэффициентов Λ _j многочлена Λ( x ), чтобы для всех позиций i во входном потоке S :

$S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.$

В приведенных ниже примерах кода C ( x ) является потенциальным экземпляром Λ ( x ). Полином локатора ошибок C ( x ) для ошибок L определяется как:

$C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1$

или наоборот:

$C(x)=1+C_{1}x+C_{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.$

Цель алгоритма — определить минимальную степень L и C ( x ), которая приводит к появлению всех синдромов.

$S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}$

быть равным 0:

$S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.$

Алгоритм: C ( x ) инициализируется значением 1, L — текущее количество предполагаемых ошибок и инициализируется нулем. N – общее количество синдромов. n используется в качестве основного итератора и для индексации синдромов от 0 до N -1. B ( x ) — копия последнего C ( x ), поскольку L был обновлен и инициализирован значением 1. b — копия последнего несоответствия d (поясняется ниже), поскольку L было обновлено и инициализировано значением 1. m — количество итераций, поскольку L , B ( x ) и b были обновлены и инициализированы значением 1.

Каждая итерация алгоритма вычисляет несоответствие d . На итерации k это будет:

$d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.$

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

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

$C(x)\gets C(x)-(d/b)x^{m}B(x).$

х ​ ^м термин сдвигает B(x) так, что он следует синдромам, соответствующим b . Если предыдущее обновление L произошло на итерации j , то m = k − j , и пересчитанное несоответствие будет:

$d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}S_{j-1}+\cdots ).$

Это изменит пересчитанное расхождение на:

$d=d-(d/b)b=d-d=0.$

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

Псевдокод

Алгоритм Мэсси (1969 , стр. 124) для произвольного поля:

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 + $\sum _{i=1}^{L}c_{i}\cdot 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;

В случае двоичного кода GF(2) BCH невязка d будет равна нулю на всех нечетных шагах, поэтому можно добавить проверку, чтобы избежать ее вычисления.

/* ... */
for (n = 0; n < N; n++) {
    /* if odd step number, discrepancy == 0, no need to calculate it */
    if ((n&1) != 0) {
        m = m + 1;
        continue;
    }
/* ... */

См. также

• Исправление ошибок Рида – Соломона
• Алгоритм Ридса – Слоана , расширение для последовательностей над целыми числами по модулю n
• Регистр сдвига с нелинейной обратной связью (NLFSR)

Внешние ссылки

• «Алгоритм Берлекэмпа-Мэсси» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Алгоритм Берлекэмпа – Мэсси в PlanetMath .
• Вайсштейн, Эрик В. «Алгоритм Берлекэмпа – Мэсси» . Математический мир .
• Реализация GF(2) в системе Mathematica
• (на немецком языке) Апплет Алгоритм Берлекампа – Мэсси
• Онлайн калькулятор GF(2) Берлекэмпа-Месси