Код алгебраической геометрии

Коды алгебраической геометрии , часто сокращенно коды AG, представляют собой тип линейного кода , который обобщает коды Рида – Соломона . российский математик В.Д. Гоппа в 1982 году. Эти коды впервые построил ^[1]

История [ править ]

Название этих кодов изменилось с момента публикации статьи Гоппы, описывающей их. Исторически эти коды также назывались геометрическими кодами Гоппы; ^[2] однако это больше не стандартный термин, используемый в литературе по теории кодирования. Это связано с тем, что коды Гоппы представляют собой отдельный класс кодов, которые также были созданы Гоппой в начале 1970-х годов. ^[3]^[4]^[5]

Эти коды вызвали интерес в сообществе теоретиков кодирования, поскольку они способны превосходить границу Гилберта-Варшамова ; на момент открытия граница Гилберта-Варшамова не была нарушена в течение 30 лет с момента ее открытия. ^[6] Это было продемонстрировано Тфасманом, Владутом и Зинком в том же году, когда была опубликована конструкция кода, в их статье «Модулярные кривые, кривые Шимуры и коды Гоппы, лучше, чем граница Варшамова-Гилберта». ^[7] Название этой статьи может быть одним из источников путаницы, влияющей на ссылки на коды алгебраической геометрии в литературе по теории кодирования 1980-х и 1990-х годов.

Строительство [ править ]

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

- Соломона Коды Рида

Коды алгебраической геометрии являются обобщением кодов Рида–Соломона . Коды Рида – Соломона , созданные Ирвингом Ридом и Гюставом Соломоном в 1960 году, используют одномерные полиномы для формирования кодовых слов путем оценки полиномов достаточно малой степени в точках конечного поля. $\mathbb {F} _{q}$ . ^[8]

Формально коды Рида–Соломона определяются следующим образом. Позволять $\mathbb {F} _{q}=\{\alpha _{1},\dots ,\alpha _{q}\}$ . Установить положительные целые числа $k\leq n\leq q$ . Позволять

\mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}

Код Рида-Соломона

RS(q,n,k)

это оценочный код

RS(q,n,k)=\left\{\left(f(\alpha _{1}),f(\alpha _{2}),\dots ,f(\alpha _{n})\right):f\in \mathbb {F} _{q}[x]_{<k}\right\}\subseteq \mathbb {F} _{q}^{n}.

Коды из алгебраических кривых [ править ]

Гоппа заметил, что $\mathbb {F} _{q}$ можно рассматривать как аффинную прямую с соответствующей проективной линией $\mathbb {P} _{\mathbb {F} _{q}}^{1}$ . Тогда полиномы в $\mathbb {F} _{q}[x]_{<k}$ (т.е. полиномы степени меньше $k$ над $\mathbb {F} _{q}$ ) можно рассматривать как многочлены с допуском на полюс не более $k$ в бесконечной точке $\mathbb {P} _{\mathbb {F} _{q}}^{1}$ . ^[6]

Имея в виду эту идею, Гоппа обратился к теореме Римана-Роха . Элементами пространства Римана–Роха являются именно те функции, порядок полюсов которых ограничен ниже заданного порога: ^[9] причем ограничение кодируется в коэффициентах соответствующего делителя . Вычисление этих функций в рациональных точках алгебраической кривой $X$ над $\mathbb {F} _{q}$ (то есть точки в $\mathbb {F} _{q}^{2}$ на кривой $X$ ) дает код в том же смысле, что и конструкция Рида-Соломона.

Однако, поскольку параметры кодов алгебраической геометрии связаны с полями алгебраических функций , определения кодов часто даются на языке полей алгебраических функций над конечными полями. ^[10] Тем не менее, важно помнить о связи с алгебраическими кривыми, поскольку это обеспечивает более геометрически интуитивный метод рассмотрения AG-кодов как расширений кодов Рида-Соломона. ^[9]

Формально коды алгебраической геометрии определяются следующим образом. ^[10] Позволять $F/\mathbb {F} _{q}$ быть полем алгебраической функции, $D=P_{1}+\dots +P_{n}$ быть суммой $n$ отдельные места $F/\mathbb {F} _{q}$ первой степени и $G$ быть делителем с непересекающейся опорой из $D$ . Код алгебраической геометрии $C_{\mathcal {L}}(D,G)$ связанный с делителями $D$ и $G$ определяется как

