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

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

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

Элвин Берлекэмп изобрел алгоритм декодирования кодов Бозе-Чоудхури-Хоквингема (БЧХ) . ^{[3] [4]} Джеймс Мэсси распознал его применение в линейных регистрах сдвига с обратной связью и упростил алгоритм. ^{[5] [6]} Мэсси назвал алгоритм алгоритмом синтеза LFSR (итеративный алгоритм Берлекэмпа), ^[7] но теперь он известен как алгоритм Берлекэмпа-Месси.

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

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

${\displaystyle 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 ошибок определяется как:

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

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

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

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

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

равно 0:

${\displaystyle 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 — текущее количество предполагаемых ошибок, инициализируется значением 0. N — общее количество синдромов. n используется в качестве основного итератора и для индексации синдромов от 0 до N −1. B ( x ) — копия последнего C ( x ), так как L был обновлен и инициализирован значением 1. b — копия последнего несоответствия d (объясняется ниже), так как L был обновлен и инициализирован значением 1. m — количество итераций, так как L , B ( x ) и b были обновлены и инициализированы значением 1.

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

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

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

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

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

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

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

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

${\displaystyle 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) для произвольного поля:

полином ( поле K ) s ( x ) = ... /* коэффициенты равны s_j; выходная последовательность как полином степени N-1) */ /* полином связи */ полином ( поле K ) C ( x ) = 1 ; /* коэффициенты равны c_j */ полином ( поле K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; поле K b = 1 ; int n ;                         /* шаги 2. и 6. */ for ( n = 0 ; n < N ; n ++ ) { /* шаг 2. вычислить расхождение */ field K d = s_n + ;                 ${\displaystyle \sum _{i=1}^{L}c_{i}\cdot s_{n-i}}$ if ( d == 0 ) { /* шаг 3. расхождение равно нулю; аннигиляция продолжается */ m = m + 1 ; } else if ( 2 * L <= n ) { /* шаг 5. */ /* временная копия C(x) */ полином ( поле K ) T ( x ) = C ( x );                           C ( x ) = C ( x ) - d B ( x ); L = n + 1 - L ; B ( x ) = T ( x ); b = d ; m = 1 ; } else { /* шаг 4. */ C ( x ) = C ( x ) - d B ( x ); m = m + 1 ; } } return L ;      ${\displaystyle b^{-1}x^{m}}$                            ${\displaystyle b^{-1}x^{m}}$        

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

/* ... */ for ( n = 0 ; n < N ; n ++ ) { /* если нечетное число шагов, расхождение == 0, нет необходимости его вычислять */ if (( n & 1 ) != 0 ) { m = m + 1 ; continue ; } /* ... */                     

Смотрите также

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

Ссылки

1. Ридс и Слоан 1985, стр. 2
2. Ридс, Дж.А.; Слоан, NJA (1985), «Синтез сдвиговых регистров (по модулю n)» (PDF) , SIAM Journal on Computing , 14 (3): 505–513, CiteSeerX  10.1.1.48.4652 , doi : 10.1137/0214038
3. Берлекамп, Элвин Р. (1967), Небинарное декодирование BCH , Международный симпозиум по теории информации, Сан-Ремо, Италия{{citation}}: CS1 maint: location missing publisher (link)
4. Берлекамп, Элвин Р. (1984) [1968], Теория алгебраического кодирования (пересмотренная редакция), Лагуна-Хиллз, Калифорния: Aegean Park Press, ISBN 978-0-89412-063-3. Предыдущий издатель McGraw-Hill, Нью-Йорк, штат Нью-Йорк.
5. Massey, JL (январь 1969), «Синтез сдвигового регистра и декодирование BCH» (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122–127, doi :10.1109/TIT.1969.1054260, S2CID  9003708
6. Бен Атти, Надя; Диас-Тока, Хема М.; Ломбарди, Анри (апрель 2006 г.), «Повторный взгляд на алгоритм Берлекэмпа–Месси», Прикладная алгебра в инженерии, коммуникациях и вычислениях , 17 (1): 75–82, arXiv : 2211.11721 , CiteSeerX 10.1.1.96.2743 , doi : 10.1007/s00200-005-0190-z, S2CID  14944277 
7. Мэсси 1969, стр. 124

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

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