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

На правах рукописи

МАЕВСКИЙ Алексей Эдуардович

АЛГОРИТМЫ СПИСОЧНОГО ДЕКОДИРОВАНИЯ СПЕЦИАЛЬНОГО КЛАССА АЛГЕБРО-ГЕОМЕТРИЧЕСКИХ КОДОВ

Специальность 01.01.09 - дискретная математика и математическая

кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

о з огз 2011

Ярославль - 2011

4853803

Работа выполнена на кафедро алгебры н дискретной математики факультета математики, механики и компьютерных наук Южного федерального университета

Научный руководитель: кандидат физико-математических наук,

доцент Деупдяк Владимир Михайлович

Официальные оппоненты: доктор физико-математических наук

Кабатянскпн Григорий Анатольевич

кандидат физико-математических наук, доцент Стукогшн Владимир Алексеевич

Ведущая организация: Институт систем информатики им.

А.П.Ершова Сибирского отделения РАН

Защита диссертации состоится 25 февраля 2011 года в 14 ч. 00 мин. на заседании диссертационного совета Д.212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 426.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г. Демидова

Автореферат разослан « /1>-)» января 2011 г.

Ученый секретарь диссертационного совета Яблокова С.И.

Общая характеристика работы

Актуальность темы

Широко известно, что при передаче информации как по пространственным, так и по временным каналам связи могут возникать ошибки. В конце 40-х годов прошлого века К. Шеннон показал, что для защиты передаваемых данных от случайных искажений и помех экономически эффективнее применять помехоустойчивые коды, чем строить дорогостоящие каналы высокого качества. С тех пор активное развитие получила теория помехоустойчивого кодирования, в процессе которого найдены различные классы помехоустойчивых кодов и определены границы их применимости. Из всего многообразия линейных кодов широкое практическое применение нашли коды Рпда-Соломона (PC-коды); традиционно PC-коды используются, например, для защиты данных на носителях информации1, в системах спутниковой связи2, в системах исследования дальнего космоса3.

В 1997 г. М.Судан4 построил первый полиномиальный алгоритм, решающий задачу списочного декодирования PC-кодов, сформулированную для произвольных кодов Элайесом5 и Возенкрафтом6 еще в середине 1950-х годов. Алгоритм Судана оказался эффективным только для PC-кодов, имеющих скорость до 1/3, поэтому несколько позже Гурусвами и Судан7 модифицировали алгоритм Судана, сняв ограничение на скорость PC-кодов. Благодаря алгоритмам Судана и Гурусвами-Судана PC-коды нашли применение при решении многих прикладных задач, изначально далеких от

lImmmk K.A.S. Coding techniques for digital recoders. N.-Y.: Prentice-IIall, 1991.

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

■'A/cAYicce II.J., Swanson L. Reed-Solonion codcs and the exploration of the solar system. // ReedSolomon codcs and their applications (Editors Wicker S.B., Bhargava V.K.). N.-Y.: IEEE Press, 1991.

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

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

6 Wiizrncrafl. J.M. List decoding. // Quatcrly Progress Report, Research Laboratory of Electronics, MIT, 1958. Vol. 48. P. 90-95.

7Cumswami V., Sudan M. Improved decoding of Reed-Solomon and algebraic-geometry codes. // IEEE Transactions on Information Theory, 1999, September. Vol. 15, P. 1757-17G7.

теории кодирования, таких как предотвращение несанкционированного копирования компакт-дисков8 9, самообучение сие,тем и распознавание обра^ зов10, построение односторонних функций для криптографических целей11, криптоанализ некоторых блочных шифров12. Отмстим, что с каждым годом круг прикладных задач, решаемых с помощью списочного декодирования, интенсивно расширяется, вследствие чего возрастает и актуальность задачи улучшения характеристик существующих и построения новых алгоритмов списочного декодирования как PC-кодов, так и других помехоустойчивых кодов.

В 1981 г. В.Д.Гоппа, используя методы алгебраической геометрии, описал новый широкий класс помехоустойчивых кодов - алгебро-геометричес-кпе коды13 (АГ-коды). Его работа завершила многолетипе исследования в области построения наиболее общего класса кодов, включающего в себя классы PC-кодов, циклических кодов и некоторых других используемых на практике кодов. Для построения АГ-кодов он предложил использовать пространства рациональных дифференциальных 1-форм на гладких проективных кривых, такой способ построения позже получил название П-конструкщш. Несколько позже В.Д.Гоппа опием другой способ построения АГ-кодов1 \ основанный на использовании пространств Римана-Роха на гладкой проективной кривой, получивший название ¿-конструкции. Впоследствии были обнаружены другие конструкции АГ-кодов с привлечением более сложных объектов алгебраической геометрии. М.А.Цфасман,

