Алгоритм Берлекемпа-Масси является алгоритм , который будет найти кратчайший линейный сдвиговый регистр с обратной связью (LFSR) для заданной двоичной выходной последовательности. Алгоритм также найдет минимальный многочлен линейно рекуррентной последовательности в произвольном поле . Требование поля означает, что алгоритм Берлекампа – Месси требует, чтобы все ненулевые элементы имели мультипликативную инверсию. [1] Ридс и Слоан предлагают удлинитель для обработки кольца . [2]
Элвин Берлекамп изобрел алгоритм декодирования кодов Бозе – Чаудхури – Хоквенгема (BCH) . [3] [4] Джеймс Мэсси распознал его применение в регистрах сдвига с линейной обратной связью и упростил алгоритм. [5] [6] Мэсси назвал алгоритм LFSR Synthesis Algorithm (Итерационный алгоритм Берлекампа) [7], но теперь он известен как алгоритм Берлекампа – Месси.
Описание алгоритма
Алгоритм Берлекампа – Месси является альтернативой декодеру Рида – Соломона Петерсона для решения системы линейных уравнений. Его можно резюмировать как нахождение коэффициентов Λ j многочлена Λ ( x ) таким образом, чтобы для всех позиций i во входном потоке S :
В приведенных ниже примерах кода C ( x ) является потенциальным экземпляром Λ ( x ). Полином локатора ошибок C ( x ) для L ошибок определяется как:
или наоборот:
Цель алгоритма - определить минимальную степень L и C ( x ), которая приводит ко всем синдромам
равно 0:
Алгоритм: 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 равно нулю, алгоритм предполагает, что C ( x ) и L верны в данный момент, увеличивает m и продолжает.
Если d не равно нулю, алгоритм корректирует C ( x ) так, чтобы пересчет d был равен нулю:
Х м термин сдвиги В (х) , так что следует синдромы , соответствующие б . Если предыдущее обновление L произошло на итерации j , то m = k - j , и пересчитанное несоответствие будет:
Это изменит пересчитанное расхождение на:
Алгоритм также должен увеличивать L (количество ошибок) по мере необходимости. Если L равно фактическое количество ошибок, то в процессе итерации, расхождения станут нулем , прежде чем п становится больше или равно 2 л . В противном случае 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. вычисление несоответствия * / поле K d = s_n + \ Sigma_ { i = 1 } ^ L c_i * 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 ^ { -1 } x ^ m B ( x ); L = n + 1 - L ; В ( х ) = Т ( х ); b = d ; m = 1 ; } else { / * шаг 4. * / C ( x ) = C ( x ) - d b ^ { -1 } x ^ m B ( x ); м = м + 1 ; } } return L ;
В случае двоичного кода GF (2) BCH расхождение d будет равно нулю на всех нечетных шагах, поэтому можно добавить проверку, чтобы избежать его вычисления.
/ * ... * / for ( n = 0 ; n < N ; n ++ ) { / * если номер шага нечетный, расхождение == 0, вычислять его не нужно * / if (( n & 1 ) ! = 0 ) { m = m + 1 ; продолжить ; } / * ... * /
Смотрите также
- Исправление ошибок Рида – Соломона
- Алгоритм Ридса – Слоана , расширение для последовательностей над целыми числами по модулю n
- NLFSR , Регистр сдвига нелинейной обратной связи
Рекомендации
- ^ Ридс и Слоан 1985 , стр. 2
- ^ Ридс, JA; Sloane, NJA (1985), "Shift-Регистр Synthesis (Modulo п)" (PDF) , SIAM журнал по вычислениям , 14 (3): 505-513, CiteSeerX 10.1.1.48.4652 , DOI : 10,1137 / 0214038
- ^ Берлекамп, Элвин Р. (1967), Недвоичное декодирование BCH , Международный симпозиум по теории информации, Сан-Ремо, Италия
- ^ Берлекамп, Элвин Р. (1984) [1968], Алгебраическая теория кодирования (пересмотренная редакция), Лагуна-Хиллз, Калифорния: Aegean Park Press, ISBN 978-0-89412-063-3. Предыдущее издательство McGraw-Hill, Нью-Йорк, штат Нью-Йорк.
- ^ Масси, ДЛ (январь 1969), "Синтез регистра сдвига и ВСН декодирования" (PDF) , IEEE Transactions по теории информации , ИТ-15 (1): 122-127, DOI : 10,1109 / TIT.1969.1054260
- ^ Бен Атти, Надя; Diaz-Toca, Gema M .; Lombardi, Анри (апрель 2006), "Берлекэмпа-Massey алгоритм вновь" , Применимое алгебра в инженерной, связи и вычислительной техники , 17 (1): 75-82, CiteSeerX 10.1.1.96.2743 , DOI : 10.1007 / s00200-005- 0190-z
- Перейти ↑ Massey 1969 , p. 124
Внешние ссылки
- "Алгоритм Берлекампа-Месси" , Энциклопедия математики , EMS Press , 2001 [1994]
- Алгоритм Берлекампа – Месси в PlanetMath .
- Вайсштейн, Эрик В. "Алгоритм Берлекампа – Месси" . MathWorld .
- Реализация GF (2) в системе Mathematica
- (на немецком языке) Апплет Алгоритм Берлекампа – Месси
- Онлайн калькулятор GF (2) Берлекамп-Месси