Código de geometría algebraica

Código matemático lineal

Los códigos de geometría algebraica , a menudo abreviados como códigos AG, son un tipo de código lineal que generaliza los códigos Reed-Solomon . El matemático ruso V. D. Goppa construyó estos códigos por primera vez en 1982. ^[1]

Historia

El nombre de estos códigos ha evolucionado desde la publicación del artículo de Goppa que los describe. Históricamente, estos códigos también se han denominado códigos geométricos de Goppa; ^[2] sin embargo, este ya no es el término estándar utilizado en la literatura sobre teoría de codificación. Esto se debe al hecho de que los códigos de Goppa son una clase distinta de códigos que también fueron construidos por Goppa a principios de la década de 1970. ^{[3] [4] [5]}

Estos códigos atrajeron el interés de la comunidad de teoría de codificación porque tienen la capacidad de superar el límite de Gilbert-Varshamov ; en el momento en que esto se descubrió, el límite de Gilbert-Varshamov no se había roto en los 30 años desde su descubrimiento. ^[6] Esto fue demostrado por Tfasman, Vladut y Zink en el mismo año en que se publicó la construcción del código, en su artículo "Curvas modulares, curvas de Shimura y códigos de Goppa, mejores que el límite de Varshamov-Gilbert". ^[7] El nombre de este artículo puede ser una fuente de confusión que afecta las referencias a los códigos de geometría algebraica en toda la literatura de teoría de codificación de los años 1980 y 1990.

Construcción

En esta sección se describe la construcción de códigos de geometría algebraica. La sección comienza con las ideas detrás de los códigos Reed-Solomon, que se utilizan para motivar la construcción de códigos de geometría algebraica.

Códigos Reed-Solomon

Los códigos de geometría algebraica son una generalización de los códigos Reed-Solomon . Construidos por Irving Reed y Gustave Solomon en 1960, los códigos Reed-Solomon utilizan polinomios univariados para formar palabras de código, evaluando polinomios de grado suficientemente pequeño en los puntos de un cuerpo finito . ^[8] ${\displaystyle \mathbb {F} _{q}}$

Formalmente, los códigos Reed-Solomon se definen de la siguiente manera. Sea . Establezca los números enteros positivos . Sea El código Reed-Solomon es el código de evaluación ${\displaystyle \mathbb {F} _{q}=\{\alpha _{1},\dots ,\alpha _{q}\}}$ ${\displaystyle k\leq n\leq q}$ $${\displaystyle \mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}}$$ ${\displaystyle RS(q,n,k)}$ $${\displaystyle 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}.}$$

Códigos a partir de curvas algebraicas

Goppa observó que se puede considerar como una línea afín, con una línea proyectiva correspondiente . Entonces, los polinomios en (es decir, los polinomios de grado menor que mayor que ) se pueden considerar como polinomios con tolerancia de polo no mayor que en el punto en el infinito en . ^[6] ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$ ${\displaystyle \mathbb {F} _{q}[x]_{<k}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$

Con esta idea en mente, Goppa se interesó en el teorema de Riemann-Roch . Los elementos de un espacio de Riemann-Roch son exactamente aquellas funciones con un orden de polos restringido por debajo de un umbral dado, ^[9] con la restricción codificada en los coeficientes de un divisor correspondiente . La evaluación de esas funciones en los puntos racionales de una curva algebraica sobre (es decir, los puntos en en la curva ) proporciona un código en el mismo sentido que la construcción de Reed-Solomon. ${\displaystyle X}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q}^{2}}$ ${\displaystyle X}$

Sin embargo, debido a que los parámetros de los códigos de geometría algebraica están conectados a campos de funciones algebraicas , las definiciones de los códigos a menudo se dan en el lenguaje de campos de funciones algebraicas sobre campos finitos. ^[10] Sin embargo, es importante recordar la conexión con las curvas algebraicas, ya que esto proporciona un método geométricamente más intuitivo de pensar en los códigos AG como extensiones de los códigos Reed-Solomon. ^[9]

Formalmente, los códigos de geometría algebraica se definen de la siguiente manera. ^[10] Sea un cuerpo de funciones algebraicas, sea la suma de lugares distintos de de grado uno, y sea un divisor con soporte disjunto de . El código de geometría algebraica asociado con divisores y se define como Puede encontrarse más información sobre estos códigos tanto en textos introductorios ^[6] como en textos avanzados sobre teoría de codificación. ^{[10] [11]} ${\displaystyle F/\mathbb {F} _{q}}$ ${\displaystyle D=P_{1}+\dots +P_{n}}$ ${\displaystyle n}$ ${\displaystyle F/\mathbb {F} _{q}}$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle C_{\mathcal {L}}(D,G)}$ ${\displaystyle D}$ ${\displaystyle G}$ $${\displaystyle C_{\mathcal {L}}(D,G):=\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(G)\rbrace \subseteq \mathbb {F} _{q}^{n}.}$$

Ejemplos

Códigos Reed-Solomon