sSiberberg A., Staddan J., Waiter J.L. Efficient traitor traicing algorithms using list decoding // Advances in Cryptology - ASIACRYPT 2001, LNCS 2248, N.-Y.:Springer, 2001. P. 175-192.

9Barg A., Kabatiansky O.A. Class of i.p.p codes with eííective tracing algorithm // Journal of Complexity, 2004. Vol. 20. No 2-3, P.137-147.

10/lr S., Lipton R.J., Rubinfeld R., Sudan M. Reconstructing algebraic functions from mixed data. // SUM Journal of Computation, 1090. Vol. 28. No. 2. P. 488-511.

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

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

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

14 Гоппа В.Д. Алгебрацко-геоыетрические коды. // Изиесшя All СССР, Серия математическая. 1982. Т. 40. № 4. С. 762-781.

С.Г.Влэдуц и Т.Цинк показали1'1', что существуют АГ-коды, построенные с помощью весьма специальных кривых, значение минимального расстояния которых гарантированно превышает нижнюю границу Варшамова-Гилберта, существенно продвинувшись, таким образом, к решению одной нз центральных в теории кодирования задач построения семейства кодов с асимптотически хорошими параметрами (кодов, у которых при стремлении параметров п, k, d к бесконечности отношения к/п и d/n одновременно отличны от нуля). Отметим, что практически все известные семейства кодов, отличные от алгебро-геометрнчеекпх, либо асимптотически плохи, либо имеют параметры, лежащие на границе Гилберта-Варшамова, поэтому класс ЛГ-кодов представляет не только теоретический интерес, по и важен для практических приложений16. В связи с этим Шокройахи и Вассермап17, используя идеи алгоритма Судана, построили алгоритм списочного декодирования некоторых подклассов АГ-кодов, эффективный только для кодов с низкими скоростями, а Гурусвами и Судан18 его модифицировали, сняв ограничение на скорость кода. Однако высокая сложность математического аппарата и объектов теории алгебраических кривых, используемых при построении АГ-кодов и алгоритмов декодирования, затрудняет их применение к решению теоретических пли практических задач.

В 1988 г. Юстесен п др.19 упростили ¿-конструкцию Гонпы, используя вместо пространства Рнмана-Роха пространство всех однородных многочленов фиксированной полной степени из однородного координатного кольца гладкой плоской проективной кривой, построив при этом новый подкласс АГ-кодов, содержащий, в частности, PC-коды. Этот подкласс АГ-

Tsfasman M.Л., Vlädul S.С., Zink T. Modular curves, Shimura curves and Goppa codes, better llian Varshamov-Gilbcrt bound // Mathcmatical Nachrichten, 1982. Vol. 109. P. 21-28.

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

17Shokrollahi M., Wasscrman II. List decoding of algebraic-gcometric codes. // IEEE Transactions on Information Theory, 1999. Vol. 45. P. 432-437.

18GuniMPtuni V., Sudan M. hnproved decoding of Kcod-Solomon and algobraic-geometry codes. // IL]EE Transactions on Information Theory, 1999, September. Vol. 45. P. 1757-1767.

19Justesen ,/., Larsen K.J., Jensen II.E., Ilavemose A., Hpholdl T. Construction and decoding of a class of ulgebruic geometry codes. // IEEE Transactions on Information Theory, Î989. Vo!. 35. N. '1. P. 811-821.

кодов будем далее называть алгебро-геометрическнмн кодами типа кодов Рида-Соломона (АГРС-кодами). Благодаря тому, что АГРС-коды по своей конструкции гораздо ближе к РС-кодам, чем другие АГ-коды, в той же статье авторы на основе классического алгоритма Питерсона декодирования кодов Боуза-Чоудхури-Хоквингема построили без использования дополнительных математических конструкций алгебраической геометрии практически реализуемый полиномиальный алгоритм декодирования кодов, двойственных АГРС-кодам. Отметим, что существующие алгоритмы декодирования РС-кодов и АГ-кодов непосредственно не могут быть перенесены на класс АГРС-кодов в силу различия базовых математических объектов.

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

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

