Pesos de hamming de códigos castillo

Resum

En la segunda mitad del siglo pasado hemos sido testigos de lo que podríamos llamar la gran revolución de la información digital. La principal causa de este suceso es la matematización de la teoría de la comunicación, ver [57]. En un proceso de transmisión de información un emisor envía un mensaje a un receptor a través de un canal. En este proceso el mensaje es convertido en una larga secuencia de símbolos (información digital) pertenecientes a un cuerpo finito $\mathbb{F}_q$ (alfabeto). Según las características del canal y nuestras necesidades, la información se codifica de tal manera que el proceso de comunicación sea lo más rápido, fiable, seguro o secreto posible, dando lugar a diferentes tipos de códigos: compresores, correctores de errores, criptográficos o esteganográficos. En esta memoria consideramos los códigos correctores de errores, cuyo propósito es preservar la calidad de la información transmitida a través de un canal con ruido. La palabra ``ruido'' hace referencia a cualquier circunstancia que produce errores y por tanto distorsiona el mensaje original. Luego el objetivo de estos códigos es corregir la mayor cantidad posible de errores que puedan ocurrir durante la transmisión de la información. Los códigos correctores de errores más estudiados y utilizados actualmente son los códigos lineales. Estos son subespacios $k$-dimensionales de $\mathbb{F}_q^n$. Ahora, si consideramos la distancia de Hamming sobre $\F_q^n$, es decir el número de componentes en que difieren dos vectores (palabras), entonces el principio utilizado para corregir errores es el de distancia mínima: recibida una palabra con errores se decodificará por la palabra del código más cercana según la métrica de Hamming. En este sentido, la capacidad correctora de un código esta determinada por su distancia mínima (o peso mínimo de Hamming). Una generalización de este concepto fue introducida independientemente por Tor Helleseth, Torleiv Klove y J. Mykkeleveit en [29] y por Victor Wei en [63], motivada por sus aplicaciones en criptografía. Para $r=1,\dots,k$, el $r$-ésimo peso de Hamming, $d_r$, de un código lineal $C$ de dimensión $k$, es el mínimo cardinal del soporte de un subcódigo $r$-dimensional de $C$. Así, $d_1$ es la distancia mínima. Un cálculo completo de los parámetros de un código lineal $C$ debería incluir los valores $n,k,d_1,d_2,\dots,d_k$. En general calcular la distancia mínima de $C$ es un problema difícil (más exactamente, es un problema NP-completo, ver [5]). Luego calcular todos los pesos de Hamming generalizados es aún más complicado. A menudo tenemos que conformarnos con obtener una estimación de estos valores basándonos en alguna cota inferior disponible. Muchas de estas cotas inferiores para la distancia mínima y, en general, para todos los pesos de Hamming generalizados, son diseñadas para una familia (o construcción) particular de códigos. En esta memoria consideramos las cotas de tipo orden, basadas en obtener estimaciones sobre subconjuntos parciales de palabras del código. De esta manera a menudo se obtienen mejores resultados que cuando se considera el conjunto total de palabras [1, 12, 30, 41]. Sean $\calx$ una curva de género $g$ sobre $\mathbb{F}_q$ y $\calp=\{P_1,\dots,P_n\}$ un conjunto de $n$ distintos puntos racionales de $\calx$. Sea $G$ un divisor racional de grado no negativo y soporte disjunto al de $D=P_1+\dots+P_n$. El código algebraico geométrico (AG para acortar) asociado a la terna $(\calx,D,G)$ está definido como la imagen del espacio de Riemman-Roch $\call(G)$, de funciones racionales que tienen ceros y polos especificados por $G$, por la función evaluación $ ev_\calp :\call(G)\rightarrow\fq^n, \ \ ev_\calp(f)=(f(P_1),\dots,f(P_n)). $ Los códigos AG fueron introducidos por Valery Denisovich Goppa en los setenta, [22,23] y adquirieron notoriedad debido a que en los ochenta, Michael Tsfasman, Serge Vladuts y Thomas Zink construyeron explícitamente familias de códigos AG cuyos parámetros sobrepasan la cota de Gilbert-Varshamov, una medida clásica que evalúa el comportamiento asintótico de una familia de códigos, ver [61]. En general, los parámetros de los códigos AG no son fáciles de calcular, ya que dependen de la información aritmética y geométrica de la curva sobre la cual se han construido. Si consideramos el divisor $G$ obtenido como un múltiplo de un punto racional $Q$, entonces los correspondientes códigos AG son llamados unipuntuales y permiten un tratamiento teórico y práctico más simple. El espacio $\call(mQ)$, de funciones racionales con polos únicamente en $Q$ de orden a lo sumo $m$, está fuertemente relacionado con el semigrupo de Weierstrass de $Q$, $H(Q)=\{-v_Q(f):f\in\call(\infty Q)\}$ donde $v_Q$ es la valoración en $Q$ y $\call(\infty Q)=\bigcup_{m\in\mathbb{Z}}\call(mQ)$. Los códigos Castillo son códigos AG unipuntuales construidos a partir de una curva Castillo, es decir una curva que tiene un punto racional con semigrupo de Weierstrass simétrico y alcanza la cota superior de Lewittes para el número de puntos racionales. Esta familia contiene algunos de los más importantes códigos AG estudiados hasta la fecha. Las curvas Castillo y los códigos Castillo fueron introducidos por Carlos Munuera, Alonso Sepúlveda y Fernando Torres en [47]. En éste artículo también se muestra que estos códigos pueden ser estudiados de manera unificada sin importar la curva de la que proceden. Organización de la memoria y resultados obtenidos. La presente memoria está dedicada a obtener una caracterización explícita sobre las estimaciones de la distancia mínima y los pesos de Hamming generalizados de los códigos Castillo. La exposición consta de cuatro capítulos. En el capítulo 1, Preliminares, establecemos el estado del arte de los temas de investigación a los que haremos referencia en los capítulos posteriores. Iniciando con la teoría básica de códigos lineales en donde pondremos énfasis en las propiedades de los pesos de Hamming generalizados y, en especial, en las cotas de tipo orden para la distancia mínima y los pesos de Hamming generalizados. Finalizaremos con la teoría de códigos AG, resaltando la construcción y propiedades fundamentales de la familia especial de códigos Castillo. En el capítulo 2, consideramos los códigos de dominio ordenado, estos generalizan a los códigos AG unipuntuales. Un dominio ordenado es un $\F_q$-álgebra $R$ junto con una función peso $v$ sobre $R$. Un código de dominio ordenado $C(\Phi,m)$ es definido como la imagen del subespacio vectorial $L(m)$, de los elementos en $R$ con peso a lo sumo un entero $m$, por un morfismo de $\F_q$-álgebras, $\Phi:R\rightarrow\fq^n$. Puesto que el espacio $L(m)$ está relacionado con el semigrupo asociado a la función peso $v$, estudiamos algunas propiedades sobre semigrupos numéricos, en particular para los semigrupos generados por dos elementos y los semigrupos telescópicos. Introducimos los conceptos de oasis y desiertos de un semigrupo numérico y en el caso de semigrupos generados por dos elementos consecutivos los caracterizamos explícitamente. Consideramos la cadena de códigos $(0)\subseteq C(\Phi,0)\subseteq C(\Phi,1)\subseteq\cdots$ y definimos el conjunto de dimensiones $M$ de ésta cadena, formado por los enteros no negativos en los cuales la cadena aumenta su dimensión. Con estas herramientas obtenemos una nueva versión de las cotas de orden para los códigos de dominio ordenado, que solo depende de $M$. Como casos especiales, estudiamos el conjunto de dimensiones y la cota de orden para los códigos AG unipuntuales y en particular para la familia especial de códigos Castillo. Finalizamos con una técnica de mejora de los códigos de dominio ordenado. En el capítulo 3, caracterizamos la cota de orden sobre la distancia mínima de los códigos Castillo. Calculamos explícitamente esta cota para los códigos Castillo que tienen semigrupo de Weierstrass generado por dos elementos consecutivos. En especial se obtiene que la cota orden coincide con el verdadero valor de la distancia mínima de los códigos Hermitianos, dada por Kyeongcheol Yang y P. Vijay Kumar en [62]. La nueva caracterización de la distancia mínima de los códigos Hermitianos, dada por la cota de orden, es más simple que las conocidas hasta el momento, ver [30,62]. Estos resultados fueron publicados en [51]. En el caso general de semigrupos generados por dos elementos cualesquiera, obtenemos igualmente el cálculo completo de la cota de orden de todos estos códigos Castillo. También obtenemos resultados similares pero incompletos, para el caso de códigos Castillo con semigrupo telescópico. Finalmente calculamos explícitamente la cota de orden para todos los códigos de Suzuki. Estos resultados fueron publicados en [53]. El capítulo 4, trata sobre los pesos de Hamming generalizados de códigos Castillo. Se pueden distinguir dos partes. En la primera parte (Sección 4.1) caracterizamos la cota de orden solo para el segundo peso de Hamming de códigos Castillo. Calculamos explícitamente esta cota para un gran número de códigos Castillo con semigrupo de Weierstrass generado por dos elementos cualesquiera. Para semigrupos generados por dos elementos consecutivos la cota es calculada completamente. Como consecuencia obtenemos una nueva caracterización del verdadero valor del segundo peso de Hamming de códigos Hermitianos, calculados por Angela Barbero y Carlos Munuera en [2]. Estos resultados fueron publicados en [52]. En la segunda parte de este capítulo (Sección 4.2) introducimos los subconjuntos del conjunto $M$ cuyos elementos se comportan regular y fatal para cada $i=1,\dots,n$. Estos conjuntos, junto con el subconjunto de elementos de $M$ que se comportan {\em bien}, forman una partición de $M$. Como resultado principal de esta sección obtenemos un intervalo en el que los códigos Castillo son $r$-ésimos MDS. En consecuencia, obtenemos una nueva cota inferior $d_w$ sobre la distancia mínima de códigos Castillo. En los ejemplos trabajados, esta cota es tan buena como la cota de orden, si bien no hemos podido encontrar relación entre ellas. Finalmente mostramos que el primer entero $w_i+1$ para el cuál los códigos Hermitianos son $(w_i+1)$-ésimo MDS, coincide con el verdadero valor del toque de los códigos Hermitianos (este es el primer elemento que satisface la igualdad en la cota singleton generalizada). Por tanto, obtenemos por primera vez el rango MDS de todos los códigos Hermitianos. Estos resultados se recogen en [54]. Bibliografía [1] H. Andersen and O. Geil, Evaluation codes from order domain theory, Finite Fields and their Applications, 14 (2008), pp. 92--123. [2] A. Barbero, C. Munuera, The Weight Hierarchy of Hermitian Codes, SIAM Journal on Discrete Mathematics, 13 (2000), pp. 79--104. [3] P. Beelen, The order bound for general algebraic geometric codes, Finite Fields and Application, 13 (2007), pp. 665--680. [4] P. Beelen and T. H\o holdt, The decoding of algebraic geometry codes. In E. Martínez-Moro, C. Munuera, D. Ruano (Eds.), Advances in algebraic geometry codes, World Scientific, Singapore, 2008, pp. 49--98. [5] E.R. Berlekamp, R.J. McEliece and H. van Tilborg, On the Inherent Intractability of Certain Coding Problems, IEEE Transactions on Information Theory, 24(3) (1978), pp. 384--386. [6] S. V. Bulygin, Generalized Hermitian codes over $GF(2^r)$, IEEE Transactions on Information Theory, 52 (2006), pp. 4664--4669. [7] C. Carvalho and Fernando Torres, On Goppa codes and Weierstrass gaps at several points, Designs, Codes and Cryptography, 35 (2005), pp. 211--225. [8] I.M. Duursma, Majority coset decoding, IEEE Transactions on Information Theory, 39 (1993), pp. 1067--1071. [9] I. Duursma and R. Kirov, An extension of the order bound for AG codes. In Applied Algebra, Algebraic algorithms and error-correcting codes, pp. 11-22, LNCS 5527, Springer, 2009. [10] I. Duursma, R. Kirov and S. Park, Distance bounds for algebraic geometric codes, J. Pure and Applied Algebra, 215 (2011), pp. 1863--1878. [11] G.L. Feng and T.R.N. Rao, Decoding of algebraic geometric codes up to the designed minimum distance, IEEE Trans. on Information Theory, 39 (1993), pp. 37--45. [12] G.L. Feng and T.N.T. Rao, Improved geometric Goppa codes. Part I: Basic Theory, IEEE Transactions on Information Theory, 41 (1995), pp. 1678--1693. [13] J. Fitzgerald and R.F. Lax, Decoding affine variety codes using Gröbner basis, Designs, Codes and Cryptography, 13(2) (1998), pp. 147--158. [14] W. Fulton, Algebraic Curves. Benjamin, New York, 1969. [15] R. Fuhrmann and F. Torres, On Weierstrass points and optimal curves, Suplemento ai Rendiconti del Circolo Matematico di Palermo, 51 (1998), pp. 25--46. [16] A. Garcia and H. Stichtenoth, A class of polynomials over finite fields, Finite Fields and Applications, 5 (1999), pp. 424--435. [17] O. Geil, On codes from norm-trace curves, Finite Fields and Their Applications, 9(3) (2003), pp. 351--371. [18] O. Geil, Evaluation codes from an affine variety code perspective. In E. Mart\'{\i}nez-Moro, C. Munuera, D. Ruano (Eds.), Advances in algebraic geometry codes, World Scientific, Singapore, 2008, pp. 153--180. [19] O. Geil and R. Matsumoto, Bounding the number of $\F_q$-rational places in algebraic function fields using Weierstrass semigroups, J. Pure and Applied Algebra, 213(6) (2009), pp. 1152--1156. [20] O. Geil, R. Matsumoto and D. Ruano, Feng-Rao decoding of primary codes, Finite Fields and their Applications, 23 (2013), pp. 35--52. [21] O. Geil, C. Munuera, D. Ruano and F. Torres, On the order bounds for one-point AG codes, Advances in Mathematics of Communications, 3 (2011), pp. 489--504. [22] V.D. Goppa, Codes Associated with Divisors, Problemy Peredachi Informatsii, 13(1) (1977), pp. 33--39. [23] V.D. Goppa, Algebraico-Geometric Codes, Mathematics of the USSR-Izvestiya, 21 (1983), pp. 75--91. [24] J.P. Hansen, Codes on the Klein Quartic, Ideals and Decoding, IEEE Transactions on Information Theory, 33(6) (1987), pp. 923--925. [25] J.P.Hansen, Deligne Lusztig varieties and group codes, Lecture Notes in Mathematics, 1518 (1992), pp. 63--81. [26] J.P. Hansen and J.P. Petersen, Automorphism of Ree type, Deligne Lasztig and function fields. J. Reine Angew Math., 440 (1993) pp. 99--109. [27] J. P. Hansen and H. Stichtenoth, Group codes on certain algebraic curves with many rational points, Applicable Algebra in Engineering, Communication and Computing, 1 (1990), pp. 67--77. [28] P. Heijnen and R. Pellikaan, Generalized Hamming weights of $q$-ary Reed-Muller codes. IEEE Transactions on Information Theory, 44(1) (1998) 181--196. [29] T. Helleseth, T. Klove and J. Mykkeleveit, The weight distribution of irreducible cyclic codes with block lengths $n((q^l-1)/N)$, Discrete Math., 18 (1977), pp. 179-211. [30] T. Hoholdt, J.H. van Lint and R. Pellikaan, Algebraic-Geometry codes. In V.S. Pless and W.C. Huffman (Eds.), Handbook of Coding Theory, vol. 1, Elsevier, Amsterdam, 1998. http://www.tue.nl/$\sim$ruudp/paper/31.pdf [31] M. Homma and S. J. Kim, \textit{Goppa codes with Weierstrass pairs}, J. Pure and Applied Algebra, 162 (2001), pp. 273--290. [32] C. Kirfel and R. Pellikaan, The minimum distance of codes in an array coming from telescopic semigroups. IEEE Transactions on Information Theory, 41 (1995), pp. 1720--1731. [33] J. Lewittes, Places of degree one in function fields over finite fields, J. Pure and Applied Algebra, 69 (1990), pp. 177-183--1156. [34] J.H. van Lint, Introduction to coding theory, second edition, Springer-Verlag, 1992. [35] J.H. van Lint and G. van der Geer, Introduction to coding Theory and Algebraic Geometry, Birkhauser, Verlag Basel, 1988. [36] F.J. MacWilliams and N. Sloane, The theory of error-correcting codes. North-Holland, Amsterdam, 1977. [37] G.L. Matthews, Weierstrass pairs and minimum distance of Goppa codes, Designs, Codes and Cryptography, 22 (2001), pp. 107--121. [38] G.L. Matthews, Codes from the Suzuki Function Field, IEEE Transactions on Information Theory, 50(12) (2004), pp. 3298--3302. [39] G.L. Matthews and T. Michel, One-point codes using places of higher degree, IEEE Transactions on Information Theory, 51 (2005), pp. 1590--1593. [40] MinT., Online database for optimal parameters of $(t, m, s)$-nets, $(t, s)$-sequences, orthogonal arrays, linear codes, and OOAs. Available at http://mint.sbg.ac.at/ [41] R. Matsumoto and S. Miura, On the Feng-Rao bound for the L-construction of Algebraic-Geometry codes. IEICE Trans. on Fundamentals, 5 (2000), pp. 923--927. [42] C. Munuera, On the generalized Hamming weights of geometric Goppa codes, IEEE Transactions on Information Theory, 40(6) (1994), pp. 2092--2099. [43] C. Munuera and W. Olaya-León, An introduction to Algebraic Geometry codes. Aparecerá en: Algebra and Geometry for Reliable Communications, Contemporary Mathematics AMS (2014). [44] C. Munuera and J. Tena, Codificación de la información, Pub. Universidad de Valladolid, 1997. [45] C. Munuera and R. Pellikaan, Equality of geometric Goppa codes and equivalence of divisors, Journal of Pure and Applied Algebra, 90 (1993), pp. 229--252. [46] C. Munuera and F. Torres, Bounding the trellis state complexity of algebraic geometric codes, Applicable Algebra in Engineering, Communication and Computing, 15 (2004), pp. 81--100. [47] C. Munuera, A. Sepúlveda and F. Torres, Algebraic Geometry codes from Castle curves, In Coding Theory and Applications, Springer-Verlag, Berlin, LNCS 5228 (2008), pp. 117--127. [48] C. Munuera, A. Sep\'ulveda and F. Torres, Castle curves and codes, Advances in Mathematics of Communication, 3 (2009), pp. 399--408. [49] C. Munuera, A. Sep\'ulveda and F. Torres, Generalized Hermitian codes, Designs, Codes and Cryptography, 69 (2013), pp. 123--130. [50] C. Munuera, G. Tizziotti and F. Torres, Two-point codes on Norm-Trace curves. In Coding Theory and Applications, Springer-Verlag, Berlin, LNCS 5228 (2008) pp. 128--136. [51] W. Olaya-Le\'on and C. Granados-Pinzón, Sobre la distancia mínima de códigos AG unipuntuales Castillo, Revista Ingenieria y Ciencia, 8(16) (2012), pp. 239--255. [52] W. Olaya-Le\'on and C. Granados-Pinzón, The second generalized Hamming weight of certain Castle codes. Aparecerá en: Designs, codes and cryptography, (2014). DOI: 10.1007/s10623-014-9981-1. [53] W. Olaya-Le\'on and C. Munuera, On the minimum distance of Castle codes, Finite Fields and Applications, 20 (2013), pp. 55--63. [54] W. Olaya-Le\'on and C. Munuera, On the generalized Hamming Weights of Castle codes, Preprint (2014). [55] R. Pellikaan, On special divisors and the two variable zeta function of algebraic curves over finite fields. In Arithmetic, geometry and coding theory, de Gruyter, Berlin, (1996) pp. 175--184. [56] J. C. Rosales and P.A. García-Sánchez, Numerical semigroups. Vol. 20 of Developments in mathematics, Springer, New York, 2009. [57] C.E. Shannon, A Mathematical Theory of Comunication, Bell Systems Technical J., 27 (1947), pp. 656--715. [58] T. Shibuya and K. Sakaniwa, A dual of well-behaving type designed minimum distance, IEICE Transactions Fundamentals, E84-A(2) (2001), pp. 647--652. [59] H. Stichtenoth, A note on Hermitian codes over $\mathbb{F}_{q^2}$, IEEE Transactions on Information Theory, 34(5) (1988), pp. 1346--1348. [60] H. Stichtenoth, Algebraic Functions Fields and Codes. Springer-Verlag, Berlin, 1993. [61] M.A. Tsfasman, S.G. Vladuts and T. Zink, Modular curves, Shimura curves and Goppa codes better than Varshamov-Gilbert bound, Mathematische Nachrichten, 109 (1982), pp. 21--28. [62] K. Yang and P.V. Kumar, On the true minimum distances of Hermitian codes. In Coding Theory and Algebraic Geometry, LNCS 1518, pp. 99-107, Springer-Verlag, Berlin, 1992. [63] V.K. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37(5) (1991) pp. 1412--1418.