Se puede ver que

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

donde es el punto en el infinito en la línea proyectiva y es la suma de los otros puntos -racionales. ${\displaystyle P_{\infty }}$ ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$ ${\displaystyle D=P_{1}+\dots +P_{q}}$ ${\displaystyle \mathbb {F} _{q}}$

Códigos hermíticos de un punto

La curva hermítica está dada por la ecuación considerada sobre el cuerpo . ^[2] Esta curva es de particular importancia porque cumple con el límite de Hasse-Weil con igualdad, y por lo tanto tiene el número máximo de puntos afines sobre . ^[12] Con respecto a los códigos de geometría algebraica, esto significa que los códigos hermíticos son largos en relación con el alfabeto sobre el que están definidos. ^[13] $${\displaystyle x^{q+1}=y^{q}+y}$$ ${\displaystyle \mathbb {F} _{q^{2}}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$

El espacio de Riemann-Roch del campo de funciones hermíticas se da en el siguiente enunciado. ^[2] Para el campo de funciones hermíticas dado por y para , el espacio de Riemann-Roch es donde es el punto en el infinito en . ${\displaystyle \mathbb {F} _{q^{2}}(x,y)}$ ${\displaystyle x^{q+1}=y^{q}+y}$ ${\displaystyle m\in \mathbb {Z} ^{+}}$ ${\displaystyle {\mathcal {L}}(mP_{\infty })}$ $${\displaystyle {\mathcal {L}}(mP_{\infty })=\left\langle x^{a}y^{b}:0\leq b\leq q-1,aq+b(q+1)\leq m\right\rangle ,}$$ ${\displaystyle P_{\infty }}$ ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$

Con esto, el código hermítico de un punto se puede definir de la siguiente manera. Sea la curva hermítica definida sobre . ${\displaystyle {\mathcal {H}}_{q}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$

Sea el punto en el infinito en , y un divisor apoyado por los puntos -racionales distintos en otros que . ${\displaystyle P_{\infty }}$ ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$ $${\displaystyle D=P_{1}+\cdots +P_{n}}$$ ${\displaystyle n:=q^{3}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$ ${\displaystyle {\mathcal {H}}_{q}}$ ${\displaystyle P_{\infty }}$

El código hermítico de un punto es ${\displaystyle C(D,mP_{\infty })}$

${\displaystyle 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}.}$

Referencias

1. Goppa, Valerii Denisovich (1982). "Códigos álgebraico-geométricos". Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya . 46 (4): 726–781 - vía Academia de Ciencias de Rusia, Instituto de Matemáticas Steklov de Rusia.
2. Stichtenoth, Henning (1988). "Una nota sobre códigos hermíticos sobre GF(q^2)". IEEE Transactions on Information Theory . 34 (5): 1345–1348 – vía IEEE.
3. Goppa, Valery Denisovich (1970). "Una nueva clase de códigos de corrección de errores lineales". Probl. Inf. Transm . 6 : 300–304.
4. Goppa, Valerii Denisovich (1972). "Códigos construidos sobre la base de códigos (L, g)". Problemy Peredachi Informatsii . 8 (2): 107–109 – vía Academia Rusa de Ciencias, Departamento de Informática, Equipos Informáticos y.
5. Berlekamp, ​​Elwyn (1973). "Códigos Goppa". IEEE Transactions on Information Theory . 19 (5): 590–592 – vía IEEE.
6. Walker, Judy L. (2000). Códigos y curvas . American Mathematical Society. pág. 15. ISBN 0-8218-2628-X.
7. Tsfasman, Michael; Vladut, Serge; Zink, Thomas (1982). "Las curvas modulares, las curvas de Shimura y los códigos Goppa son mejores que el límite de Varshamov-Gilbert". Mathematische Nachrichten .
8. Reed, Irving ; Solomon, Gustave (1960). "Códigos polinómicos sobre ciertos cuerpos finitos". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 8 (2): 300–304 – vía SIAM.
9. Hoholdt, Tom; van Lint, Jacobus ; Pellikaan, Ruud (1998). «Códigos de geometría algebraica» (PDF) . Manual de teoría de la codificación . 1 (Parte 1): 871–961 - vía Elsevier Amsterdam.
10. Stichtenoth, Henning (2009). Campos y códigos de funciones algebraicas (2.ª ed.). Springer Science & Business Media. pp. 45–65. ISBN 978-3-540-76878-4.
11. van Lint, Jacobus (1999). Introducción a la teoría de la codificación (3.ª ed.). Springer. pp. 148–166. ISBN 978-3-642-63653-0.
12. Garcia, Arnoldo ; Viana, Paulo (1986). "Puntos de Weierstrass en ciertas curvas no clásicas". Archiv der Mathematik . 46 : 315–322 – vía Springer.
13. Tiersma, HJ (1987). "Observaciones sobre códigos a partir de curvas hermíticas". IEEE Transactions on Information Theory . 33 (4): 605–609 – vía IEEE.