- длина п, размерность к и конструктивное расстояние <1* АГРС-кода удовлетворяют двойному неравенству:

п-к-д+1<с1*<п-к+1,

поэтому если отношение д/п мало, параметры АГРС-кода лежат близко к границе Синглтона,

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

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

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

Необходимо отметить, что одним из важных этапов всех алгоритмов списочного декодирования PC-кодов и АГ-кодов, начиная с алгоритма Судана, является вычисление корней многочлена, одной переменной с коэффициентами из кольца Fg[x] многочленов одной переменной над конечным полем в случае PC-кодов или вычисление корней многочлена одной переменной с коэффициентами из пространств Рпмана-Роха L(D) на плоской проективной кривой над конечным полем в случае АГ-кодов. Задача факторизации многочленов одной пли нескольких переменных с коэффициентами из различных алгебраических структур является классической в алгоритмической алгебре, существует множество общих подходов ее решения, например, методы Кронсксра, Гензеля, Берлекэмпа, Цассеихауза. Однако использование общих подходов в алгоритмах списочного декодирования неэффективно в силу того, что факторнзуемые многочлены могут иметь неприводимые делители высоких степеней, на вычисление или избавление от которых тратится значительная часть вычислительного времени. В силу этого для существующих алгоритмов списочного декодирования разработаны специальные алгоритмы вычисления корней многочленов, ориентированные на использование тонких свойств алгебраических структур, над которыми рассматриваются многочлены. Так, для алгоритмов списочного декодирования PC-кодов первый эффективный полиномиальный алгоритм разработали Рог н Рукенштейн20; By и Знгель21 перенесли этот алгоритм на случай списочного декодирования АГ-кодов. Отметим также алгоритмы Ого и Пека22, Гао н Шокройахи23, существующие в двух вариантах

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

21 Wu X.-W., Siegd P.II. 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.

11 A u'}ot D., l'l rija.!'! !,. A Hansel lift ing 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.

23Gao S.-H., Shokrollalii 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.:

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

Цель работы

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

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

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

Springer, 2000. Г. 214-228.

24Duursma I.M. Algebiaic geometry Codes: general theory // Advances in algebraic geometry Codes (editors RMurtiirez-Moi o, C.Munuera, D.Rnano), Singapur«: World Scientific Publishing Co. Pte. Ltd., 2008. Р. M8.

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

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

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

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

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

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

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

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

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

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

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

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

Публикации 25

Основные результаты опубликованы в 11 работах [1-11].

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

25Работа поддержана ФЦП "Научные н научно-педагогические кадры инновационной России", Государственный контракт №02.710.11.0208 от 7 июля 2009 г.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы, содержащего 72 наименования, включая работы автора. Полный объем диссертации составляет 141 страницу машинописного текста.

Краткое содержание работы

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

Первая глава содержит предварительные сведепня из теории линейных помехоустойчивых кодов, теории градуированных колец, теории проективных алгебраических кривых. В частности, приводятся определения однородного координатного кольца ¥ч\Рр\ гладкой плоской проективной кривой Р/г над конечным полем как градуированного кольца ФУ11КЦ1Ш Гильберта Н кольца ¥я['Рр}, локального кольца О^р точки Р кривой Рр, кратности пересечения плоских проективных кривых в терминах локальных колец. В конце главы вводится конструкция класса АГРС-кодов, рассматриваются формулы вычисления их параметров, обсуждается связь с РС-кодами и АГ-кодамп, выбирается модель вычислений для оценки сложности построенных в работе алгоритмов.

Определение. Пусть Р/г - гладкая плоская проективная кривая рода д, порожденная абсолют,по неприводимым однородным многочленом F € 1Р9[жъ ж3] степени т, А - подмножество всех¥ч-рациональиых точек Т>Р с зафиксированными значениями однородных координат, п = \А\- Для произвольного ] € [1, — 1)/"1_|] определим АГРС-код С^дО') как образ отображения вычисления

■■ - / ~ (/(/и №), • • •, ПРп)).

п

Доказывается, что АГРС-код Cf,aU) имеет длину п, размерность k{j) = H(j), минимальное кодовое расстояние d(j) > п — mj.

