Постановка задачи
Ввод: поле; n различных пар элементов в ; и целые числа а также .
Вывод: список всех функций. удовлетворение
является многочленом от степени не более
| | ( 1 ) |
Чтобы лучше понять алгоритм Судана, можно сначала узнать другой алгоритм, который можно рассматривать как более раннюю версию или фундаментальную версию алгоритмов для декодирования RS-кодов по списку - алгоритм Берлекампа – Велча . Первоначально Уэлч и Берлекамп предложили алгоритм, который может решить проблему за полиномиальное время с лучшим порогом на быть . Механизм алгоритма Судана почти такой же, как алгоритм алгоритма Берлекампа – Велча, за исключением шага 1, когда требуется вычислить двумерный многочлен ограниченногостепень. Алгоритм декодирования списка Судана для кода Рида – Соломона, который является улучшением алгоритма Берлекампа и Велча, может решить проблему с помощью. Эта граница лучше, чем уникальная граница декодирования. для .
Алгоритм
Определение 1 (взвешенная степень)
Для весов , то - взвешенная степень монома является . В - взвешенная степень многочлена является максимумом по одночленам с ненулевыми коэффициентами - взвешенная степень монома.
Например, имеет -степень 7
Алгоритм:
Входы: ; {} / * Параметры l, m будут установлены позже. * /
Шаг 1. Найдите ненулевой двумерный многочлен удовлетворение
- имеет -взвешенная степень не более
- Для каждого ,
| | ( 2 ) |
Шаг 2. Разложите Q на неприводимые множители.
Шаг 3. Выведите все многочлены. такой, что является фактором Q и для не менее t значений
Анализ
Необходимо доказать, что приведенный выше алгоритм работает за полиномиальное время и дает правильный результат. Это можно сделать, доказав следующий набор утверждений.
Утверждение 1:
Если функция удовлетворяющее (2) существует, то его можно найти за полиномиальное время.
Доказательство:
Обратите внимание, что двумерный многочлен из -взвешенная степень не более можно однозначно записать как . Затем нужно найти коэффициенты удовлетворение ограничений , для каждого . Это линейная система уравнений с неизвестными {}. Можно найти решение, используя метод исключения Гаусса за полиномиальное время.
Утверждение 2:
Если тогда существует функция удовлетворяющий (2)
Доказательство:
Чтобы гарантировать существование ненулевого решения, количество коэффициентов в должно быть больше, чем количество ограничений. Предположим, что максимальная степень из в m и максимальная степень из в является . Тогда степень будет самое большее . Нужно видеть, что линейная система однородна. Настройкиудовлетворяет всем линейным ограничениям. Однако это не удовлетворяет (2), так как решение может быть тождественно нулевым. Чтобы гарантировать, что существует ненулевое решение, нужно убедиться, что количество неизвестных в линейной системе равно, так что можно иметь ненулевой . Поскольку это значение больше n, переменных больше, чем ограничений, и поэтому существует ненулевое решение.
Утверждение 3:
Если - функция, удовлетворяющая (2) и - функция, удовлетворяющая (1) и , тогда разделяет
Доказательство:
Рассмотрим функцию . Это многочлен от, и утверждают, что он имеет степень не выше . Рассмотрим любой моном из . С имеет -взвешенная степень не более можно сказать, что . Таким образом, термин является многочленом от степени не более . Таким образом имеет высшее образование
Далее утверждают, что тождественно равен нулю. С равен нулю всякий раз, когда можно сказать, что равен нулю для строго больше, чем точки. Таким образомимеет больше нулей, чем его степень и, следовательно, тождественно равен нулю, что означает
Поиск оптимальных значений для а также . Обратите внимание, что а также Для заданного значения , можно вычислить наименьшее для которого выполняется второе условие. Меняя местами второе условие, можно получить быть в лучшем случае Подставляя это значение в первое условие, можно получить быть хотя бы Затем минимизируйте указанное выше уравнение неизвестного параметра. . Это можно сделать, взяв производную уравнения и приравняв ее к нулю. Подставляя обратно ценность в а также один получит
Определение
Рассмотрим Код Рида – Соломона над конечным полем с оценочным набором и положительное целое число , декодер списка Гурусвами-Судана принимает вектор в качестве входных данных и выводит список многочленов степени которые находятся в соответствии 1 к 1 с кодовыми словами.
Идея состоит в том, чтобы добавить больше ограничений на двумерный многочлен что приводит к увеличению ограничений вместе с количеством корней.
Множественность
Двумерный многочлен имеет нуль кратности в Значит это не имеет ученой степени , где x -степень определяется как максимальная степень любого члена x в
Например: пусть .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg
Следовательно, имеет нуль кратности 1 в точке (0,0).
Позволять .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg
Следовательно, имеет нуль кратности 1 в точке (0,0).
Позволять
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg
Следовательно, имеет нуль кратности 2 в точке (0,0).
Аналогично, если Потом, имеет нуль кратности 2 при .
Общее определение множественности
имеет корни в если имеет нуль кратности в когда .
Алгоритм
Пусть переданное кодовое слово будет , быть поддерживающим набором переданного кодового слова и полученного слова быть
Алгоритм следующий:
• Шаг интерполяции
Для полученного вектора , построить ненулевой двумерный многочлен с участием взвешенная степень не более такой, что имеет нуль кратности в каждой из точек где
• Шаг факторизации
Найдите все факторы формы а также как минимум ценности
где & является многочленом степени
Напомним, что многочлены степени находятся в соответствии 1 к 1 с кодовыми словами. Следовательно, этот шаг выводит список кодовых слов.
Анализ
Шаг интерполяции
Лемма: из шага интерполяции следует ограничения на коэффициенты
Позволять где а также
Потом, ........................ (Уравнение 1)
где
Доказательство уравнения 1:
- ................. Использование биномиального разложения
Доказательство леммы:
Полином имеет нуль кратности в если
- такой, что
- может взять ценности как . Таким образом, общее количество ограничений равно
Таким образом, количество вариантов выбора может быть сделано для и каждый выбор подразумевает ограничения на коэффициенты
Шаг факторизации
Предложение:
если фактор
Доказательство:
С, фактор , можно представить как
где, частное, полученное, когда делится на остаток
Сейчас если заменяется на , , только если
Теорема:
Если , тогда фактор
Доказательство:
........................... Из уравнения 2
Дано, мод
Следовательно, мод
Таким образом, фактор .
Как доказано выше,
где LHS - верхняя граница числа коэффициентов RHS - ранее доказанная лемма.
Следовательно,
Заменять ,
Таким образом, доказано, что алгоритм декодирования списка Гурусвами – Судана может перечислить декодируемые коды Рида-Соломона с точностью до ошибки.