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

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

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

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

Применение алгоритма

Как указано выше, алгоритм имеет дело с декодированием двоичных кодов BCH, включая коды Рида - Соломона. Непосредственный интерес представлял более эффективный способ декодирования этого типа кодов в его алгоритме. Использование его алгоритма в качестве инструмента декодирования варьировалось от стандарта связи NASA в дальнем космосе до декодирования в CD проигрывателях. Кроме того, множество вариаций и аналогичные алгоритмы также использовались в похожих процедурах декодирования.

Регистры сдвига с линейной обратной связью

Регистры сдвига с линейной обратной связью используются в криптографии как инструменты дляповышения эффективности шифров. Данные регистры сдвига с линейной обратной связью (РСЛОС) — это инструменты, используемые при кодировании и декодировании последовательности с помощью простой линейной формулы.

Для создания линейного регистра сдвига обратной связи, мы сначала зафиксировать размер N, этот N является числом выбранных коэффициентов, а также размером исходного ядра. Также выбираем модуль m (обычно m = 2). Затем выбираем коэффициенты c = (c₀, c₁, …, c_N-1), а также выбираем начальное состояние ядра s = (s₀, s₁, …, s_N-1). Из этих простых определений мы можем рекурсивно определить s_N+1 когда n + 1 > N :

по модулю m

Это рекурсивное определение, которое можно использовать для определения всего ключевого потока, можно очень легко записать в терминах матриц. В качестве примера выберем N = 5 и m = 2. Итак, наши коэффициенты c = (c₀, c₁, c₂, c₃, c₄), тогда мы можем сделать матрицу C и из этой матрицы рекурсивное соотношение:

по модулю 2

Из этого уравнения видно, что разные варианты выбора для c = ( c₀, c₁, c₂, c₃, c₄ ) и для s = ( s₀, s₁, s₂, s₃, s₄ ) будут созданы разные потоки ключей, и потоки ключей будут иметь разные периоды.

Затем с помощью алгоритма Берлекэмпа-Мэсси решаются уравнения для всех c, где c = ( c₀, c₁, …,c_N-1 ), используя только 2n членов, где n = длина периода РСЛОС, связанного с определенным ключевым потоком. Прежде чем мы сможем предоставить доказательство алгоритма или даже попытаться понять его, нам нужно понять, как Берлекэмп пришел к «ключевому уравнению». Как только мы это установим, мы можем перейти к его решению.

Круговые многочлены и первообразные корни

Мы можем начать с нахождения всех комплексных нулей xⁿ - 1. Обозначим w как следствие из Теоремы ДеМуавра, которая утверждает, что для любого положительного целого числа n, и для любого действительного числа θ, верно:

обозначили w

так, что wⁿ = 1 и w^k ¹ 1 для 1 < k < n. Следовательно, каждый из 1, w, w², …, w^n-1 - это нуль sⁿ = 1, и, следственно, из алгоритма деления многочленов, который утверждает, что многочлен степени n над полем имеет не более n нулей с учетом кратности, там нет других нулей. Комплексное число w называется первообразным корнем n-ой степени из единицы. Для того чтобы показать, как вычисляются круговые многочлены, будет полезно получить более формальное определение первообразных корней. Первообразные корни похожи на генераторы циклических групп. Рассмотрим w как определено выше. Оно является генератором циклической группы порядка n по операции умножения. Эту циклическую группу можно обозначить как < w > и из следующей теоремы о генераторах циклических групп, мы знаем, что генераторы < w > – это элементы вида w^k, где 1 £ k < n и gcd( n, k ) = 1, где функцией gcd обозначен генератор циклической группы. Эти образующие (генераторы) называются первообразными корнями n-ой степени из единицы.

Теорема: образующие циклических групп

Пусть G = < a > - циклическая группа порядка n. Тогда G = < a^k > тогда и только тогда, когда gcd(n, k) = 1

Теперь, когда мы лучше понимаем, что такое первообразный корень, мы можем перейти к рассмотрению циклотомических полиномов и тому, почему эти полиномы важны. Вспомним функцию Эйлера f(n) как обозначение числа положительных целых чисел меньше или равных n и взаимно простых с n. Таким образом, для каждого натурального n есть ровно f(n) первообразных корней n-й степени из единицы. Многочлены, нули которых лежат на f(n) первообразных корнях n-й степени единицы называются круговыми многочленами.

Определение: циклотомические многочлены

Пусть для любого натурального числа n, w₁, w₂, …,w_f(n) обозначают первообразные корни n-ой степени из единицы. N-й круговой многочлен над Q является многочленом вида:

*Примечание: F_n(x) является моническим (т.е многочленом одной переменной со старшим коэффициентом равным 1) и имеет степени f(n), где f(n) - функция Эйлера.*

Вместо того, чтобы использовать это определение F_n(x) для его вычисления, на практике проще использовать следующую формулу, а затем рекурсивно использовать результат.

Для каждого целого положительного n действительна следующая формула:

произведение над всеми положительными делителями n

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

Вывод ключевого уравнения

Чтобы создать двоичный код BCH (БЧХ), способный исправлять t или меньше ошибок, сначала выбираем несократимый двоичный множитель кругового многочлена F_n над Q . Степень неприводимого бинарного множителя равна мультипликативному порядку 2 по модулю n, который обозначается m . Поскольку мы знаем, что степень неприводимого двоичного множителя - m, и что 2^m mod n = 1 в конечном поле GF(2^m) отсюда можем ввести a принадлежащее GF(2^m) - корень неприводимого двоичного многочлена. Как только мы обозначили корень нашего многочлена, мы можем построить наш двоичный код BCH.