Вторая глава посвящена построению алгоритмов декодирования произвольного АГРС-кода. В пункте 2.1 рассматриваются центральные в современной теории кодирования задачи декодирования по максимуму правдоподобия и списочного декодирования. Показывается, что задача декодирования по максимуму правдоподобия может быть сведена к задачам декодирования с ограниченным расстоянием и списочного декодирования. Пусть С - линейный код в метрическом векторном пространстве F" с метрикой Хемминга d(x,y). Для произвольных v 6 и целого R S [l,n] рассмотрим множество

C(R\v) = {се С | d(v,c) < R}.

Задача списочного декодирования заключается в вычислении множества С'л)(г>), задача декодирования с ограниченным расстоянием является практически важным частным случаем задачи списочного декодирования и заключается в вычислении множества C^(v) при R £ [1, [(d— l)/2j], где d -минимальное расстояние кода С. Пункт 2.1 заканчивается аналитическим обзором существующих алгоритмов списочного декодирования РС-кодов и АГ-кодов, рассмотрением возможности их практической реализации.

В пункте 2.2 на основе идей подхода Бсрлекэмпа-Велча к декодированию РС-кодов строится п полностью обосновывается алгоритм UniqDecoding декодирования произвольного АГРС-кода Cp^U) с ограниченным расстоянием до d*(j) — 1 - m\(d*(j) — 1)/2m + g/m], где d*(j) = n — mj -конструктивное расстояние кода Cf,a(])- Центральной частью алгоритма UniqDecoding является вычисление многочлена вида Qa{T) = N + DT, где D £ (F,[Pf])a, N е (F,l7V])e+j, а = \(d"{j) - 1)/2m + g/m], удовлетворяющего условиям

Vi € [1, n], VPj e A : JV(Pi) + ViD(PÙ = 0, (1)

и последующее нахождение его T-корня из {^ч[Рр\)]- В этом же пункте вычисляются асимптотические оценки временной и емкостной сложности

построенного алгоритма в наихудшем случае, равные Тцг,(п,]) + 0(п3), Ацо{п,]) + 0(п2) соответственно, где Тцц(п,Аио{п^) ~ временная и емкостная сложности алгоритма вычисления корня многочлена С?а(Т).

В пункте 2.3 на основе идей подхода Судана к списочному декодированию РС-кодов строится и полностью обосновывается базовый алгоритм ¡^Бесос!»^ списочного декодирования произвольного АГРС-кода основанный па вычислении многочлена вида <3а,ь{Т) = -^Г5, где для всех в € [0,6]: Д, 6 (Р9[^])а+((,_ф-, с последующим вычислением множества всех Г-корней С}а,ъ{Т) из В процессе обоснования алгоритма доказывается, что если параметры алгоритма а, Ь и целое число Я 6 [1, эт.] удовлетворяют системе неравенств

то алгоритм ListDecoding для произвольного v £ F™ вычисляет все элементы множества >), при этом < Ъ. После обоснования корректности алгоритма вычисляются асимптотические оценки временной и емкостной сложности построенного алгоритма в наихудшем случае, равные T(a,b,j) + 0(bn3), A(a,b,j) + 0(bn2) соответственно, где T(a,b,j), A(a,b,j) - временная Ii емкостная сложности алгоритма вычисления всех корней многочлена Qa,b(T). В конце пункта 2.3 рассматриваются вопросы выбора значений параметров a, b, R алгоритма и оценивается верхняя граница pmax(A), А = mj/n ~ k(j)/n, максимального значения отношения R/n в зависимости от параметров кода Cf,a{Ú)- В частности, доказывается, что Ртах (А) > Pi(A), где pi(A) - максимальное значение отношения R/n при 6=1, только в случае А < 0,3(3).

В пункте 2.4 на основе идей подхода Гурусвами-Судана к модификации алгоритма Судана списочного декодирования PC-кодов строится и полностью обосновывается модифицированный алгоритм MListDecoding списочного декодирования произвольного АГРС-кода В начале

пункта вводится критерий того, что пара (Р, v) € А х F, является нулем кратности не менее г(> 0) заданного многочлена Qa,b{T) — Y1s=qDsTs,

п — R > m(a + bj),

Ув € [0,6]: Бц е по отношению к некоторой проективной

прямой Ь € ¥ч\Рр], показывается, что в каждой градунровочной компоненте кольца существует базис специального вида, удобный для вычисления кратности, и доказывается следующая

Теорема.!. Для произвольного г^елого ] € [1, зафиксируем АГРС-

код Ср,л(]) длины п, размерности к(]), с конструктивным расстоянием <1*{]) = п — т,}. Если существуют целые числа г £ К, а £ |о, г^ ,

