Código de geometría algebraica

Código lineal matemático

Los códigos de geometría algebraica , a menudo abreviados códigos AG, son un tipo de código lineal que generaliza los códigos Reed-Solomon . El matemático ruso VD 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 Goppa geométricos; ^[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 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 la teoría de la codificación porque tienen la capacidad de superar el límite de Gilbert-Varshamov ; En el momento en que se descubrió esto, el vínculo Gilbert-Varshamov no se había roto en los 30 años transcurridos desde su descubrimiento. ^[6] Esto fue demostrado por Tfasman, Vladut y Zink 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 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 códigos de geometría algebraica a lo largo de 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-Salomón

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

Formalmente, los códigos Reed-Solomon se definen de la siguiente manera. Dejar . Establecer números enteros positivos . Deje que el código Reed-Solomon sea 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 de curvas algebraicas

Goppa observó que se puede considerar como una línea afín, con su correspondiente línea proyectiva . Entonces, los polinomios en (es decir, los polinomios de grado menor que superior a ) se pueden considerar como polinomios con un margen de polos 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 miró hacia el teorema de Riemann-Roch . Los elementos de un espacio de Riemann-Roch son exactamente aquellas funciones con el orden de los polos restringido por debajo de un umbral determinado, ^[9] y la restricción está codificada en los coeficientes de un divisor correspondiente . La evaluación de esas funciones en los puntos racionales de una curva algebraica (es decir, los puntos dentro de la curva ) da 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 para 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 campo de función algebraica, sea la suma de distintos lugares 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 Se puede encontrar 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

Uno puede ver eso

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

donde es el punto en el infinito de la recta proyectiva y es la suma de los demás 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 hermitianos de un punto

La curva hermitiana viene dada por la ecuación considerada sobre el campo . ^[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 hermitianos 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 hermitiano se proporciona en la siguiente declaración. ^[2] Para el campo de función hermitiano dado por y para , el espacio de Riemann-Roch es donde está 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 eso, el código hermitiano de un punto se puede definir de la siguiente manera. Sea la curva hermitiana definida sobre . ${\displaystyle {\mathcal {H}}_{q}}$ ${\displaystyle \mathbb {F} _{q^{2}}}$

Sea el punto en el infinito de , y sea un divisor sostenido por los distintos puntos racionales de distintos de . ${\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 hermitiano 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 los códigos hermitianos sobre GF (q ^ 2)". Transacciones IEEE sobre teoría de la información . 34 (5): 1345–1348 - vía IEEE.
3. Goppa, Valery Denisovich (1970). "Una nueva clase de códigos lineales de corrección de errores". Problema. inf. Trans . 6 : 300–304.
4. Goppa, Valerii Denisovich (1972). "Códigos construidos sobre la base de códigos (L, g)". Problema Peredachi Informatsii . 8 (2): 107–109 - vía Academia de Ciencias de Rusia, Rama de Informática, Equipos Informáticos y.
5. Berlekamp, ​​Elwyn (1973). "Códigos Goppa". Transacciones IEEE sobre teoría de la información . 19 (5): 590–592 - vía IEEE.
6. Walker, Judy L. (2000). Códigos y Curvas . Sociedad Matemática Estadounidense. pag. 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. Caña, Irving ; Salomón, Gustave (1960). "Códigos polinómicos sobre ciertos campos 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). Códigos y campos de funciones algebraicas (2ª ed.). Medios de ciencia y negocios de Springer. págs. 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.). Saltador. págs. 148-166. ISBN 978-3-642-63653-0.
12. García, Arnoldo ; Viana, Paulo (1986). "Puntos de Weierstrass en determinadas curvas no clásicas". Archiv der Mathematik . 46 : 315–322 - vía Springer.
13. Tiersma, HJ (1987). "Observaciones sobre códigos de curvas hermitianas". Transacciones IEEE sobre teoría de la información . 33 (4): 605–609 - vía IEEE.