Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Алгоритмы списочного декодирования специального класса алгебро-геометрических кодов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В 1981 г. В. Д. Гоппа, используя методы алгебраической геометрии, описал новый широкий класс помехоустойчивых кодов — алгебро-геометричес-кие коды (АГ-коды). Его работа завершила многолетние исследования в области построения наиболее общего класса кодов, включающего в себя классы РС-кодов, циклических кодов и некоторых других используемых на практике кодов. Для построения АГ-кодов он предложил… Читать ещё >

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

Содержание

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

Показать весь текст

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

  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. 11 791 197.
  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. 16 721 677.
  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., Vladuf 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. Vladuf 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.
Заполнить форму текущей работой

Сессия? Спокойно!