Ь 6 К, Л £ [1,п], удовлетворяющие неравенствам

то для любого вектора V = (у1,...,ьп) £ справедливы утверждения:

({) в кольце многочленов ^[Т^р1] одной переменной Т существует такой ненулевой многочлен

(Ь) для всех г £ [1 ,п] элемент (Р;,^) является нулем Яа,ъ{Т) кратности не менее г по отношению к некоторой прямой Ц;

(и) многочлен может быть найден за время 0(6п3г5);

(Ш) любой элемент множества

является Т-корнем многочлена Яа,ь{Т): \/(7 £ : (¡а,ь{0) = 0.

На основании теоремы 1 выписывается алгоритм списочного декодирования, получающий на вход вектор V, значения параметров а, Ь, II, г, и вычисляющий множество Далее определяются асимптотические оценки временной и емкостной сложности алгоритма МГ^ОесосШ^ в наихудшем

ЯаАТ) = А) + £>1Т + £2т2 + ... + ОьТъ,

что

(а) VI е [0, Ц : Д е (Р,рЪ])в+(6_<и> А ф 0,

= {с е 1 <г(е^(С),«) < я}

случае, равные Т(а, b,j)+0{bn3rb), А{а, b,j)+0(bn2r3) соответственно, где T(a,b,j), A(a,b,j) - временная и емкостная сложности алгоритма вычисления всех корней многочлена Qa,b{T). Завершается пункт рассмотрением вопроса оптимального выбора значений параметров а, Ъ, R, г алгоритма и оценивается верхняя граница Ртах(А), А = mj/n « k(j)/n, максимального значения отношения R/n в зависимости от параметров кода Cf,aÜ) 11 фиксированного значения tq параметра г. В частности, доказывается, что

Vr0 е N, VA е (0,1) : 1/2 - А/2 < р<^(А) < 1 - VX

0,8-

0,6-

0,2-

\

\

S!

0,2

0,4

0,6

0,8

Рисунок 1. Зависимость />1,1 (Л), PmL(A), PmL(A), Pmai(A), Ртах (А) ОТ А

,(2)

„(Ю) С

На рис. 1 для наглядности представлены графики функций Р1д(А), Рт1х(А), ртах (А), Ртах (А), соответствующих случаям декодирования с ограниченным расстоянием, списочного декодирования с помощью алгоритма 1лз1Бссос1и^, списочного декодирования с помощью алгоритма М1л810ссос1п^ с кратно-стями г ~ 2 и г — 10 соответственно, а также график функции ртах(А) = 1 — \/~Х. Из их сравнения можно сделать вывод о том, что алгоритм М1лз1Ве-со<1и^ по сравнению с алгоритмом Ь^ОесосШ^ потенциально позволяет

вычислять список мощности 2 и выше для АГРС-кодов, параметры которых удовлетворяют условию k(j)/n « А > 0,3(3).

Несмотря на то, что алгоритм UniqDecoding является частным случаем алгоритма ListDeeoding, который, в свою очередь, является частным случаем алгоритма MListDecoding, каждый нз алгоритмов имеет самостоятельное практическое значение. Так, алгоритм UniqDecoding решает классическую задачу декодирования с ограниченным расстоянием, а алгоритм ListDeeoding значительно проще алгоритма MListDecoding за счет отсутствия требований к кратности нулей вида (Р, v), что исключает рассмотрение в нем дополнительных математических объектов и во многом упрощает структуру системы уравнений, возникающей при вычислении Qa,b{T).

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

В пункте 3.1 рассматривается задача вычисления корпя многочлена Qa(T) = N + DT € ¥q[Pp], возникающая в алгоритме UniqDecoding, п на основе метода неопределенных коэффициентов строится алгоритм FindRootUD. Основная идея алгоритма заключается в том, что произвольный элемент G пространства (Fч\Рр\)з может быть записан в виде G = Е^о' Gjj\ где ф[Л, ..., ф®и) - базис (F,^]),-, Vs е [1 ,H(j)] ■ Gs 6 F,. Тогда система равенств (1) может быть рассмотрена как неоднородная система линейных уравнений относительно неизвестных коэффициентов Gs элемента G. Решая эту систему, например, методом Гаусса, можно либо вычислить коэффициенты искомого корня G, либо выявить отсутствие корня многочлена Qa{T) в пространстве (F9[7V])j. Асимптотические оценки временной н емкостной сложностей алгоритма FindRootUD равны 0(k(j)n2) и 0(d*(j)k(j)n) соответственно, итоговые асимптотические оценки времен-нон и емкостной сложностей алгоритма UniqDecoding с использованием алгоритма FindRootUD равны 0(п3) и 0(п2).

В пункте 3.2 рассматривается задача вычисления множества всех корней многочлена Qa,b(T) = DSTS 6 ¥д[Рр], возникающего в алгорпт-

мах ListDecoding, МЬ^БеоосШ^, и, на основе идеи проекционного подхода Гао-Шокройахи, строится алгоритм Рт(Ш.оо1йЬВ. Центральным шагом алгоритма Рш(Щоо18ЬВ является построение такого гомоморфизма Рг кольца и некоторого расширения поля что сужение Рг на гра-дуировочную компоненту является мономорфизмом. После этого задачу вычисления всех корней многочлена (¿ар(Т) можно свести к задаче вычисления всех корней многочлена Рг(С}а<ъ(Т)) =Г Рг(П3)Т" в иоле с последующим восстановлением их прообразов относительно Рг. В пункте доказывается, что в качестве гомоморфизма Рг можно взять гомоморфизм вычисления значения элементов в К^-рациональной точке Р степени е кривой 7-У с фиксированными однородными координатами при условии, что величина е удовлетворяет неравенству е > тах{т_/, та}. Кроме того отмечено, что если величина е удовлетворяет неравенству

де-2дде'2> £ + 2дд^),

г|е,г<е

то на кривой 'Рр существует не менее е Ед«-рацноналы1ых точек степени е. Алгоритм FindRootsLD заключается в вычислении многочлена Рг{Яа,ь{Т)) £ нахождении всех его корней в поле ¥Ч' с помощью

какого-либо известного метода и для каждого найденного корня ¡3 вычислении решения уравнения Рг((?) = /?, рассматриваемого как системы из е линейных уравнений относительно неизвестных коэффициентов разложения (2 по базису (^['Рг]);. В конце пункта вычисляются асимптотические оценки временной н емкостной сложностей алгоритма РтсШх^йЬВ, равные 7>(Ь, е, д) + 0{Ье{е + (а + Ь^')2)) и Ар(Ь, е,д) + 0(Ье(а + Ь^2 + тпЦЬ + е)), где Тр(Ь,е,д), Ар(Ь,е,д) - временная и емкостная сложности алгоритма вычисления всех корней многочлена степени Ь из Кроме того, вы-

числяются итоговые асимптотические оценки алгоритмов иш<[Песо<1н^, Ь^Оесоёп^, МГ^ВесосНпЁ при условии использования в них на шаге факторизации алгоритма РпкЖо^яЬО, равные, соответственно, 0(п3), 0(п2), Тр(Ь, е, д) + 0(Ьп3), АР{Ь, е, д) + 0{Ьп2), Тр(Ь, е, д) + 0(Ьп3г5), Ар{Ь, е, д) + 0(Ьп2г3).

Четвертая глава посвящена задаче построения алгоритма FindRoots вычисления всех корней полной степени не выше d многочлена одной переменной Q(T) с коэффициентами из кольца многочленов n(> 1) переменных над произвольной областью Ю>.

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

В пункте 4.2 вводится проекционный гомоморфизм

1%: D[n,...Ia:n][ri-»D[a;i)...1®„_i][T])

сопоставляющий произвольному многочлену результат подстановки вместо переменной хп пулевого элемента области D, и для произвольного ненулевого многочлена Q{T) € D[xi,..., хп][Г] и его корня / в В[жх,..., х„] степени не выше d определяются вспомогательные последовательности многочло-нов {Qi(T)}f=0, {МДТ)}^0 и Ш?=0 из колец В[хь..., zjT], В[ж],..., £n_i][Т] и B[a;i,..., соответственно, вычисляемые рекурсивно следующим образом: /0 = /, Q0(T) = Q{q\t) = Q^{T), М0(Т) = i>l{Qo{T)), Vi € [l,d]

П = (/¿-i - №<-i))/®n.

Qi(T) = Q\%(xnT + фтп{Ь-г)), Mi(T) = ФМХ](Т)),