C_{\mathcal {L}}(D,G):=\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(G)\rbrace \subseteq \mathbb {F} _{q}^{n}.

Более подробную информацию об этих кодах можно найти в обоих вводных текстах. ^[6] а также продвинутые тексты по теории кодирования. ^[10]^[11]

Примеры [ править ]

Коды Рида-Соломона [ править ]

Это можно увидеть

$RS(q,n,k)={\mathcal {C}}_{\mathcal {L}}(D,(k-1)P_{\infty })$

где $P_{\infty }$ - это бесконечная точка на проективной прямой $\mathbb {P} _{\mathbb {F} _{q}}^{1}$ и $D=P_{1}+\dots +P_{q}$ это сумма других $\mathbb {F} _{q}$ -рациональные моменты.

Одноточечные эрмитовы коды

Эрмитова кривая задается уравнением

x^{q+1}=y^{q}+y

считается по полю

\mathbb {F} _{q^{2}}

. ^[2] Эта кривая имеет особое значение, поскольку она с равенством удовлетворяет границе Хассе – Вейля и, таким образом, имеет максимальное количество аффинных точек над ней.

\mathbb {F} _{q^{2}}

. ^[12] Применительно к кодам алгебраической геометрии это означает, что эрмитовы коды длиннее алфавита, в котором они определены. ^[13]

Пространство Римана–Роха эрмитова функционального поля дается в следующем утверждении. ^[2] Для поля эрмитовой функции $\mathbb {F} _{q^{2}}(x,y)$ данный $x^{q+1}=y^{q}+y$ и для $m\in \mathbb {Z} ^{+}$ , пространство Римана–Роха ${\mathcal {L}}(mP_{\infty })$ является

{\mathcal {L}}(mP_{\infty })=\left\langle x^{a}y^{b}:0\leq b\leq q-1,aq+b(q+1)\leq m\right\rangle ,

где

P_{\infty }

это точка на бесконечности

{\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})

.

При этом одноточечный эрмитовский код можно определить следующим образом. Позволять ${\mathcal {H}}_{q}$ — эрмитова кривая, определенная над $\mathbb {F} _{q^{2}}$ .

Позволять $P_{\infty }$ быть точкой в бесконечности на ${\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})$ , и

D=P_{1}+\cdots +P_{n}

быть делителем, поддерживаемым

n:=q^{3}

отчетливый

\mathbb {F} _{q^{2}}

-рациональные точки зрения на

{\mathcal {H}}_{q}

кроме

P_{\infty }

.

Одноточечный эрмитовский код $C(D,mP_{\infty })$ является

$C(D,mP_{\infty }):=\left\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(mP_{\infty })\right\rbrace \subseteq \mathbb {F} _{q^{2}}^{n}.$

Ссылки [ править ]

