Алгоритмы списочного декодирования специального класса алгебро-геометрических кодов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Маевский, Алексей Эдуардович

• Маевский, Алексей Эдуардович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Маевский, Алексей Эдуардович

Введение

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 Модифицированный алгоритм списочного декодирования

Введение диссертации (часть автореферата) на тему «Алгоритмы списочного декодирования специального класса алгебро-геометрических кодов»

Предмет и актуальность исследования

Широко известно, что при передаче информации как по пространственным, так и по временным каналам связи могут возникать ошибки. В конце 40-х годов прошлого века К. Шеннон показал, что для защиты передаваемых данных от случайных искажений и помех экономически эффективнее применять помехоустойчивые коды, чем строить дорогостоящие каналы высокого качества [29]. С тех пор активное развитие получила теория помехоустойчивого кодирования, в процессе которого найдены различные классы помехоустойчивых кодов и определены границы их применимости (см., например, [26]). Из всего многообразия линейных кодов широкое практическое применение нашли коды Рида-Соломона (РС-коды). Традиционно РС-коды используются, например, для защиты данных на магнитных и оптических носителях [50], в системах спутниковой связи [34], [72], в системах исследования дальнего космоса [57].

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

В 1981 г. В.Д.Гоппа, используя методы алгебраической геометрии, описал новый широкий класс помехоустойчивых кодов - алгебро-геометричес-кие коды (АГ-коды) [4]. Его работа завершила многолетние исследования в области построения наиболее общего класса кодов, включающего в себя классы РС-кодов, циклических кодов и некоторых других используемых на практике кодов. Для построения АГ-кодов он предложил использовать пространства рациональных дифференциальных 1-форм на гладких проективных кривых, такой способ построения позже получил название ^-конструкции (см., например, [3], стр. 264); несколько позже в статье [5] В.Д.Гоппа описал другой способ построения АГ-кодов, основанный на использовании пространств Римана-Роха на гладкой проективной кривой, получивший название Ь-конструкции. Впоследствии были обнаружены другие конструкции АГ-кодов с привлечением более сложных объектов алгебраической геометрии (см., например, [3], стр.266-268). В работе [67] М.А.Цфасман, С.Г.Влэдуц и Т.Цинк показали, что существуют АГ-коды, построенные с помощью весьма специальных кривых, значение минимального расстояния которых гарантированно превышает нижнюю границу Варшамова-Гилберта, существенно продвинувшись, таким образом, к решению одной из центральных в теории кодирования задач построения семейства кодов с асимптотически хорошими параметрами (кодов, у которых при стремлении параметров п, к, й к бесконечности отношения к/п и ¿/п одновременно отличны от нуля) (см. [7], стр. 142, [3], стр. 80). Отметим, что практически все известные семейства кодов, отличные от алгебро-геометрических, либо асимптотически плохи, либо имеют параметры, лежащие на границе Гилберта-Варшамова ([3], стр. 88), поэтому класс АГ-кодов представляет не только теоретический интерес, но и важен для практических приложений. В связи с этим в работе [62] Шокройахи и Вас-сермаи, используя идеи алгоритма Судана, построили алгоритм списочного декодирования некоторых подклассов АГ-кодов, эффективный только для кодов с низкими скоростями, а Гурусвами и Судан в [45] его модифицировали, сняв ограничение на скорость кода. Однако высокая сложность математического аппарата и объектов теории алгебраических кривых, используемых при построении АГ-кодов и алгоритмов декодирования, затрудняет их применение к решению теоретических или практических задач.

