Описано побудову AG-коду і процедура декодування з точки зору просторів, асоційованих з дівізоров

Анотація наукової статті з математики, автор наукової роботи - Алексєєнко Катерина Сергіївна


The construction of an AG-code and the process of decoding are described by the Rimann-Roch spaces


Область наук:

  • Математика

  • Рік видавництва: 2010


    Журнал: Вісник Балтійського федерального університету ім. І. Канта. Серія: Фізико-математичні та технічні науки


    Наукова стаття на тему 'Алгебро-геометричний код, асоційований з кривою роду 3 над кінцевим полем з дискримінантом? {19'

    Текст наукової роботи на тему «Алгебро-геометричний код, асоційований з кривою роду 3 над кінцевим полем з дискримінантом? {19»

    ?ЗАХИСТ ІНФОРМАЦІЇ

    УДК 512.81, 519.95

    Е. С. Олексієнко

    Алгебра-ГЕОМЕТРИЧНИЙ КОД,

    АСОЦІЙОВАНИЙ З КРИВИЙ РОДА 3 НАД КІНЦЕВИМ ПОЛЕМ З Дискримінант -19

    Описано побудову AG-коду і процедура декодування з точки зору просторів, асоційованих з дівізоров.

    The construction of an AG-code and the process of decoding are described by the Rimann-Roch spaces.

    Ключові слова: алгебро-геометричний код, крива алгебри, простір Рімана-Роха.

    Key words: algebraic-geometric code, algebraic curve, code automorphism, Riemann-Roch space.

    Ідея побудови лінійних кодів, асоційованих з алгебраїчними кривими, визначеними над кінцевим полем Fq, була представлена ​​Гоппе. Такі коди зазвичай

    називаються алгебро-геометричними кодами (AG-кодами). Зазвичай AG-коди з хорошими параметрами асоційовані з кривими з великим числом F? - раціональних точок в

    Відповідно до родом кривих g.

    Мета цієї статті - дослідити параметри AG-коду, асоційованого з деяким класом максимальних кривих. Число точок таких кривих задовольняє кордоні Хассе - Вейля - Серрі.

    \ Z2 = 5 + 45x + 30x2 + 10y,

    Розглянемо максимальну криву C: < певну над полем F47,

    ^ Y = x + x + 38,

    з числом раціональних точок, рівним n = C (F) = 87. Для спрощення подальших обчислень дану систему рівнянь ми можемо звести до наступного рівняння над F47:

    z4 + 37z2 + 4z2x + 34z2x2 + 32 + 21x + 22x2 + 15x3 + 7x4 = 0. (1)

    Перейдемо безпосередньо до обчислення параметрів AG-коду. Нехай CL (D, G) - алгеброгеометріческій код, визначений для раціональних дівізоров D і G на несінгулярной проективної кривої C над F47. Як дівізоров D = P1 + ... + P87 розглянемо дільник, що складається з суми точок нашої кривої, де P1 = (2, 46, 8), ..., P87 = (46,6, 35). Якщо ж звести нашу систему до рівняння (1), то досить розглянути точки P1 = (2, 8), ..., P87 = (46, 35). Відзначимо, що ступеня точок рівні degPt = 1 для i = 1, ..., 87. Як дільник G, такого, що supp GIsupp D = 0, розглянемо G = 5O, де G = f_1 (ю ') =

    = I e (O | ж ') - O, і f: C ^ E, ж' e E, же P1. Оскільки degO = 2, то deg G = 10, і

    O | ю

    dim G = deg G +1 - g = 8 (по теоремі Рімана - Роха).

    Нехай L (G) - простір, асоційоване з дівізоров G. Як базису L (G) розглянемо {1, x, x2, x3, z, z2, xz2, x2z2 j. тоді код

    CL (D, G) = {(1 (P1), ..., 1 (P87), ..., x2z2 (P1), ..., x2z2 (P87) 11, ..., x2z2 e L ( G) j з f477.

    Параметри коду знайдемо за допомогою наступної теореми.

    Теорема. Якщо ступінь дівізоров G менше n, то CL (D, G) - [n, k, dj-код, де d > n - deg G -1 і k = dim G > deg G +1 - g -1.

    Вісник Російського державного університету ім. І. Канта. 2010. Вип. 10. С. 104-107.

    Остаточно, з огляду на нижню межу для мінімального 'відстані, отримуємо код з параметрами [87, 8, d], де 76 < d < 81. Значення d уточнимо за допомогою наступної теореми.

    Теорема. Нехай CL (D, G) - [n, k, d] -Лінійний код над полем Fq з перевірочної матрицею B, s є N.

    Тоді d = s тоді і тільки тоді, коли будь-які s - 1 стовпців матриці B є лінійно незалежними і існують s лінійно залежних стовпців.

    Г fl (Pl) ... fl (Pn) Л

    З огляду на, що породжує матриця A =::

    U (Pl) ... fk (Pn)

    де fi - елементи базису простору L (G) для i = 1, ..., k, а також вирішуючи систему рівнянь

    B • AT = 0 і з огляду на попередню теорему, остаточно отримуємо, що параметр d = 77.

    Таким чином, код CL (D, G) є [87, 8, 77]-кодом.

    Опишемо процедуру декодування для CL (D, G). Нехай а - вектор, який ми бажаємо декодувати. Відзначимо, що відстань від а до кодового слова CL (D, G) мінімально. Також ми знайдемо функцію локатора помилок вектора а, яку можна визначити, вирішивши систему лінійних рівнянь. Нехай t - ціле, яке задовольняє умові

    0 < t <(D * -1) / 2, (2)

    де d * - визначальне відстань коду CL (D, G). Наступна теорема дасть нам умови, щодо яких ми знайдемо простір функцій локатора помилок.

    Теорема. Якщо є дільник G1 на кривій C, що задовольняє умовам

    supp G11supp D = 0, degG1 <degG- (2g-2) -t, dimG1 >t, (3)

    то L (G1) містить функцію локатора помилок для вектора а. Зокрема, f є L (G1) є

    и

    функцією локатора помилок тоді і тільки тоді, коли f = I аі ^ и, де (Х1, ..., Хі) = К, ..., аі) -

    1 = 1

    нетривіальне рішення лінійної системи и

    I [а,! | Пр] • Хі = 0, для р = 1, ..., k, (4)

    і = 1

    де (| 1, ...,?, i} і {n1, ..., nk} - базиси просторів L (G1) і L (G - G1) відповідно.

    У нашому випадку в якості дільник G1, який задовольняє умові (3) попередньої теореми, слід розглянути G1 = 2O. При цьому очевидно, що t = 2 задовольняє умові (2).

    Тепер визначимо базиси просторів: L (G1), L (G - G1), L (G). Для цього спочатку знайдемо розмірності дівізоров, асоційованих з цими просторами. dim G1 = dim 2O = 3 = і, dim (G - G1) = dim 3O = 4 = k.

    Маємо: (| 1, ..., ^} = (1, x, z} - базис L (G1); (n1, ..., nk} = (1, x, z, x2} - базис L ( G-G1); (| 1, ...,}

    = {1, x, x2, x3, z, z2, xz2, x2z21 - базис L (G).

    Система (4) набуває вигляду

    [А, Пр] • x1 + [а, x (Pi) • Пр] • x2 + [а, z (P) • Пр] • x3 = 0, р = 1, ..., 4; i = 1, ..., 87, або більш докладно:

    [А, 1] • x1 + [а, x (Pi)] • x2 + [а, z (P. \)] • x3 = 0,

    [А, x (Pi)] • x1 + [а, x2 (Pi)] • x2 + [а, xz (Pt)] • x3 = 0,

    [А, z (Pi)] • x1 + [а, xz (Pi)] • x2 + [а, z2 (Pt)] • x3 = 0,

    [А, x2 (Pi)] • x1 + [а, x3 (Pi)] • x2 + [а, x2z (Pi)] • x3 = 0.

    Остаточно система зводиться до наступного вигляду:

    39 • x3 = 0,

    13 • x3 = 0,

    39 • x1 +13 • x2 + 21 • x3 = 0,

    38 • x3 = 0.

    Отже, рівняння має нетривіальне рішення: (x1,44x1,0) в поле F47. Поклавши x1 = 1, маємо рішення системи (1, 44, 0).

    и

    Отже, отримуємо функцію локатора помилок f = ЕаіЛ ,, то есгь f (pi) = 1 + 44 • x (P) для i = 1, •••,

    ,= 1

    87. Нарешті, вирішимо систему

    X С, (Pv) • xv = [а, Z,],

    veN (f)

    де N (f) = {v | f (Pv) = 0, v = 1, ..., 87}. Рішенням є вектор x =

    = (0, ..., 0, 46, 46, 1, 1, 0, ..., 0), де на i-х місцях стоять нулі при i ф 31, 32, 33, 34.

    Вважаючи e = x, отримуємо, що

    з = а - e = (34, 7, 41, 0, 9, 1, 1, 31, 1, 1, 34, 0, 1,., 2, 2, 0, 0, 1,., 2, 0 ) -

    кодове слово, що асоціюється з вектором а (на місцях трьох крапок варто відповідне число одиниць). Слід також зазначити, що з є CQ (D, G) і w (e) < t +1, де CQ (D, G) - код, дуальний до CL (D, G), w (e) - вага вектора помилок e.

    Якщо ж покласти G = 41O, то процедури побудови коду і декодування здійснюються аналогічним чином, за винятком громіздких обчислень і викладок. Тому обмежимося лише поданням кінцевого результату, а саме: CL (D, G) є

    [87, 80, 5]-кодом Гоппе.

    Ми показали процедуру декодування з точністю до t = 2 помилок для геометричного коду Гоппе CL (D, G). Слід також зазначити, що всі обчислення перевірені і в системі комп'ютерної алгебри MAGMA. Таким чином, можна зробити висновок, що AG-коди, засновані на максимальних кривих, визначених у [1] над кінцевим полем з дискримінантом -19, є придатними для кодування інформації.

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

    1. Alekseenko E., Aleshnikov S., Markin N., Zaytsev A. Optimal curves of genus 3 over finite fields with discriminant -19 // arXiv: 0902.1091v1 [math. AG], Feb. 2009.

    2. Алексєєнко Е. С., Алешніков С. І., Зайцев А. І. Загальні рівняння оптимальних кривих над кінцевим полем з дискримінантом -19 / / Вісник Російського державного університету ім. І. Канта. 2008. Вип. 10. С. 73 - 79.

    3. Stichtenoth H. Algebraic function fields and codes. N.-Y .: Springe-Verlag, 1991.

    4. Goppa V. D. Codes on algebraic curves // Dokl. Akad. Nauk. SSSR. 1981. 259. P. 1289 - 1290.

    5. Blahut R.E. Decoding of cyclic codes and codes on curves // Handbook of coding theory. V. S. PLess, W. C. Huffman and R. A. Brualdi, eds. Amsterdam: Elsevier, 1998..

    6. Feng G.-L., Rao T. R. N. Improved geometric Goppa codes. Part I: Basic Theory // IEEE Trans. Inform. Theory. 1995. Vol. 41. P. 1678-1693.

    про автора

    Катерина Сергіївна Алексєєнко - асист., РГУ ім. І. Канта,

    e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Author

    Ekaterina Alekseenko - assistant, IKSUR, e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.


    Ключові слова: Алгебра-ГЕОМЕТРИЧНИЙ КОД /кривих алгебри /ПРОСТІР Риму-Роха /ALGEBRAIC-GEOMETRIC CODE /ALGEBRAIC CURVE /CODE AUTOMORPHISM /RIEMANNROCH SPACE

    Завантажити оригінал статті:

    Завантажити