Содержание к диссертации
Введение
1 Предварительные сведения 13
1.1 Линейные коды 13
1.2 Многочлены нескольких переменных 16
1.3 Аффинное и проективное пространства 20
1.4 Плоские проективные кривые 22
1.5 Однородное координатное кольцо 27
1.6 Кратность пересечения проективных кривых 30
1.7 Алгебро-геометрические коды типа кодов Рида-Соломона 33
1.8 Модель вычислений 40
2 Алгоритмы декодирования АГРС-кодов 41
2.1 Задачи декодирования линейных кодов 41
2.2 Алгоритм декодирования с ограниченным расстоянием 44
2.3 Базовый алгоритм списочного декодирования 55
2.4 Модифицированный алгоритм списочного декодирования 68
2.5 Заключение к главе 93
3 Алгоритмы вычисления Т-корней многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой 94
3.1 Алгоритм вычисления Т-корня линейного многочлена 94
3.2 Алгоритм вычисления Т-корней многочлена произвольной степени 97
3.3 Заключение к главе 106
4 Алгоритм вычисления Т-корней многочленов одной переменной с коэффициентами из кольца многочленов нескольких переменных над произвольной областью целостности 108
4.1 Постановка задачи 108
4.2 Специальные многочлены и некоторые свойства Т-корней 110
4.3 Алгоритм вычисления множества всех Т-корней 115
4.4 Анализ сложности алгоритма вычисления Т-корней 121
4.5 Заключение к главе 130
Заключение 131
Литература
- Аффинное и проективное пространства
- Алгоритм декодирования с ограниченным расстоянием
- Алгоритм вычисления Т-корней многочлена произвольной степени
- Алгоритм вычисления множества всех Т-корней
Введение к работе
Актуальность темы
Широко известно, что при передаче информации как по пространственным, так и по временным каналам связи могут возникать ошибки. В конце 40-х годов прошлого века К. Шеннон показал, что для защиты передаваемых данных от случайных искажений и помех экономически эффективнее применять помехоустойчивые коды, чем строить дорогостоящие каналы высокого качества. С тех пор активное развитие получила теория помехоустойчивого кодирования, в процессе которого найдены различные классы помехоустойчивых кодов и определены границы их применимости. Из всего многообразия линейных кодов широкое практическое применение нашли коды Рида-Соломона (PC-коды); традиционно PC-коды используются, например, для защиты данных на носителях информации1, в системах спутниковой связи2, в системах исследования дальнего космоса3.
В 1997 г. М.Судан4 построил первый полиномиальный алгоритм, решающий задачу списочного декодирования PC-кодов, сформулированную для произвольных кодов Элайесом5 и Возенкрафтом6 еще в середине 1950-х годов. Алгоритм Судана оказался эффективным только для PC-кодов, имеющих скорость до 1/3, поэтому несколько позже Гурусвами и Судан7 модифицировали алгоритм Судана, сняв ограничение на скорость РС-кодов. Благодаря алгоритмам Судана и Гурусвами-Судана PC-коды нашли применение при решении многих прикладных задач, изначально далеких от
1Immink K.A.S. Coding techniques for digital recoders. N.-Y.: Prentice-Hall, 1991.
2 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.
3McEliece 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.
4Sudan 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 channel. Technical Report no. 335, Research Laboratory of Electronics, MIT, 1957.
6 Wozencraft J.M. List decoding. // Quaterly Progress Report, Research Laboratory of Electronics, MIT,
1958. Vol. 48. P. 90-95.
7 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.
теории кодирования, таких как предотвращение несанкционированного копирования компакт-дисков8 9, самообучение систем и распознавание образов10, построение односторонних функций для криптографических целей11, криптоанализ некоторых блочных шифров12. Отметим, что с каждым годом круг прикладных задач, решаемых с помощью списочного декодирования, интенсивно расширяется, вследствие чего возрастает и актуальность задачи улучшения характеристик существующих и построения новых алгоритмов списочного декодирования как PC-кодов, так и других помехоустойчивых кодов.
В 1981 г. В.Д.Гоппа, используя методы алгебраической геометрии, описал новый широкий класс помехоустойчивых кодов - алгебро-геометричес-кие коды13 (АГ-коды). Его работа завершила многолетние исследования в области построения наиболее общего класса кодов, включающего в себя классы PC-кодов, циклических кодов и некоторых других используемых на практике кодов. Для построения АГ-кодов он предложил использовать пространства рациональных дифференциальных 1-форм на гладких проективных кривых, такой способ построения позже получил название Q-конструкции. Несколько позже В.Д.Гоппа описал другой способ построения АГ-кодов14, основанный на использовании пространств Римана-Роха на гладкой проективной кривой, получивший название L-конструкции. Впоследствии были обнаружены другие конструкции АГ-кодов с привлечением более сложных объектов алгебраической геометрии. М.А.Цфасман,
8Silverberg A., Staddon J., Walker 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 G.A. Class of i.p.p codes with effective tracing algorithm // Journal of Complexity, 2004. Vol. 20, No 2-3, P.137-147.
10Ar S., 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.
^Sudan 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 in Cryptography - Crypto'98 (Editor Krawczyk H.). Lecture Notes in Computer Sciences No.1462, N.-Y.:Springer, 1998.
13Гоппа В.Д. Коды на алгебраических кривых. // Доклады АН СССР. 1981. Т. 259. № 6. С. 1289-1290.
14Гоппа В.Д. Алгебраико-геометрические коды. // Известия АН СССР, Серия математическая. 1982. Т. 46. №4. С. 762-781.
С.Г.Влэдуц и Т.Цинк показали , что существуют АГ-коды, построенные с помощью весьма специальных кривых, значение минимального расстояния которых гарантированно превышает нижнюю границу Варшамова-Гилберта, существенно продвинувшись, таким образом, к решению одной из центральных в теории кодирования задач построения семейства кодов с асимптотически хорошими параметрами (кодов, у которых при стремлении параметров п, к, d к бесконечности отношения к/п и d/n одновременно отличны от нуля). Отметим, что практически все известные семейства кодов, отличные от алгебро-геометрических, либо асимптотически плохи, либо имеют параметры, лежащие на границе Гилберта-Варшамова, поэтому класс АГ-кодов представляет не только теоретический интерес, но и важен для практических приложений16. В связи с этим Шокройахи и Вассерман17, используя идеи алгоритма Судана, построили алгоритм списочного декодирования некоторых подклассов АГ-кодов, эффективный только для кодов с низкими скоростями, а Гурусвами и Судан18 его модифицировали, сняв ограничение на скорость кода. Однако высокая сложность математического аппарата и объектов теории алгебраических кривых, используемых при построении АГ-кодов и алгоритмов декодирования, затрудняет их применение к решению теоретических или практических задач.
В 1988 г. Юстесен и др.19 упростили L-конструкцию Гоппы, используя вместо пространства Гимана-Гоха пространство всех однородных многочленов фиксированной полной степени из однородного координатного кольца гладкой плоской проективной кривой, построив при этом новый подкласс АГ-кодов, содержащий, в частности, ГС-коды. Этот подкласс АГ-
15Tsfasman М.А., Vladuj S.G., Zink Т. Modular curves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound // Mathematical Nachrichten, 1982. Vol. 109. P. 21-28.
16Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. М.: МЦНМО, 2003. 504 с. С.88
17Shokrollahi М., Wasserman Н. List decoding of algebraic-geometric codes. // IEEE Transactions on Information Theory, 1999. Vol. 45. P. 432-437.
18 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.
19 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.
кодов будем далее называть алгебро-геометрическими кодами типа кодов Рида-Соломона (АГРС-кодами). Благодаря тому, что АГРС-коды по своей конструкции гораздо ближе к PC-кодам, чем другие АГ-коды, в той же статье авторы на основе классического алгоритма Питерсона декодирования кодов Боуза-Чоудхури-Хоквингема построили без использования дополнительных математических конструкций алгебраической геометрии практически реализуемый полиномиальный алгоритм декодирования кодов, двойственных АГРС-кодам. Отметим, что существующие алгоритмы декодирования PC-кодов и АГ-кодов непосредственно не могут быть перенесены на класс АГРС-кодов в силу различия базовых математических объектов.
В силу своей конструкции АГРС-коды, как и АГ-коды, обладают следующими характеристиками:
максимальная длина АГРС-кода над полем q ограничена сверху достижимым числом Ni = q+l + 2g\_y/q\: определяемому максимальным количеством F^-рациональных точек на кривой рода д: в то время как максимальная длина PC-кода над полем q равна q + 1;
длина п, размерность к и конструктивное расстояние d* АГРС-кода удовлетворяют двойному неравенству:
п — к — g + l
поэтому если отношение д/п мало, параметры АГРС-кода лежат близко к границе Синглтона.
Вследствие этого можно ожидать, что при условии существования практически реализуемых эффективных алгоритмов декодирования АГРС-коды наравне с PC-кодами найдут широкое применение в разнообразных прикладных задачах.
В связи с изложенным значимой и актуальной представляется задача построения алгоритмов списочного декодирования и декодирования с ограниченным расстоянием произвольного АГРС-кода с сохранением при
этом основной направленности конструкции класса АГРС-кодов на минимальное использование математического аппарата теории алгебраических кривых и алгебраической геометрии.
Необходимо отметить, что одним из важных этапов всех алгоритмов списочного декодирования PC-кодов и АГ-кодов, начиная с алгоритма Судана, является вычисление корней многочлена одной переменной с коэффициентами из кольца q[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. II IEEE Transactions on Information Theory, 2000. Vol. 46. P. 246-257.
21 Wu X.-W., Siegel P.H. Efficient root-finding algorithm with application to list decoding of algebraic-
geometric codes. I/ IEEE Transactions on Information Theory, 2001. Vol. 47. No.6. P. 2579-2587.
22 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.
23 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.:
- для PC-кодов и для АГ-кодов. Тем не менее, все построенные алгоритмы в случае АГРС-кодов не применимы в силу специфичности структуры используемого в их конструкции однородного координатного кольца. В связи с этим представляется актуальным дальнейшее развитие теории и практики вычисления корней многочленов с коэффициентами из различных алгебраических структур, в частности, используемых в конструкциях помехоустойчивых кодов. Например, конструкция АГРС-кодов использует однородное координатное кольцо гладкой плоской проективной кривой над конечным полем, конструкция проективных кодов Рида-Маллера24 использует кольцо многочленов нескольких переменных над конечным полем. Такие алгоритмы могут найти применение как в существующих, так и разрабатываемых алгоритмах декодирования.
Цель работы
Цель работы - разработка алгоритмов списочного декодирования и декодирования с ограниченным расстоянием произвольного АГРС-кода, а также разработка новых алгоритмов вычисления корней многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой плоской проективной кривой и кольца многочленов нескольких переменных над произвольной областью целостности.
Основные методы исследования
В работе используются методы и результаты теории помехоустойчивого кодирования, в частности, подходы Берлекэмпа-Велча, Судана, Гурусвами-Судана к построению алгоритмов декодирования; алгоритмической алгебры, в частности, подходы Рота-Рукенштейн, Гао-Шокройахи к построению алгоритмов вычисления корней многочленов; линейной и общей алгебры; алгебраической геометрии и коммутативной алгебры в части, касающейся теории проективных алгебраических кривых над конечными полями; теории сложности алгоритмов.
Springer, 2000. Р. 214-228.
24Duursma 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.
сновные результаты работы
Основные результаты работы, выносимые на защиту состоят в следую-ем:
Построен полиномиальный алгоритм декодирования с ограниченным расстоянием произвольного АГРС-кода, полностью обоснована его корректность, вычислены максимальное количество исправляемых ошибок и асимптотические верхние границы временной и емкостной сложности в наихудшем случае.
Построены базовый и модифицированный полиномиальные алгоритмы списочного декодирования произвольного АГРС-кода. Для каждого алгоритма полностью обоснована корректность, вычислены оценки максимального значения радиуса сферы Хэмминга, внутри которой алгоритм способен вычислить все элементы выходного списка, а также оценки асимптотических верхних границ временной и емкостной сложности в наихудшем случае.
Для многочленов одной переменной с коэффициентами из однородного координатного кольца гладкой проективной кривой построены два алгоритма вычисления всех корней, принадлежащих заданной градуи-ровочной компоненте: в случае многочлена первой степени - на основе метода неопределенных коэффициентов, в случае многочленов произвольной степени - на основе подхода Гао-Шокройахи. Для каждого алгоритма полностью обоснована корректность и вычислены асимптотические верхние границы временной и емкостной сложности в наихудшем случае.
Построен алгоритм вычисления корней многочленов одной переменной с коэффициентами из кольца многочленов нескольких переменных над произвольной областью целостности, полностью обоснована его корректность и вычислена асимптотическая верхняя граница его временной сложности в наихудшем случае.
Научная новизна
Все основные результаты работы являются новыми.
Теоретическая и практическая ценность
Работа носит теоретический характер. Результаты диссертации могут быть использованы специалистами, работающими в области теории и практики помехоустойчивого кодирования, криптографии, теории обучения, теории распознавания образов.
Апробация результатов
Основные результаты диссертации представлены в виде докладов на следующих конференциях: Международная школа-семинар по анализу и геометрии памяти Н.В. Ефимова (п.Абрау-Дюрсо, 2004 и 2006 гг.), Межрегиональная научно-практическая конференция "Теория и практика создания радиотехнических и мехатронных систем (теория, проектирование, экономика)" (Ростов-на-Дону, 2007 г.), Международная алгебраическая конференция, посвященная 100-летию со дня рождения Д.К.Фаддеева (СПб., 2007 г.), Международная научно-практическая конференция "Информационная безопасность" (Таганрог, 2008 и 2010 гг.), а также неоднократно обсуждались на семинаре "Математические методы в защите информации" кафедры алгебры и дискретной математики мехмата ЮФУ (руководитель - к.ф.-м.н., доцент Деундяк В.М.).
Публикации 25
Основные результаты опубликованы в 11 работах [1-11].
В работе [3] автору принадлежит разработка структуры алгебро-геомет-рического кодека, в работе [11] автору принадлежит определение понятия поверхности помехоустойчивости, а также способы выбора параметров алгоритма списочного декодирования для решения задачи декодирования по максимуму правдоподобия.
25Работа поддержана ФЦП "Научные и научно-педагогические кадры инновационной России", Государственный контракт №02.740.11.0208 от 7 июля 2009 г.
Структура и объем диссертации
Аффинное и проективное пространства
Пусть q - произвольное конечное поле, п - натуральное число. Рассмотрим векторное пространство F и для каждого элемента х — (жі,... ,хп) Є F определим его норму w(x) как количество ненулевых координат: ги(а0 = {гє[1,ті] а 0}.
В теории помехоустойчивого кодирования норма w(x) называется весом Хэмминга вектора х. Расстояние между двумя произвольными векторами x = (xi,..., xn), у = (2/i,..., yn) пространства F, определяемое весом Хэм-минга, называется расстоянием Хэмминга и равно количеству координат, в которых х и у различаются: d{x, у) = w{x -у) = \{і Є [1, п) \ х{ ф уг}\. Легко проверяется тот факт, что расстояние Хэмминга является метрикой на пространстве F. Линейным блоковым кодом (далее - просто кодом) над полем F называется любое собственное подпространство С пространства F" Размерность к подпространства С называется размерностью кода С, величина п - длиной кода С, величина d = min lw(x)\ хЄС\{(0,...,0)} - минимальным расстоянием кода С. Будем говорить, что код С над полем q является [п, к, d]q-KoppM, если он имеет длину п, размерность к и минимальное расстояние d. Известно (см., например, [26], стр. 43), что длина, размерность и минимальное расстояние произвольного кода С связаны следующим соотношением:
Лемма 1.1 (верхняя граница Синглтона). Для всякого [n:k,d]q-Koda d n-k + l. Порождающей матрицей [п, /с, d] д-кода С называется любая матрица G размера k х п с элементами из Fg, чье пространство строк совпадает с кодом С. Каждая порождающая матрица G кода С определяет вложение . rG : FJ - F, (аь..., ак) ь- (аь ..., ак) G, образом которого является код С. В теории помехоустойчивого кодирования элементы пространства F обычно называют информационными словами, элементы кода С - кодовыми словами, отображение тс - кодирующим отображением (кодированием).
Для произвольного линейного кода С определим двойственный код С-1, представляющий собой ортогональное дополнение к коду С в пространстве F, вычисленное относительно стандартного скалярного произведения: С1- = {(жі,..., хп) Є FJ V(ci,..., Сп) Є С : хгсі + ... + хпсп = 0}
Ясно, что С-1 является линейным кодом с параметрами п-1 — п, к-1 = п — к, dL п1- — ArL-f-l = ;-f-lH (С-1)-1 = С. Порождающие матрицы G кода С и G-1 двойственного кода С1- связаны соотношением: G (Gx) = О, где t - символ транспонирования, О - нулевая к х (п — к) матрица. Часто матрицу G1- называют проверочной матрицей кода С (соответственно, матрицу G называют проверочной матрицей кода С1-).
Для пары кодов (С, С1-) определим понятие рода ([3], стр. 30). Пусть д - неотрицательное целое число. Будем говорить, что код С является кодом рода не выше д, если выполнены следующие соотношения: k-\- d п-Ь 1 — д, (п - к) + d1- п+1-д. Ясно, что двойственный код С1- также является кодом рода не выше д. Род кода характеризует, насколько параметры кодов С и С1- далеки от границы Синглтона. Код рода не выше 0 называется кодом с максимально достиоюимым расстоянием (МДР-кодом) (см., например, [26], стр. 310).
Одними из широко применяемых в теории и практике помехоустойчивого кодирования кодов являются коды Рида-Соломона. Приведем одно из описаний этих кодов ([3], стр. 60). Зафиксируем поле q и положим п = q — 1, F = q \ {0}. Для произвольного а Є [0,п — 2] рассмотрим множество La всех многочленов одной переменной степени не выше а с коэффициентами из q. Отображение "вычисления" где ai,..., ап - различные элементы F , является линейным и инъектив-ным, его образ называют кодом Рида-Соломона (PC-кодом). Ясно, что dimLa — а 4- 1 и, так как произвольный ненулевой многочлен степени не выше а имеет не более а корней, произвольный ненулевой вектор РС-кода имеет не менее п — а ненулевых координат. Таким образом, PC-код является [п, а + 1,п — а]д-кодом. Легко проверить, что произвольный РС-код является кодом рода нуль.
Вычислим одну из порождающих матриц кода Рида-Соломона. Поскольку строки любой из них являются базисом PC-кода, то, выбрав какой-либо базис кода, легко записать матрицу GRS(O)- Кодирующее отображение инъ-ективно, следовательно, базис пространства La оно переводит в базис РС-кода. Следовательно, зафиксировав в La, например, базис {і, х,.т2,..., ха} получим, что /і 1 ... 1 \ п а GRS(a) = п а а: s/ \ \ 2 Далее удобно будет использовать следующую терминологию. Множество всех кодов Рида-Соломона над заданным полем q будем называть семейством PC-кодов, определенным над полем q, а множество всех возможных семейств PC-кодов будем называть классом РС-кодов.
Алгоритм декодирования с ограниченным расстоянием
Пусть С - произвольный линейный [п, к, d]q-KOR. Рассмотрим следующие задачи, играющие центральную роль в теории помехоустойчивого кодиро-вания ([3], [26], [27], [44]): - задача декодирования по максимуму правдоподобия: для произвольно заданного вектора v Є F найти ближайший к нему относительно расстояния Хэмминга вектор с Є С; - задача списочного декодирования: для произвольно заданного вектора v Є F и целого числа R Є [1,п] найти такое наибольшее подмножество C(R\v) С С, что расстояние Хэмминга от v до любого элемента из C R\v) не превышает R. На данный момент далеко не для всех линейных кодов известны вычислительно эффективные (например, работающие за полиномиальное относительно п и q время) и практически реализуемые алгоритмы решения обеих задач. В связи с этим вместо задачи декодирования по максимуму правдоподобия чаще всего рассматривают задачу списочного декодирования в случае, когда R \_{d—l)/2\. Так как наименьшее расстояние между любыми двумя различными элементами кода С не менее d, то множество C(L(d_1)/2J)(i;) содержит не более одного элемента. В этом случае говорят о задаче декодирования с ограниченным расстоянием до t = [(d — 1)/2J (или об исправлении t ошибок): если множество C \v) не пусто, то исправлено t ошибок в векторе v, в противном случае ошибки исправить нельзя (неполное декодирование).
Для класса кодов Рида-Соломона в настоящий момент существует несколько эффективных методов декодирования с ограниченным расстоянием до \_{d— 1)/2J, одним которых является широко используемый на практике алгоритм Питерсона-Горенстейна-Цирлера ([2]). Первоначально он имел временную сложность 0(п3) операций в поле Fg, затем был ускорен до 0{п2) операций за счет замены нескольких шагов алгоритмом Берлекэмпа-Месси. Схожесть (в некотором смысле) конструкций PC-кодов и АГРС-кодов позволила Й.Юстесену и др. в работе [52] построить аналог алгоритма Питерсона, решающий задачу декодирования кодов, двойственных АГРС-кодам, с ограниченным расстоянием до \_d /2 — ra2/4J, где т - степень порождающей АГРС-код кривой, за 0(пл) операций в поле q. В последующих работах [53], [60] алгоритм декодирования Юстесена улучшен и позволяет исправить до \d /2 — т2/8 + т/А — 9/8J (соответственно, до [d /2\) ошибок за 0(п7/3) операций в поле д. Отметим, что для АГ-кодов также существует ряд работ (см., например, [64], [68]), в которых построены аналоги алгоритма Питерсона. Тем не менее, для работы практически всех разработанных алгоритмов декодирования АГ-кодов требуется эффективный метод вычисления базиса в пространстве Римана-Роха, ассоциированного, в общем случае, с произвольно заданным дивизором.
Сравнительно недавно для декодирования кодов Рида-Соломона с ограниченным расстоянием до _( —1)/2J появился алгоритм Берлекэмпа-Велча ([69], 1989 г.), имеющий временную сложность 0(пг) операций в поле Fq. С одной стороны, он представляет практический интерес в силу простоты реализации, а с другой стороны, стал основой для построения алгоритмов списочного декодирования PC-кодов. Задача списочного декодирования линейных кодов впервые была поставлена Элайесом [39] и Возенкраф-том [70] еще в середине 1950-х годов, но первый практически приемлемый алгоритм появился в только 1989 г. для некоторых семейств кодов Ада-мара ([42]). В 1997 г. в работе [65] М.Судан, основываясь на алгоритме Берлекэмпа-Велча, а также некоторых своих более ранних работах, построил первый алгоритм списочного декодирования кодов Рида-Соломона, работающий за полиномиальное время. Алгоритм Судана, несмотря на то, что является эффективным только при малых отношениях к/п, стал базой для дальнейшего развития алгоритмов списочного декодирования. В работе [62] Шокройахи и Вассерман перенесли алгоритм Судана на АГ-коды, построенные с помощью L-конструкции, а Гурусвами и Судан в работе [62] сняли ограничение на малые отношения к/п, модифицировав алгоритмы списочного декодирования как PC-кодов, так и АГ-кодов. Все алгоритмы списочного декодирования PC- и АГ-кодов, начиная с алгоритма Судана, состоят из двух шагов: шага интерполяции и шага факторизации. Шаг интерполяции сводится, в конечном счете, к решению однородной системы линейных уравнений и может быть реализован, например, с помощью метода исключения Гаусса. Основной вычислительной проблемой этого шага в алгоритмах Шокройяхи-Вассермана и Гурусвами-Судана для АГ-кодов является то, что при построении системы уравнений необходимо за полиномиальное время уметь вычислять базис в пространствах Римана-Роха, ассоциированными с различными дивизорами. Алгоритмы такого типа существуют (см., например, [47]), но остается открытым вопрос их эффективной практической реализации. Шаг факторизации заключается в нахождении корней многочлена одной переменной с коэффициентами из кольца многочленов одной переменной (для PC-кодов) или из поля функций на проективной кривой (для АГ-кодов). Имеется несколько работ, посвященных построению требуемых алгоритмов факторизации, наиболее интересными из них являются [59] для РС-кодов, [41], [71] для АГ-кодов. Следует отметить, что все алгоритмы факторизации многочленов с коэффициентами из функциональных полей также нуждаются в эффективных методах построения базиса в пространствах Римана-Роха. Таким образом, как для класса кодов Рида-Соломона, так и для класса алгебро-геометрических кодов, существуют алгоритмы списочного декодирования, причем если для PC-кодов эти алгоритмы вычислительно эффективны (полиномиальны) и сравнительно легко реализуемы практически (программным или аппаратным способом, см., например, [43]), то для АГ-кодов их практическая реализация, видимо, затруднена (необходимо решить вопрос экономного представления элементов функциональных полей, способов вычислений с ними, реализации алгоритмов вычисления базиса и факторизации и т.п.). Кроме того, специалистам в области связи, разрабатывающим помехоустойчивые системы передачи информации, по-видимому, затруднительно понять все тонкости техники алгебраической геометрии, применяемой для списочного декодирования АГ-кодов, и, как следствие, оценить преимущества тех или иных кодов и методов их декодирования.
В настоящей главе для класса АГРС-кодов на основе идей метода Берле-кэмпа-Велча декодирования PC-кодов строится алгоритм декодирования с ограниченным расстоянием до \_(d — 1)/2J — д — т (пункт 2.2), а также аналоги алгоритмов списочного декодирования PC-кодов Судана (пункт 2.3) и Гурусвами-Судана (пункт 2.4). При построении этих алгоритмов особое внимание уделяется сохранению основной направленности авторов конструкции класса АГРС-кодов - сведение к минимуму количества используемых объектов и методов алгебраической геометрии, поэтому разрабатываемые алгоритмы можно рассматривать как обобщение способов декодирования PC-кодов, а не как сужение способов декодирования АГ-кодов на класс АГРС-кодов. Поскольку представленные методы списочного декодирования по-прежнему содержат шаг факторизации, то в главе 3 строятся эффективные алгоритмы, которые могут быть использованы для его реализации.
Алгоритм вычисления Т-корней многочлена произвольной степени
Зафиксируем АГРС-код CF,A{J), имеющий длину п, размерность k(j), конструктивное расстояние d (j). В алгоритме UniqDecodmg (см. п.2.2) декодирования кода CF,AU) С ограниченным расстоянием для произвольно заданного вектора v — (г і,..., vn) из F на основе значений параметров кода вычисляется значение величины а, фиксируются базисы ф , ..., Фп(а\ и Фі\ ..., Фщсї+j) ГРаДУиРовочных КОМПОНеит (q[PF])a, (q[pF])a+j КОЛЬ ца FJ7-V] соответственно и на шаге интерполяции вычисляется многочлен Q{T) = N + DT, где N Є (F?pV])«+,-, D Є {Fq[PF])a, удовлетворяющий условиям пункта (і) теоремы 2.2. На шаге факторизации требуется определить, существует ли такой элемент G из градуировочной компоненты кольца (№q[VF])j кольца F9[7V, что выражение Q(G) = N + DG (3.1) тождественно равно нулю в FJ7V]. Отметим, что если такой элемент G существует, то он единственен, поскольку кольцо FgfTV] является областью целостности и элемент D отличен от нуля. Для определения существования и вычисления многочлена G воспользуемся следующим общематематическим методом неопределенных коэффициентов. Пусть фі , ..., Ф ІАЛ -базис градуировочной компоненты ($q\pF\)j-Выражение (3.1) запишем в виде Ma+j) \ /П(а) \ /H(j) \ Q(G)= I Е N +A + 11 # 1Х И = Ma+j) \ Ma)H(j) \ = Е a+i) + ЕЕАА# у г=1 у ys=l u=l у где через Nr, Z)s, Gu обозначены коэффициенты разложения элементов N, D, G градуировочных компонент (q[pF])a+j, №q[PF])ai O gP Di по соответствующим базисам. Для всех s Є [l,7 (a)], и Є [1,7 ( )] зафиксируем разложение ПрОИЗВедеНИЯ фі фи ПО баЗИСу КОМПОНеНТЫ (Fq[VF])a+j: которую удобно интерпретировать как неоднородную систему линейных уравнений относительно неизвестных коэффициентов 6?і, ..., G n(jy Ясно, что в случае разрешимости системы (3.4) любое решение будет удовлетворять тождеству Q(G) = О, а в случае отсутствия решений ни один элемент компоненты (FJTVDj не будет удовлетворять тождеству Q(G) = 0. Следовательно, разрешимость системы (3.4) определяет наличие или отсутствие Т-корня многочлена Q(T), а единственность Т-корня в случае его существования гарантирует единственность решения системы (3.4).
На основе приведенных рассуждений выпишем алгоритм вычисления Т-корня многочлена Q(T), найденного на шаге интерполяции алгоритма UniqDecoding.
Алгоритм FindRootUD (вычисление Т-корня линейного многочлена Q(T))\ Вход: Неотрицательное целое число а, элементы N = Y2r=i Nr4 r3 Є №q[PF])a+j, D = ЕЇЇі} Djsa) Є (Fq[VF])a \ {0}. Выход: Если существует такой элемент G Є ( q[PF-])j, что N 4- DG — 0, то будет возвращен G, в противном случае будет возвращено сообщение об отсутствии Т-корня. 1. (Подготовительный шаг). Для всех s Є [1,7ї(а)], и Є [l,7i(j)] вычислить коэффициенты J , ..., С (а+7) разложения произведения фз Фи по базису компоненты (q[PF])a+j; 2. Вычислить матрицу М = (mrjU) размера Н(а + j) х 7i(j), где П(а) 8=1 3. Решить неоднородную систему уравнений М (Gb ..., Сад) = (-ЛГЬ ..., -Nn{a+j)Y. Если решений нет, вернуть сообщение об отсутствии Т-корня, в противном случае вернуть элемент n(j) u=l Конец алгоритма.
Замечание. Подготовительный шаг алгоритма не зависит от коэффициентов N, .D, поэтому при многократном применении алгоритма для одних и тех же градуировочных компонент и их базисов с целью уменьшения вычислительной сложности его можно выполнить только один раз.
Оценим временную и емкостную сложности алгоритма FindRootUD в соответствии с зафиксированной в главе 1 моделью вычислений. Так как шаг 1 может быть выполнен только один раз при выборе параметров АГРС-кода, то его временную сложность учитывать не будем. Для хранения всех коэффициентов, вычисляемых на шаге 1, необходимо 7i{a) H(j) П.{а + j) ячеек памяти. Поскольку а т — 2 (см. доказательство п.(іі) теоремы 2.2), то П(а) = (d (j) + 1)/2, П(а + j) = п - (d Q) - 1)/2, H{j) = к(3) и
Шаг 2 имеет временную сложность 0(d (j)k(j)n) и требует дополнительно 0(k(j)n) ячеек памяти. Шаг 3, выполняемый с помощью метода Гаусса, имеет временную сложность 0(k(j)2n). Следовательно, общая оценка временной сложности алгоритма в наихудшем случае есть 0(k(j)n(k(j) + d (j))) С 0(k(j)n2), общая оценка емкостной сложности есть 0{d {j)k{j)n). Общая оценка временной сложности алгоритма UniqDecoding с применением алгоритма FindRootUD составляет 0(п3), общая оценка емкостной сложности составляет 0(n(d (j)k(j) +п)).
Как и в предыдущем пункте, зафиксируем АГРС-код CF,A{J)- имеющий длину п, размерность k(j), конструктивное расстояние d {j). В алгоритмах , ListDecoding и MListDecoding (см. пп.2.3, 2.4) списочного декодирования кода Ср,л(з) Для произвольно заданного вектора v = (г і,..., vn) из F и целых чисел а, 6, R, выбранных на основе значений параметров кода и удо 98 влетворяющих системе неравенств (2.9) или (2.36), для всех і Є [0,6] фик сируется баЗИС 01 , ГраДуирОВОЧНОЙ КОМПОНеНТЫ (q[pF])a+ij и на шаге интерполяции вычисляется многочлен Q(T) = ZS=QDSTS, где Ds Є (Fq[PF])a+(b-s)j, удовлетворяющий условиям пункта (і) теоремы 2.3 или 2.8) соответственно. На шаге факторизации требуется вычислить множество всех таких элементов G граду ировочной компоненты {q[pF])j, ЧТО выражение Q{G) = D0 + DXG + T 2G2 4-... + DbGb (3.5) тождественно равно нулю в кольце q[pF\ Подход, использованный в предыдущем пункте для нахождения Т-корня линейного многочлена, в случае многочлена Q{T) произвольной степени не представляется вычислительно эффективным, поскольку возникающая при этом неоднородная система уравнений относительно коэффициентов элемента G является нелинейной. Для решения задачи воспользуемся общей идеей проекционного метода, предложенного в статье [41] для нахождения Т-корней многочлена одной переменной Т с коэффициентами из поля функций q(X) на некоторой кривой X. Она заключается в построении такого гомоморфизма поля q{X) и некоторого расширения Fge поля q, что подмножество q(X)) содержащее возможные Т-корни, ииъективно отображается на некоторое подмножество qe. После этого задачу вычисления Т-корней можно свести к задаче вычисления всех корней многочлена одной переменной с коэффициентами из F с последующим восстановлением искомых Т-корней по найденым корням.
Алгоритм вычисления множества всех Т-корней
Для уменьшения вычислительной сложности алгоритма можно использовать следующие соображения:
Шаги 1.1 и 1.2 процедуры RecursiveSearch не являются обязательными. Они предназначены для уменьшения вычислительной сложности алгоритма в случае, когда Т-корень многочлена Q(T), поступившего на вход процедуры, легко найти. Однако, если п велико, операция деления многочленов нескольких переменных может занять довольно большое время (см. далее пункт 3.4 и замечание к теореме 4.14). Поэтому при больших п от шагов 1.1 и 1.2 можно отказаться.
Многочлен Q(T), поступающий на вход алгоритма FindRoots или RecursiveSearch, может иметь делители кратности 2 и выше. Если в Щх\,... ,хп] существует алгоритм вычисления наибольшего общего делителя (например, если D евклидова область или область с однозначным разложением на множители, см. [49], стр. 162), то, по аналогии с некоторыми алгоритмами факторизации (см., например, [8], [35], [36]), для уменьшения вычислительной сложности к многочлену Q(T) можно применить алгоритм вычисления многочлена Q \T), свободного от квадратов (не имеющего кратных делителей).
Для обоснования корректности алгоритма FindRoots необходимо показать, что при любых допустимых значениях входных параметров Q(T), d и п алгоритм заканчивает свою работу за конечное число шагов, а также, что множество 0д)Г1(с/), возвращаемое алгоритмом, совпадает с множеством Q,Q,n(d). Ясно, что свойства алгоритма целиком зависят от процедуры RecursiveSearch, поэтому кратко обсудим ее работу.
Во время выполнения процедуры дважды происходит рекурсивный вызов - на шагах 4 и 5.4. На шаге 4 процедура вызывается для определения всех Т-корней степени не выше 6-і многочлена М{Т) из кольца Щх\,... ,a;m_i][T], в то время как вызов процедуры на шаге 5.4 - переход к определению следующих компонентов Т-корней многочлена Q{T). В связи с этим при анализе работы процедуры удобно разделить эти вызовы, полагая, что па шаге 4 происходит обращение к отдельно выполняемому алгоритму FindRoots(M(T), 5 — i,m — 1). С учетом этого разделения весь процесс работы алгоритма удобно представить в виде ориентированного леса. Каждая вершина леса соответствует процессу выполнения процедуры RecursiveSearch с первого шага по шестой. Переход между вершинами осуществляется в двух случаях: при рекурсивном вызове процедуры и при окончании выполнения процедуры на данной вершине. При рекурсивном вызове процедуры на шаге 5.4 происходит переход от вершины к вершине внутри дерева, а при вызове процедуры на шаге 4 происходит переход от вершины текущего дерева к корню другого дерева. После окончания работы процедуры на какой-либо вершине осуществляется переход между вершинами в обратном порядке (возврат на "предыдущую" вершину). Таким образом, каждое дерево леса описывает последовательность рекурсивных вызовов процедуры на шаге 5.4. Дерево, соответствующее вызову процедуры из алгоритма FindRoots, назовем главным, а лес, порожденный работой алгоритма, назовем лесом вызовов. Отметим основные свойства любого дерева леса вызовов: - путь в дереве (последовательность вызовов на шаге 5.4) обрывается либо сразу после корня на шаге 1, либо когда множество Фт , вычисленное на шаге 4, пусто, либо когда і — 6] - глубина каждой вершины (длина пути из корня дерева в эту вершину) равна значению переменной г, корень всегда имеет глубину, равную нулю; - поскольку для любого дерева 6 d, то все пути имеют длину, не превышающую d, а все деревья - высоту, не превышающую d. В следующей лемме будет показано, что количество вершин в деревьях вызовов всегда конечно, лес состоит из конечного числа деревьев, и, как следствие, алгоритм FindRoots заканчивает свою работу за конечное число шагов.
Лемма 4.7. Процедура RecursiveSearch, вызванная с параметрами (Q(T), do, io, п, f, Q), где Q(T) - некоторый ненулевой многочлен из Ш[хі,...,хп][Т], do, го - такие неотрицательные числа, что do io, п Є N, f - некоторый многочлен из Щх\,..., хп], 0 - подмножество Щхі,..., хп], полностью заканчивает свою работу за конечное число шагов.
Доказательство. Используем индукцию по п. При п = 1 и любом допустимом значении го всегда будет выполняться первая ветвь условия на шаге 4. Поэтому лес вызовов будет содержать только главное дерево и, так как Q{T) ф 0 (а, следовательно, и М(Т) ф О, / (Т) ф 0), множество Фі будет всегда состоять из конечного числа элементов (возможно, нулевого). Следовательно, на каждой вершине на шаге 5.4 при всех значениях г Є [го, do] будет происходить конечное число рекурсивных вызовов процедуры, причем при каждом вызове значение г увеличивается, а значение 6 = do не меняется. Таким образом, главное дерево содержит конечное число путей, имеющих длину, не превышающую do — го. Необходимо отметить, что из конечности путей в дереве следует тот факт, что процедура добавляет конечное число многочленов к входному множеству G. Поэтому при п = 1 процедура RecursiveSearch при любых допустимых значениях входных параметров всегда заканчивает свою работу за конечное число шагов.
Пусть теперь п 1 и утверждение леммы справедливо для всех значений входного параметра т, меньших п. При га = п и при любом допустимом значении г о на шаге 4 всегда будет выполняться вторая ветвь условия, причем, согласно индуктивному предположению, вызываемая на шаге 4 процедура завершит свою работу за конечное число шагов, а множество Ф будет всегда состоять из конечного числа элементов (возможно, нулевого). Повторяя теперь все предыдущие рассуждения, получим, что главное дерево рекурсивных вызовов имеет конечное количество путей и КОНеЧНуЮ ВЫСОТу. Следовательно, утверждение ЛеММЫ ВерНО И При 771 = 72. Лемма доказана. Покажем теперь, что если алгоритм FindRoots вызван с параметрами ((5(Т),с, п), то по завершении своей работы он вернет все элементы множества QQ n(d). Рассмотрим вспомогательные утверждения.
Лемма 4.8. Пусть Q(T) (є D[a;i][T]) - некоторый ненулевой многочлен, d - неотрицательное целое число, 0 = RecursiveSearch(Q(T), d, 0; 1, 0; 0). Если 0 непусто, то любой многочлен f из 0 имеет полную степень не выше d.
Доказательство. По условию леммы п — т — 1, поэтому при любом і (є [0, d}) на шаге 3 процедуры RecursiveSearch многочлен М(Т) всегда принадлежит кольцу D[T], а на шаге 4 всегда выполняется первая ветвь условия и множество Ф] , если оно непусто, состоит из многочленов полной степени 0 (элементов области D). Если 0 непусто, то, как нетрудно видеть, для любого значения г Є [0, d] найдется такая последовательность рекурсивных вызовов процедуры RecursiveSearch на шаге 5.4, что множество Фі непусто, а любой многочлен д из 0 имеет вид д = 2i=0x\hk,i, где hk,i Є Фі,г, и возвращается процедурой при г — d. Таким образом, любой многочлен из 0 имеет степень не выше d.