В 1988 г. Юстесен и др. в работе [52] упростили ¿-конструкцию Гоп-пы, используя вместо пространства Римана-Роха пространство всех однородных многочленов фиксированной полной степени из однородного координатного кольца гладкой плоской проективной кривой, построив при этом новый подкласс АГ-кодов, содержащий, в частности, РС-коды. Этот новый подкласс АГ-кодов будем далее называть алгебро-геометрическими кодами типа кодов Рида-Соломона (АГРС-кодами). Благодаря тому, что АГРС-коды по своей конструкции гораздо ближе к РС-кодам, чем другие АГ-коды, в той же статье авторы на основе классического алгоритма Пи-терсона декодирования кодов Боуза-Чоудхури-Хоквингема построили без использования дополнительных математических конструкций алгебраической геометрии практически реализуемый полиномиальный алгоритм декодирования кодов, двойственных АГРС-кодам. Дальнейшее развитие этот алгоритм получил в работах [53], [60], где была уменьшена его вычислительная сложность за счет применения алгоритма Сакаты - двумерного аналога алгоритма Берлекэмпа-Месси. Отметим, что существующие алгоритмы декодирования РС-кодов и АГ-кодов непосредственно не могут быть перенесены на класс АГРС-кодов в силу различия базовых математических объектов.

В силу своей конструкции АГРС-коды, как и АГ-коды, обладают следующими характеристиками:

- максимальная длина АГРС-кода над полем ¥д ограничена сверху достижимым числом N1 = д+Ц-2определяемому максимальным количеством Е^-рациональных точек на кривой рода д, в то время как максимальная длина РС-кода над полем ¥д равна д + 1;

- длина п, размерность к и конструктивное расстояние а?* АГРС-кода удовлетворяют двойному неравенству [52]: п — к — <7 + 1<сГ<п — к + 1, поэтому если отношение д/п мало, параметры АГРС-кода лежат близко к границе Синглтона.

Вследствие этого можно ожидать, что при условии существования практически реализуемых эффективных алгоритмов декодирования АГРС-коды наравне с РС-кодами найдут широкое применение в разнообразных прикладных задачах.

В связи с изложенным значимой и актуальной представляется задача построения алгоритмов списочного декодирования и декодирования с ограниченным расстоянием произвольного АГРС-кода с сохранением при этом основной направленности конструкции класса АГРС-кодов на минимальное использование математического аппарата теории алгебраических кривых и алгебраической геометрии.

Необходимо отметить, что одним из важных этапов всех алгоритмов списочного декодирования РС-кодов и АГ-кодов, начиная с алгоритма Судана, является вычисление корней многочлена одной переменной с коэффициентами из кольца ^[я;] многочленов одной переменной над конечным полем в случае РС-кодов, или вычисление корней многочлена одной переменной с коэффициентами из пространств Римана-Роха Ь(О) на плоской проективной кривой над конечным полем в случае АГ-кодов. Задача факторизации многочленов одной или нескольких переменных с коэффициентами из различных алгебраических структур является классической в алгоритмической алгебре, существует множество общих подходов ее решения, например, методы Кронекера, Гензеля, Берлекэмпа, Цассенхауза [8]. Однако использование общих подходов в алгоритмах списочного декодирования неэффективно в силу того, что факторизуемые многочлены могут иметь неприводимые делители высоких степеней, на вычисление или избавление от которых тратится значительная часть вычислительного времени. В силу этого для существующих алгоритмов списочного декодирования разработаны специальные алгоритмы вычисления корней многочленов, ориентированные на использование тонких свойств алгебраических структур, над которыми рассматриваются многочлены. Так, для алгоритмов списочного декодирования РС-кодов первый эффективный полиномиальный алгоритм разработали Рот и Рукенштейн [59]; Ву и Зигель перенесли этот алгоритм на случай списочного декодирования АГ-кодов [71]. Отметим также алгоритмы Ого и Пека [31], Гао и Шокройахи [41], существующие в двух вариантах - для РС-кодов и для АГ-кодов.

В связи с этим представляется актуальным дальнейшее развитие теории и практики вычисления корней многочленов с коэффициентами из различных алгебраических структур, в частности, используемых в конструкциях помехоустойчивых кодов. Например, конструкция АГРС-кодов использует однородное координатное кольцо гладкой плоской проективной кривой над конечным полем, конструкция проективных кодов Рида-Маллера [38] использует кольцо многочленов нескольких переменных над конечным полем. Такие алгоритмы могут найти применение как в существующих, так и разрабатываемых алгоритмах декодирования.

