Алгоритмы списочного декодирования специального класса алгебро-геометрических кодов

• Автор: Маевский, Алексей Эдуардович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ростов-на-Дону
• Количество страниц: 141 с. : ил.

Оглавление
Введение

1 Предварительные сведения

1.1 Линейные коды

1.2 Многочлены нескольких переменных

1.3 Аффинное и проективное пространства

1.4 Плоские проективные кривые

1.5 Однородное координатное кольцо

1.6 Кратность пересечения проективных кривых

1.7 Алгебро-геометрические коды типа кодов Рида-Соломона . .

1.8 Модель вычислений
2 Алгоритмы декодирования АГРС-кодов
2.1 Задачи декодирования линейных кодов
2.2 Алгоритм декодирования с ограниченным расстоянием
2.3 Базовый алгоритм списочного декодирования
2.4 Модифицированный алгоритм списочного декодирования . .
2.5 Заключение к главе
3 Алгоритмы вычисления Т-корней многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой
3.1 Алгоритм вычисления Т-корня линейного многочлена
3.2 Алгоритм вычисления Т-корней многочлена произвольной
степени
3.3 Заключение к главе

4 Алгоритм вычисления Т-корней многочленов одной переменной с коэффициентами из кольца многочленов нескольких переменных над произвольной областью целостности
4.1 Постановка задачи
4.2 Специальные многочлены и некоторые свойства Т-корней .
4.3 Алгоритм вычисления множества всех Т-корней
4.4 Анализ сложности алгоритма вычисления Т-корней
4.5 Заключение к главе
Заключение
Литература

Введение
Предмет и актуальность исследования
Широко известно, что при передаче информации как по пространственным, так и по временным каналам связи могут возникать ошибки. В конце 40-х годов прошлого века К. Шеннон показал, что для защиты передаваемых данных от случайных искажений и помех экономически эффективнее применять помехоустойчивые коды, чем строить дорогостоящие каналы высокого качества [29]. С тех пор активное развитие получила теория помехоустойчивого кодирования, в процессе которого найдены различные классы помехоустойчивых кодов и определены границы их применимости (см., например, [26|). Из всего многообразия линейных кодов широкое практическое применение нашли коды Рида-Соломона (РС-коды). Традиционно РС-коды используются, например, для защиты данных на магнитных и оптических носителях [50], в системах спутниковой связи [34], [72], в системах исследования дальнего космоса [57].
В 1997 г. М.Судан в работе [65] построил первый полиномиальный алгоритм, решающий задачу списочного декодирования РС-кодов, сформулированную для произвольных кодов Элайесом [39] и Возенкрафтом [70] еще в середине 1950-х годов. Алгоритм Судана оказался эффективным только для РС-кодов, имеющих скорость до 1/3, поэтому несколько позже Гурусвами и Судан в работе [45] модифицировали алгоритм Судана, сняв ограничение на скорость РС-кодов. Благодаря алгоритмам Судана и Гурусвами-Судана РС-коды нашли применение при решении многих прикладных задач, изначально далеких от теории кодирования, таких как предотвращение несанкционированного копирования компакт-дисков [32], [33], [63] самообучение систем и распознавание образов [30], построение односторонних функций для криптографических целей [66], криптоанализ некоторых блочных шифров [51]. Отметим, что с каждым годом круг

Исходя из этого легко проверить, что АГРС-код СрДз) в случае у > т — 2 является кодом рода не выше д.
Вычислим одну из порождающих матриц АГРС-кода Ср,л{з)- Для этого зафиксируем базис градуировочной компоненты {^q['PF])j■
Лемма 1.7. Для всех в Є N множество
Мр(в) = {х^Х^Х^ І І + І2 + ?’з = 5, ЬТ(^) { хгХго хг33}
является базисом градуировочной компоненты ^[Рр]),; кольца ¥чРр.
Доказательство. Ясно, что М^(я) С (^[Т^р]).;. Предположим, что однородный многочлен (С из линейной оболочки, натянутой на множество Мр(,з) над полем принадлежит (/р),;. Так как идеал /р главный, то любой многочлен из (/рД делится на Г без остатка, поэтому необходимым условием принадлежности С подпространству (/рД является делимость ЬТ(С) па ЬТ(А'). Поскольку ни один моном из Мр(в) не делится на ЬТ(Т'), приходим к противоречию и никакая нетривиальная линейная комбинация мономов из Мр(й) не принадлежит (/рД. Как следствие, никакие два различных многочлена из линейной оболочки, натянутой на Мр(з), не принадлежат одному классу эквивалентности факторпространства (Т?['Рр])5.
Покажем, что Мр{в) = бшфТ^Рр]),;. Общее количество мономов трех переменных полной степени з равно (5 + 1)(з + 2)/2, а количество мономов той же полной степени, делящихся на заданный моном степени т (< я), равно (в — ти. + 1)(й — т + 2)/2. Следовательно, |Мр(5)| = ЛрДв).
Лемма доказана.
Упорядочив каким-либо образом мономы ф,, фк^ множества Мр(;у) (например, в соответствии с порядком >р) и точки Рі,... ,Рп множества А, получим порождающую матрицу АГРС-кода Ср,л(,з):
/ фі(Рі) фі(Р2) ... Фі(Рп) с{.)= ИРі) ф2(р2) ... МРп) ФкЬ){Рі) Фю(Ъ) ••• Фк(л(Рп) )