Определение ключевого уравнения для декодирования двоичных кодов BCH

 Предположим, что кодер передает двоичное BCH кодовое слово:

При передаче слова возможно, что шум канала может вызвать аддитивные ошибки в коэффициентах двоичного многочлена. Эти ошибки могут быть представлены следующим уравнением и затем изменить полученное кодовое слово на R(x) = C(x) + E(x)

Уравнение ошибок

Вариант записи R(x)

Уравнение A

 Для j = 1, 2, …, 2t кодовое слово кратно минимальному многочлену по a^j. Пусть M^(j)(x) – минимальный многочлен по a^j при условии (1 <  j < 2t). Итак, полученное слово можно записать как

Уравнение B

Здесь t - максимальное количество ошибок, которое может исправить код, e - количество произошедших ошибок. Местоположение ошибки поля Галуа X₁, X₂, …, X_e обозначает позиции, где E_i = 1 (где произошла ошибка). Теперь, если полученное слово R(x) из Уравнения A делится на M^(j)(x) и S_j = R(a^j) может быть вычислено из остатка r^(j)(a^j ). Это можно сделать с помощью матрицы проверки на четность.

--------------

В качестве примера: если полученное слово R(x) представлено, как указано выше, S₁ дает сумму ошибки положений, а S₂ дает сумму квадратов положений ошибок, тогда S₁ = R(a) и S₂ = R(a²)

--------------

Таким образом, для вычисления S - 1, разделим R(x) на M⁽¹⁾(x) и получим остаток r⁽¹⁾(x) и, следовательно, S₁ = r⁽¹⁾(a). Аналогично, чтобы вычислить S₂, мы разделим R(x) на M⁽²⁾(x) и получим остаток r⁽²⁾(x). Тогда S₂ = r⁽²⁾(a²). 

После вычисления S₁, S₂, …, S_2t, вопрос состоит в том, чтобы найти X₁, X₂, …, X_e из уравнений

 j = 1, 2, …, 2t

Уравнение C

У этих уравнений есть много решений, каждое из которых соответствует различным типам ошибок в одном и том же классе аддитивных групп кодовых слов. По понятным причинам мы хотим найти решение с минимальным значением е. Для этого необходимо ввести полином локатора ошибок Берлекэмпа:

Уравнение D

[Метод Берлекэмпа для нахождения этого уравнения слишком обширен для этой статьи, но его можно найти в его книге Алгебраическая теория кодирования, переработанное издание, 1984 г., глава 1.]

После того, как декодер найдет многочлен локатора ошибок s(z), обратные корни (мультипликативно обратные) можно найти, выполнив Chien search (алгоритм поиска корней многочленов, определенных на конечном поле). Как только это будет выполнено, ошибки можно будет исправить.

Самая сложная часть декодирования — это найти s(z) из S. Чтобы получить связь между s(x) и S, мы должны ввести порождающую функцию:

Уравнение E

Теперь мы можем выполнить сокращения в последней сумме, тогда получается следующее уравнение. Из него сразу же прибавляем s(z) к обеим сторонам и вводим многочлен w(z):

Уравнение F

У нас получается уравнение [1 + S(z)]s(x) = w(z). Как правило, декодеру известно только ограниченное число коэффициентов при степенях z в S(z). (А именно, только первые 2t степени). Поэтому неизвестными остаются S_2t+1, _S2t+2, S_2t+3,…Итак, хотя S(z) неизвестно, из-за модульной арифметики декодер действительно знает результат S(z) mod z^2t+1. Этот факт раскрывает ключевое уравнение Берлекэмпа.

Ключевое уравнение

Уравнение G

Здесь S(z) - известная производящая функция, а ее коэффициенты – известны на входе. s(z) и w(z)- два неизвестных многочлена со степенью < e (где e - количество ошибок, которые действительно произошли). Коэффициенты этих многочленов станут выходными данными алгоритма.

Заключение

Как мы можем видеть из доказательства и выражения алгоритма, его понимание - это сложный процесс. Алгоритм используется и в наше время, послужил основой для многих исследований.

Список литературы:

1.     Корни из единицы [Электронный ресурс] https://ru.wikipedia.org/wiki/Корниизединицы

2.     Тер-Крикоров А.М., Шабунин М.И.  Курс математического анализа. Учебник для вузов, 2001. 672 с.

3.     Erin Casey, “Berlekamp-Massey Algorithm”, 2000

4.     David C. Arney, Joseph Gallian, and Paul Campbell, “Principles and Practice of Mathematics: COMAP”

5.     Berlekamp's Algebraic Coding Theory, Revised edition, 1984

6.     Chien поиск [Электронный ресурс] https://en.wikipedia.org/wiki/Chiensearch

7.     Gallian, Joseph A. Contemporary Abstract Algebra, Houghton Miin Company, Boston, 1998.

8.     Garrett, Paul. Error Correcting Codes. Notes 1999-2000.

9.     Garrett, Paul. Introduction to Cryptography. Notes. 2000.

10.  Пан, Виктор. Конечные поля «Новые методы вычисления коэффициентов линейной повторяемости» и их приложения. Том 6. 2000, с.93-118

11.  Двоичный код [Электронный ресурс] https://ru.wikipedia.org/wiki/Двоичныйкод