Цель работы

Цель работы - разработка алгоритмов списочного декодирования и декодирования с ограниченным расстоянием произвольного АГРС-кода, а также разработка новых алгоритмов вычисления корней многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой и кольца многочленов нескольких переменных над произвольной областью целостности.

Основные методы исследования

В работе используются методы и результаты теории помехоустойчивого кодирования, в частности, подходы Берлекэмпа-Велча, Судана, Гурусвами

Судана к построению алгоритмов декодирования; алгоритмической алгебры, в частности, подходы Рота-Рукенштейн, Гао-Шокройахи к построению алгоритмов вычисления корней многочленов; линейной и общей алгебры; алгебраической геометрии и коммутативной алгебры в части, касающейся теории проективных алгебраических кривых над конечными полями; теории сложности алгоритмов.

Основные результаты работы

Основные результаты работы, выносимые на защиту, состоят в следующем:

1. Построен полиномиальный алгоритм декодирования с ограниченным расстоянием произвольного АГРС-кода, полностью обоснована его корректность, вычислены максимальное количество исправляемых ошибок и асимптотические верхние границы временной и емкостной сложности в наихудшем случае.

2. Построены базовый и модифицированный полиномиальные алгоритмы списочного декодирования произвольного АГРС-кода. Для каждого алгоритма полностью обоснована корректность, вычислены оценки максимального значения радиуса сферы Хэмминга, внутри которой алгоритм способен вычислить все элементы выходного списка, а также оценки асимптотических верхних границ временной и емкостной сложности в наихудшем случае.

3. Для многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой проективной кривой построены два алгоритма вычисления всех корней, принадлежащих заданной градуи-ровочной компоненте: в случае многочлена первой степени - на основе метода неопределенных коэффициентов, в случае многочленов произвольной степени - на основе подхода Гао-Шокройахи. Для каждого алгоритма полностью обоснована корректность и вычислены асимптотические верхние границы временной и емкостной сложности в наихудшем случае.

4. Построен алгоритм вычисления корней многочленов одной переменной с коэффициентами из кольца многочленов нескольких переменных над произвольной областью целостности, полностью обоснована его корректность и вычислена асимптотическая верхняя граница его временной сложности в наихудшем случае.

Научная новизна

Все основные результаты работы являются новыми.

Теоретическая и практическая ценность

Работа носит теоретический характер. Результаты диссертации могут быть использованы специалистами, работающими в области теории и практики помехоустойчивого кодирования, криптографии, теории обучения, теории распознавания образов.

Апробация результатов

Основные результаты диссертации представлены в виде докладов на следующих конференциях: Международная школа-семинар по анализу и геометрии памяти Н.В. Ефимова (и.Абрау-Дюрсо, 2004 и 2006 гг.), Межрегиональная научно-практическая конференция "Теория и практика создания радиотехнических и мехатронных систем (теория, проектирование, экономика)" (Ростов-на-Дону, 2007 г.), Международная алгебраическая конференция, посвященная 100-летию со дня рождения Д.К.Фаддеева (СПб., 2007 г.), Международная научно-практическая конференция "Информационная безопасность" (Таганрог, 2008 и 2010 гг.), а также неоднократно обсуждались на семинаре "Математические методы в защите информации" кафедры алгебры и дискретной математики мехмата ЮФУ (руководитель - к.ф.-м.н., доцент Деундяк В.М.).

Публикации

Основные результаты опубликованы в 11 работах [15]-[25], из них три работы [15], [16], [25] опубликованы в научных журналах, включенных в перечень ВАК РФ.

В работе [24] автору принадлежит определение понятия поверхности помехоустойчивости, а также способы выбора параметров алгоритма списочного декодирования для решения задачи декодирования по максимуму правдоподобия, в работе [25] автору принадлежит разработка структуры алгебро-геометрического кодека.

