Об алгоритме Берлекэмпа — Месси и его применении в алгоритмах декодирования

В работе содержатся описание алгоритма Берлекэмпа — Месси и его эквивалентный вариант на основе обобщенного алгоритма Евклида. Также приводится оптимизированный алгоритм Берлекэмпа — Месси для случая поля характеристики два. Алгоритм Берлекэмпа — Месси имеет квадратичную сложность и применяется, например, для решения систем линейных уравнений, у которых матрица системы является матрицей Тёплица. В частности, такие системы уравнений появляются в алгоритмах синдромного декодирования кодов БЧХ, кодов Рида — Соломона, обобщенных кодов Рида — Соломона, кодов Гоппы. Приводятся алгоритмы декодирования перечисленных кодов на основе алгоритма Берлекэмпа — Месси.