^ Goppa, Valerii Denisovich (1982). "Algebraico-geometric codes" . Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya . 46 (4): 726–781 – via Russian Academy of Sciences, Steklov Mathematical Institute of Russian.
^ Jump up to: Перейти обратно: ^а ^б ^с Стихтенот, Хеннинг (1988). «Заметка об эрмитовых кодах над GF(q^2)» . Транзакции IEEE по теории информации . 34 (5): 1345–1348 – через IEEE.
^ Гоппа, Валерий Денисович (1970). «Новый класс линейных кодов, исправляющих ошибки» . Пробл. Инф. Трансм . 6 : 300–304.
^ Гоппа, Валерий Денисович (1972). «Коды, построенные на основе (L,g)-кодов» . Проблемы передачи информации . 8 (2): 107–109 – через Отделение информатики и вычислительной техники РАН.
^ Берлекамп, Элвин (1973). «Коды Гоппы» . Транзакции IEEE по теории информации . 19 (5): 590–592 – через IEEE.
^ Jump up to: Перейти обратно: ^а ^б ^с Уокер, Джуди Л. (2000). Коды и кривые . Американское математическое общество. п. 15. ISBN 0-8218-2628-Х .
^ Цфасман, Михаил; Владут, Серж; Зинк, Томас (1982). «Модулярные кривые, кривые Шимуры и коды Гоппы лучше, чем граница Варшамова-Гилберта» . Математические новости .
^ Рид, Ирвинг ; Соломон, Гюстав (1960). «Полиномиальные коды над некоторыми конечными полями» . Журнал Общества промышленной и прикладной математики . 8 (2): 300–304 – через SIAM.
^ Jump up to: Перейти обратно: ^а ^б Хохолдт, Том; ван Линт, Джеймс ; Пелликаан, Рууд (1998). «Коды алгебраической геометрии» (PDF) . Справочник по теории кодирования . 1 (Часть 1): 871–961 – через Elsevier Amsterdam.
^ Jump up to: Перейти обратно: ^а ^б ^с Стихтенот, Хеннинг (2009). Алгебраические функциональные поля и коды (2-е изд.). Springer Science & Business Media. стр. 45–65. ISBN 978-3-540-76878-4 .
^ ван Линт, Якобус (1999). Введение в теорию кодирования (3-е изд.). Спрингер. стр. 148–166. ISBN 978-3-642-63653-0 .
^ Гарсия, Арнольдо ; Виана, Пауло (1986). «Точки Вейерштрасса на некоторых неклассических кривых» . Архив математики . 46 : 315–322 – через Спрингер.
^ Тирсма, HJ (1987). «Замечания о кодах из эрмитовых кривых» . Транзакции IEEE по теории информации . 33 (4): 605–609 – через IEEE.

[1] Goppa, Valerii Denisovich (1982). "Algebraico-geometric codes" . Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya . 46 (4): 726–781 – via Russian Academy of Sciences, Steklov Mathematical Institute of Russian.

[:0-2] Jump up to: Перейти обратно: ^а ^б ^с Стихтенот, Хеннинг (1988). «Заметка об эрмитовых кодах над GF(q^2)» . Транзакции IEEE по теории информации . 34 (5): 1345–1348 – через IEEE.

[3] Гоппа, Валерий Денисович (1970). «Новый класс линейных кодов, исправляющих ошибки» . Пробл. Инф. Трансм . 6 : 300–304.

[4] Гоппа, Валерий Денисович (1972). «Коды, построенные на основе (L,g)-кодов» . Проблемы передачи информации . 8 (2): 107–109 – через Отделение информатики и вычислительной техники РАН.

[5] Берлекамп, Элвин (1973). «Коды Гоппы» . Транзакции IEEE по теории информации . 19 (5): 590–592 – через IEEE.

[:1-6] Jump up to: Перейти обратно: ^а ^б ^с Уокер, Джуди Л. (2000). Коды и кривые . Американское математическое общество. п. 15. ISBN 0-8218-2628-Х .

[7] Цфасман, Михаил; Владут, Серж; Зинк, Томас (1982). «Модулярные кривые, кривые Шимуры и коды Гоппы лучше, чем граница Варшамова-Гилберта» . Математические новости .

[8] Рид, Ирвинг ; Соломон, Гюстав (1960). «Полиномиальные коды над некоторыми конечными полями» . Журнал Общества промышленной и прикладной математики . 8 (2): 300–304 – через SIAM.

[:2-9] Jump up to: Перейти обратно: ^а ^б Хохолдт, Том; ван Линт, Джеймс ; Пелликаан, Рууд (1998). «Коды алгебраической геометрии» (PDF) . Справочник по теории кодирования . 1 (Часть 1): 871–961 – через Elsevier Amsterdam.

[:3-10] Jump up to: Перейти обратно: ^а ^б ^с Стихтенот, Хеннинг (2009). Алгебраические функциональные поля и коды (2-е изд.). Springer Science & Business Media. стр. 45–65. ISBN 978-3-540-76878-4 .

[11] ван Линт, Якобус (1999). Введение в теорию кодирования (3-е изд.). Спрингер. стр. 148–166. ISBN 978-3-642-63653-0 .

[12] Гарсия, Арнольдо ; Виана, Пауло (1986). «Точки Вейерштрасса на некоторых неклассических кривых» . Архив математики . 46 : 315–322 – через Спрингер.

[13] Тирсма, HJ (1987). «Замечания о кодах из эрмитовых кривых» . Транзакции IEEE по теории информации . 33 (4): 605–609 – через IEEE.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]