Структура диссертации

В главе 1 вводятся необходимые понятия и математические объекты, используемые в работе, приводится конструкция класса АГРС-кодов.

Глава 2 посвящена построению алгоритмов декодирования АГРС-кодов. В начале главы рассматривается постановка основных задач декодирования помехоустойчивых кодов - задачи декодирования с ограниченным расстоянием и задачи списочного декодирования. Далее на основе идей алгоритма Берлекэмпа-Велча декодирования РС-кодов строится алгоритм декодирования АГРС-кодов с ограниченным расстоянием, обосновывается его корректность и вычисляются асимптотические оценки временной и емкостной сложности. Глава продолжается построением базового алгоритма списочного декодирования АГРС-кодов на основе схемы алгоритма Судана декодирования РС-кодов, обоснованием корректности алгоритма, вычислением асимптотических оценок временной и емкостной сложностей, вычислением оценки верхней границы корректирующей способности алгоритма. В конце главы вводятся необходимые понятия и строится модификация базового алгоритма списочного декодирования АГРС-кодов с целью увеличения его корректирующей способности, обосновывается корректность модификации, вычисляются асимптотические оценки временной и емкостной сложностей, оценка корректирующей способности модифицированного алгоритма.

Глава 3 является вспомогательной для главы 2. В начале главы строится алгоритм вычисления корней линейного многочлена одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой, необходимый для реализации шага факторизации алгоритма декодирования АГРС-кода с ограниченным расстоянием. Там же обосновывается корректность алгоритма и вычисляются асимптотические оценки его временной и емкостной сложности. Завершается глава построением алгоритма вычисления корней многочлена одной переменной произвольной степени с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой, необходимого для реализации шага факторизации базового и модифицированного алгоритмов списочного декодирования АГРС-кодов, обоснованием его корректности, вычислением асимптотических оценок временной и емкостной сложности.

В главе 4 рассматривается задача и строится полиномиальный алгоритм вычисления корней многочлена одной переменной с коэффициентами из кольца многочленов нескольких переменных над произвольной областью целостности, обосновывается его корректность и производится асимптотическая оценка временной сложности в наихудшем случае.

Работа завершается выводами.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Маевский, Алексей Эдуардович

Заключение

Основными результатами диссертационной работы являются:

1. Впервые построен полиномиальный алгоритм UniqDecoding декодирования произвольного [п, к, сГ]д-АГРС-кода с ограниченным расстоянием до <1*(з) — 1 — т

ГЦ)~ 1 I а 2т т Корректность алгоритма полностью обоснована и вычислены асимптотические верхние границы оценок временной и емкостной сложностей в наихудшем случае, равные 0(п3) и 0(п2) соответственно.