где Q^(T) = Qi(T)/x\J, r* - такое неотрицательное целое число, что делит Qi{T), но не делит Qi(T). Далее исследуются различные свойства этих последовательностей многочленов, с помощью которых доказываются следующие важные утверждения:

!)/ = £?=„«(/<)■

2) Если (Т — /) делит Q(T), то для всех целых i € [0,rf] многочлен (Т — iplifi)) делит многочлен Mi.

3) (Г — /) делит Q{T) тогда и только тогда, когда Т делит Qd+i{T) =f

В конце пункта 4.2 описывается идея рекурсивного алгоритма РшсШойв, заключающаяся в следующем. Если для каждого г 6 [0,с£] выполнить сл(?-дующие действия: вычислить множество — г) всех корней степсу

ни не выше ^ — г многочлена М^Т) е В[жь ... ,жп_1][Т] и для каждого элемента множества — г), являющегося кандидатом на состав-

ляющую некоторого корня / многочлена Т), вычислить много-

член Л^+х(Т), то, при i = (I, мы получим множество последовательностей вида {'ФпИг)}^ и соответствующих им последовательностей {(¡^Т)}'}=0, {М;}^=0. Те последовательности {0,ТШ}?=о> Для которых Т делит (¿М(Т), согласно утверждению 3 соответствуют корням исходного многочлена С} (Г) и по ним можно восстановить искомые корни в соответствии с утверждением 1.

В пункте 4.3 на основе результатов из пункта 4.2 строится рекурсивный алгоритм Ршс111оо18 вычисления всех корней стенепн не выше ё, многочлена <2(Т). Особенностью алгоритма является наличие двойной рекурсии -по количеству переменных в коэффициентах текущего многочлена л по номеру вычисляемого многочлена в текущей вспомогательной последовательности многочленов. В конце пункта 4.3 обосновывается корректность алгоритма и доказывается, что алгоритм закончит свою работу за конечное число шагов. Отметим, что при п = 1 и О = алгоритм РтсШх^й на уровне идеи совпадает с алгоритмом Рота-Рукенштейн.

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

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

0(bd'\F(b) + {s + М2)2" + bV'-Hs + bd2)"))

арифметических операций в области D, где b - максимальная степень переменной Т в многочлене Q(T), s - максимальная полная степень коэффициентов Q(T), F(b) - временная сложность алгоритма вычисления всех корней многочлена из кольца В[Т] степени Ь. Отметим, что в случае D = F? оценка временной сложности алгоритма FindRoots может быть упрощена:

0{b<fl(F(b) + (а + bd2)2n + b2(s + М2)^"1'Iog*3+1)).

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

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

Публикации автора по теме диссертации

Статьи в ведущих рецензируемых научных журналах и изданиях, включенных в перечень ВАК РФ

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

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

3. Маевский А.Э. Пслеиицын A.M. Реализация программного алгебро-геомптрического кодека с применением алгоритма Сакаты. // Известия Южного федерального университета. Технические науки. Тематический выпуск "Информационная безопасность", 2008. №8(85). С. 196198.

Другие публикации

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

5. Маевский Л.Э. Аналог алгоритма Гурусвамп-Судана для списочного декодирования специального класса алгебро-геометрических кодов. // Материалы XI Международной научно-практической конференции "Информационная безопасность". В 3 ч. 4.1. Таганрог: Издательство ТТИ ЮФУ, 2010. С. 226-231.

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

7. Маевский А.Э. О распространении алгоритма Берлекэмпа-Велча на один класс алгебро-геометрических кодов на проективных кривых. // Тезисы докладов международной алгебраической конференции, посвященной 100-летию со дня рождения Д.К.Фаддеева. СПб., 2007. С. 52-54.

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

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

10. Маевский А.Э. Разработка п исследование помехоустойчивых свойств алгебро-геометрического списочного кодека // Теория и практика создания радиотехнических и мехатронных систем (теория, проектирование, экономика): Материалы межрегиональной научно-практической конференции, ФГУП "ВНИИ "Градиент". Ростов-на-Дону, 2007. С. 1213.

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

Печать цифровая. Бумага офсетная. Гарнитура «Тайме». Формат 60x84/16. Объем 1,0 уч.-изд.-л. Подписано в печать 11.01.2011 г. Заказ № 2047. Тираж 100 экз. Отпечатано в КМЦ «КОПЯЦЕНТР» 344006, г. Ростов-на-Дону, ул. Суворова, 19, тел. 247-34-88

Введение

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. 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.