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

Первоначальная версия алгоритма Берлекэмпа–Месси была изложе-
на Берлекэмпом в 1968 году [1] в качестве элемента конструкции декодера
кодов Боуза–Чоудхудри–Хоквингема над конечным полем. Хотя в этой ра-
боте была указана возможность формулировки решаемой задачи с исполь-
зованием понятия линейного регистра сдвига с обратной связью, алгоритм
описывался исключительно в терминах полиномов и был весьма сложен
для понимания. Спустя год Месси [2] предложил свою интерпретацию ал-
горитма, как позволяющего строить линейный регистр сдвига минималь-
ной длины, генерирующий заданную последовательность. Эта интерпрета-
ция оказалась полезной для более широкого распространения алгоритма,
получившего название по имени этих двух ученых. В некоторых работах
алгоритм излагается также с помощью непрерывных дробей и рациональ-
ной аппроксимации.

1. Введение и постановка задачи.......................................................................3
2. Алгоритм Берлекэмпа–Месси........................................................................5
3. Реализация алгоритма Берлекэмпа–Месси.................................................14
3.1. Архитектура реализации .......................................................................15
3.2. Класс линейного регистра сдвига.........................................................16
3.3. Класс алгоритма .....................................................................................17
3.4. Тестирование ..........................................................................................18
4. Декодер для кодов Рида–Соломона ............................................................21
5. Литература ......................