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

Введение

Цель данной работы - познакомить читателя с алгоритмом Берлекэмпа-Мэсси, это включает в себя доказательство и некоторые его приложения.

Основная цель алгоритма Берлекэмпа-Мэсси - оценка двоичных кодов BCH (Коды Боуза — Чоудхури — Хоквингема, БЧХ-коды). Двоичные коды - это способ представления данных в виде кода, в котором каждый разряд принимает одно из двух возможных значений, обычно обозначаемых цифрами 0 и 1. Берлекэмп опубликовал свой алгоритм в 1968 году, а вскоре после этого Мэсси опубликовал свой вариант алгоритма в 1969 году. Алгоритм наиболее широко используется как быстрый способ обращения матриц с постоянными диагоналями. Он работает с любым полем, но конечные поля, которые чаще всего встречаются в теории кодирования, являются наиболее часто используемыми. Алгоритм особенно полезен для декодирования различных алгебраических кодов. В своей публикации Берлекэмп обозначил, что алгоритм использует «ключевое уравнение» для ввода известного числа коэффициентов производящей функции и затем определяет оставшиеся коэффициенты полинома. Что полезно в этом алгоритме, так это то, что требуется лишь небольшая часть закодированного сообщения, чтобы иметь возможность его декодировать. Решающий шаг - переформулировать проблему таким образом, чтобы избежать размышлений о матрицах n на n явно, поскольку объем работы с такой операцией слишком большой. Это удалось сделать Берлекэмпу с помощью его ключевого уравнения, а затем повторить Мэсси с помощью его варианта алгоритма. 

Приложения и реализация этого алгоритма были усовершенствованы и расширены Мэсси, который использовали физическую интерпретацию регистра сдвига с линейной обратной связью (LFSR) как инструмент для лучшего понимания алгоритма. Этот вариант синтезирует LFSR с заданной выходной последовательностью. Физическая интерпретация LFSR дает физическое объяснение длины закодированного сообщения, которое нужно расшифровать с помощью алгоритма. Длина необходимого сообщения всего в два раза больше длины LFSR (2n). Теперь, когда у нас есть представление о том, что пытается сделать алгоритм, мы можем увидеть, где он может быть полезен.  

Источник: Хабрахабр