2. Впервые построены полиномиальные алгоритмы списочного декодирования ListDecoding, MListDecoding произвольного [п, к, (¿*]д-АГРС-кода, полностью обоснована их корректность. Доказано, что максимальный радиус сферы Хэмминга, внутри которой алгоритмами ListDecoding, MListDecodmg вычисляется выходной список, ограничен сверху величиной п — л/п(п — ск*). Для каждого алгоритма вычислены асимптотические верхние границы оценок временной и емкостной сложностей в наихудшем случае, равные соответственно Т(а, Ь, з) + 0(Ьп3), А(а, Ъ,з)-\-0(Ъп2) в случае алгоритма ListDecoding, где Т(а, 6, А(а: Ь,з) - временная и емкостная сложности алгоритма вычисления всех корней многочлена Яа,ь{Т), Т(а, Ь^)+0(Ьп3г5), А(а, 6, з)+0(Ьп2гъ) в случае алгоритма MListDecoding.

3. Для реализации шага факторизации алгоритма UшqDecoding на основе метода неопределенных коэффициентов впервые построен и полностью обоснован полиномиальный алгоритм Р^К/^БиБ вычисления корня линейного многочлена одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой и вычислены асимптотические верхние границы оценок его временной и емкостной сложностей, равные 0(кп2) и 0(с1*кп) соответственно.

4. Для реализации шага факторизации алгоритмов Ь^ОесосИг^, МИ^БесосНг^, а также алгоритма ишдБесосЦг^, впервые построен и полностью обоснован полиномиальный алгоритм ГшсИЗх^бЫ) вычисления всех корней многочлена одной переменной произвольной степени с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой, вычислены асимптотические верхние границы оценок его временной и емкостной сложностей в наихудшем случае, равные Тр(6, е, д) 4- 0(Ьп(п 4 (а 4- )2)), Ар(Ь, е, д) 4-0(Ьп(а 4- Ь?)2 4 к{у){Ъ 4 п)), где Тр(Ь, е, д), Ар(Ъ, е, д) - временная и емкостная сложности алгоритма вычисления всех корней многочлена одной переменной с коэффициентами из поля ¥де.

5. Впервые построен полиномиальный рекурсивный алгоритм ЕтёШ^в вычисления всех корней полной степени не выше с? многочлена Я(Т) одной переменной степени Ь > 1с коэффициентами из кольца многочленов п(> 1) переменных над произвольной областью целостности Р. Полностью обоснована корректность алгоритма и вычислена асимптотическая верхняя граница временной сложности в наихудшем случае, равная

0(Ьйп(Р{Ь) + (5 + Ъй2)2п 4- Ь2^~\з 4 М2П), где б - максимальная из полных степеней коэффициентов многочлена <5(Т), - временная сложность алгоритма вычисления корней многочлена / (Е Ю>[Т] степени Ь.

Результаты, полученные в данной работе, позволяют выделить следующие направления дальнейших исследований:

1. Исследование существующих и поиск новых плоских алгебраических проективных кривых над конечными полями с целью построения АГРС-кодов с параметрами, близкими к параметрам МДР-кодов; точное определение характеристик (максимальной корректирующей способности, значений параметров алгоритмов, сложности) построенных в работе алгоритмов декодирования для выбранных АГРС-кодов.

2. Разработка вычислительно эффективной программной или аппаратной реализации АГРС-кодов и построенных в работе алгоритмов списочного декодирования, декодирования с ограниченным расстоянием.

3. Модификация построенных в работе алгоритмов декодирования АГРС-кодов с целью уменьшения их вычислительной или емкостной сложностей, например, путем применения быстрых методов решения систем линейных уравнений.

4. Исследование возможности модификации методов прикладной математики (связанных, например, с защитой информации, распознаванием образов, самообучением систем), основанных на использовании РС-кодов и алгоритмов их списочного декодирования, путем применения АГРС-кодов на различных кривых и построенных для них алгоритмов списочного декодирования.

5. Распространение построенных в работе алгоритмов декодирования АГРС-кодов на проективные коды Рида-Маллера с использованием на шаге факторизации алгоритма РтсИк^в для случая О =

Список литературы диссертационного исследования кандидат физико-математических наук Маевский, Алексей Эдуардович, 2010 год

1. Атья М., Макдоналд И. Введение в коммутативную алгебру. М.: "Факториал Пресс", 2003. 144 с.

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Издательство "Мир", 1986. 576 с.

3. Влэдуц С.Г., Но?мн Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. М.: МЦНМО, 2003. 504 с.

4. Гоппа В.Д. Коды на алгебраических кривых. // Доклады АН СССР. 1981. Т. 259. № 6. С. 1289-1290.

5. Гоппа В.Д. Алгебраико-геометрические коды. // Известия АН СССР, Серия математическая. 1982. Т. 46. № 4. С. 762-781. ^

6. Зарисский О., Самюэль П. Коммутативная алгебра. В 2 т. Т. 2. М.: Издательство "Мир", 1963. 436 с.

7. Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования. М.: Издательство "Мир", 1978. 576 с.

8. Калтофен Э. Разложение полиномов на множители. // Компьютерная алгебра: символьные и алгебраические вычисления (под ред. Б. Бухбергера, Дж. Коллинза, Р. Лооса). М.: Издательство "Мир", 1986. С. 127-150.

9. Кнэпп Э. Эллиптические кривые. М.: Факториал Пресс, 2004. 488 с.

10. Кнут Д. Искусство программирования для ЭВМ. В 3 т. Т. 2. М.: Издательство "Мир", 1977. 724 с.

11. Кокс Д., ЛиттлДж., О'Ши Д. Идеалы, многообразия и алгоритмы. М.: Издательство "Мир", 2000. 688 с.

12. Коллинз Дэю.Э., Минъотт М., Уинклер Ф. Арифметика в основных алгебраических областях // Компьютерная алгебра: символьные и алгебраические вычисления (под ред. Б. Бухбергера, Дж. Коллинза, Р. Лооса). М.: Издательство "Мир", 1986. С. 237-276.

13. Кормен Т., Лейзерсон Ч., Ривест Р., Штайп К. Алгоритмы: построение и анализ. М.: Издательский дом "Вильяме", 2005. 1296 с.

14. Лидл Р., Нидеррайтер Г. Конечные поля. В 2 т. Т. 1. М.: Издательство "Мир", 1988. 430 с.

15. Маевский А.Э. Алгоритм вычисления корней многочленов с коэффициентами из кольца многочленов над произвольной областью целостности. // Математические заметки, 2009. Т.85. Вып.1. С. 73-88.

16. Маевский А.Э. Алгоритм поиска корней многочленов с коэффициентами из кольца кх,у. // Вестник Донского государственного технического университета, 2007. Т.7. №3(34). С. 263-269.

17. Маевский А.Э. Алгоритм списочного декодирования одного класса алгебро-геометрических кодов на проективных кривых. // Интегральные и дифференциальные уравнения. Сб. статей. Вып. 6. Ростов-на-Дону: ДГТУ, 2007. С. 73-78.

18. Маевский А.Э. Некоторые алгебро-геометрические кодеки и их программная реализация. // Труды участников международной школысеминара по геометрии и анализу памяти Н.В.Ефимова. Ростов-на-Дону: Издательство ООО "ЦВВР", 2004. С. 208-209.

19. Маевский А.Э. О списочном декодировании одного класса алгебро-геометрических кодов на проективных кривых // Труды участников международной школы-семинара по геометрии и анализу памяти Н.В.Ефимова. Ростов-на-Дону: Изд-во ООО "ЦВВР", 2006. С. 55-56.

20. Маевский А.Э. Полиномиальный алгоритм списочного декодирования специального класса алгебро-геометрических кодов // Труды научной школы И.Б.Симоненко. Ростов-на-Дону: Издательство ЮФУ, 2010. С. 145-168.

21. Маевский А.Э., Мкртичян В.В. О некоторых стратегиях детерминиза-ции списочных декодеров // Интегральные и дифференциальные уравнения. Сб. статей. Вып. 6. Ростов-на-Дону: ДГТУ, 2007. С. 79-87.

22. Мак-Вилъямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: "Связь", 1979. 744 с.

23. Сиделъников В.М. Теория кодирования. М.: Физматлит, 2008. 324 с.

24. Харстхорн Р. Алгебраическая геометрия. В 2 т. Т. 1. Новокузнецк: ИО НФМИ, 2000. 368 с.

25. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963. 829 с.

26. Ar Lipton R.J., Rubinfeld R., Sudan M. Reconstructing algebraic functions from mixed data. // SIAM Journal of Computation, 1999. Vol. 28. No. 2. P. 488-511.

27. Augot D., Pecquet L. A Hansel lifting to replace factorization in list-decoding of algebraic-geometry and Reed-Solomon codes. // IEEE Transactions on Information Theory, 2000. Vol. 46. No. 7. P. 2605-2614.

28. Barg A., Blakley G.R., Kabatiansky G.A. Digital fingerprinting codes: problem statements, constructions, identification of traitors. // IEEE Transactions on Information Theory, 2003. Vol.49. P. 852-865.

29. Barg A., Kabatiansky G.A. Class of i.p.p codes with effective tracing algorithm. // Journal of Complexity, 2004. Vol. 20. No 2-3. P. 137-147.

30. Berlekamp E.R., Peile R.E., Pope S.P. The application of error control to communications. // IEEE Communications Magazine, 1987. Vol. 25. P. 4457.

31. Bernardin L. On square-free factorization of multivariate polynomials over a finite fields. // Theoretical computer science, 1997. Vol. 187. No. 1-2. P. 105-116.

32. Cohen H. A course in computational algebraic number theory. Heidelberg: Springer, 1996. 563 pp.

33. Burner I., Kabatiansky G., Tavernier C. List Decoding of Biorthogonal Codes and the Hadamard Transform with Linear Complexity. // IEEE Transactions on Information Theory, 2008. Vol 54. No. 10. P. 4488-4492.

34. Duursma I.M. Algebraic geometry codes: general theory // Advances in algebraic geometry codes (editors E.Martinez-Moro, C.Munuera, D.Ruano), Singapore: World Scientific Publishing Co. Pte. Ltd., 2008. P. 1-48.

35. Elias P. List decoding for noisy channel. Technical Report no. 335, Research Laboratory of Electronics, MIT, 1957.

36. Fulton W. Algebraic curves. An introduction to algebraic geometry. N.-Y.: W.A. Benjamin, Inc., 1969. xiv+226 pp.

37. Gao S.-H., Shokrollahi M. Computing roots of polynomials over function fields of curves. // Coding theory and cryptography: from Enigma and Geheimschreiber to quantum theory (Editor Joyner D.), N.Y.: Springer, 2000. P. 214-228.

38. Goldreich O., Levin L.A. A hard-core predicate for any one-way function. // Proceedings of the 21st Annual ACM Symposium on Foundations of Computer Science, 1995. P. 294-303.

39. Gross W.J., Kschischang F.R., Koetter R., Gulak P.G. Towards a VLSI architecture for interpolation-based soft-decision Reed-Solomon decoders. // The Journal of VLSI Signal Processing, 2005. Vol. 39. No.1-2. P. 93-111.

40. Guruswami V. List decoding of error-correcting codes. Lecture notes in computer science 3282. Springer, 2004. xx+350 pp.

41. Guruswami V., Sudan M. Improved decoding of Reed-Solomon and algebraic-geometry codes. // IEEE Transactions on Information Theory, 1999, September. Vol. 45, P. 1757-1767.

42. Hassett B. Introduction to algebraic geometry. N.-Y.: Cambridge University Press, 2007. xii+252 pp.

43. Hess F. Computing Riemann-Roch spaces in algebraic function fields and related topics. // Journal of Symbolic Computation, 2002. Vol. 33, Iss.4. R 425-445.

44. Hirschfeld J. W.P., Korchmaros G., Torres F. Algebraic curves over a finite field. Princeton: Princeton University Press, 2008. xx+696 pp.

45. Hungerford T.W. Algebra (Graduate texts in Mathematics No. 73). N.-Y.: Springer, 2003. xix+502 pp.

46. Immink K.A.S. Coding techniques for digital recoders. N.-Y.: Prentice-Hall,1991.

47. Jakobsen T. Cryptoanalysis of block ciphers with probabilistic non-linear relation of low degree. // Proceedings of Advances in Cryptography -Crypto'98 (Editor Krawczyk H.). Lecture Notes in Computer Sciences No. 1462, N.-Y.:Springer, 1998.

48. Justesen J., Larsen K.J., Jensen H.E., Havemose A., H0holdt T. Construction and decoding of a class of algebraic geometry codes. // IEEE Transactions on Information Theory, 1989. Vol. 35. N. 4. P. 811-821.

49. Justesen J., Larsen K.J., Jensen H.E., H0holdt T. Fast decoding of codes from algebraic plane curves. // IEEE Transactions on Information Theory,1992. Vol. 38, No. 1. P. 111-119.

50. Kaltofen E., Shoup V. Subquadratic-time factoring of polynomials over finite fields // Mathematics of computation, 1998. Vol. 67(223). P. 11791197.

51. Kaltofen E., Shoup V. Fast polynomial factorization over algebraic extensions of finite fields // Proceedings of ISSAC'97. ACM Press, 1997. P. 184-188.

52. Matsumura H. Commutative algebra. Mathematics Lecture Note Series, vol. 56. Massachusetts: The Benjamin/Cummings Publishing Company, Inc., 1980. xv+313pp.

53. McEliece R.J., Swanson L. Reed-Solomon codes and the exploration of the solar system. // Reed-Solomon codes and their applications (Editors Wicker S.B., Bhargava V.K.). N.-Y.: IEEE Press, 1994.

54. Niederreiter H., Xing C. Rational points on curves over finite fields: Theory and applications. Cambridge: Cambridge University Press, 2002. x+245 pp.

55. Roth R.M., Ruckenstein G. Efficient decoding of Reed-Solomon codes beyond half the minimum distance. // IEEE Transactions on Information Theory, 2000. Vol. 46. P. 246-257.

56. Sakata S., Justesen J., Madelung Y., Jensen H.E., H0holdt T. Fast decoding of algebraic-geometric codes up to the desiged minimum distance. // IEEE Transactions on Information Theory, 1995. Vol. 41. No. 5. P. 16721677.

57. Shaw M., Traub J.F. On the number of multiplications for the evaluation of a polynomial and some of its derivatives // Journal of the ACM, 1974. Vol. 21(1). P. 161-167.

58. Shokrollahi M., Wasserman H. List decoding of algebraic-geometric codes. 11 IEEE Transactions on Information Theory, 1999. Vol. 45. P. 432-437.

59. Silverberg A., Staddon J., Walker J.L. Efficient traitor traicing algorithms using list decoding // Advances in Cryptology ASIACRYPT 2001, Lecture Notes in Computer Science 2248, N.-Y.:Springer, 2001. P. 175-192.

60. Skorobogatov A.N., Vlâduf S.G. On the decoding of algebraic-geometric codes. // IEEE Transactions on Information Theory, 1990. Vol. 36. No. 5. P. 1051-1061.

61. Sudan M. Decoding of Reed Solomon codes beyond the error-correction bound. // Journal of Complexity, 1997. Vol. 13, No. 1. P. 180-193.

62. Sudan M. List decoding: Algorithms and applications. // SIGACT News, 2000. Vol. 31, P. 16-27.

63. Tsfasman M.A., Vladuf S.G., Zink T. Modular curves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound // Mathematical Nachrichten, 1982. Vol. 109. P. 21-28.

64. Vlâduf S. G. On the decoding of algebraic-geometric codes over ¥q for q > 16. // IEEE Transactions on Information Theory, 1990. Vol. 36. N. 11. P. 1461-1463.

65. Welch L.R., Berlekamp E.R. Error correction for algebraic block codes. U.S. Patent 4,633,470, issued Dec. 30, 1986.

66. Wozencraft J.M. List decoding. // Quaterly Progress Report, Research Laboratory of Electronics, MIT, 1958. Vol. 48. P. 90-95.

67. Wu X.-W., Siegel P.H. Efficient root-finding algorithm with application to list decoding of algebraic-geometric codes. // IEEE Transactions on Information Theory, 2001. Vol. 47. No.6. P. 2579-2587.

68. Wu W.W., Haccoun D., Peile R.E., Hirata Y. Coding for satellite communication. // IEEE Journal on Selected Areas in Communications, 1987. Vol. 5. P. 724-785.