Cálculo de la distancia aparente de códigos abelianoscódigos BCH multivariables

Zusammenfassung

RESUMEN El objetivo principal de este trabajo es el estudio del cálculo de la distancia aparente de un código abeliano, la cual es una cota para su distancia mínima. Asimismo, también son objeto de este trabajo el desarrollo de la noción de cota BCH y código BCH multivariable, de las construcciones multivariables y las aplicaciones a los códigos cíclicos que se desprenden de dichas nociones. Un primer problema concreto que abordamos en esta tesis es determinar cuándo en un código cíclico la mayor de sus cotas BCH coincide con su distancia mínima. En este sentido hemos encontrado condiciones en términos de los divisores del polinomio xr-1 en ciertas extensiones del cuerpo base de los códigos que consideramos en este trabajo. Es más, a partir de estos resultados mostramos un método de construcción de códigos para los cuales el máximo de sus cotas BCH y su distancia mínima coinciden. En 1970, P. Camion [1] extendió el estudio de la cota BCH a la familia de los códigos abelianos al introducir la noción de distancia aparente de un código abeliano. En el caso de los códigos cíclicos, la distancia aparente y la (máxima) cota BCH del código, coinciden. La distancia aparente de un código abeliano en un anillo semisimple es el mínimo de la distancia aparente de ciertos polinomios que corresponden con la transformada de Fourier discreta de los elementos de todos los subconjuntos del conjunto de idempotentes que pertenecen al código. Esto implica que el cálculo es de orden exponencial. Así, en la práctica, el número de operaciones requeridas es muy elevado, por lo que es pertinente plantearse la búsqueda de un método alternativo que simplifique el original. En [2], R. E. Sabin realizó la primera reducción de los cálculos para obtener la distancia aparente de un polinomio fijo usando ciertas manipulaciones de matrices en el contexto de los llamados "2-D cyclic codes" (códigos abelianos en dos variables). Aún cuando el método de Sabin simplifica el original, no ayuda en nada a reducir el número de cálculos necesarios en el cómputo de la distancia aparente de un código. Así que el problema de la complejidad siguió abierto. En el trabajo de Camion antes mencionado, puede comprobarse que la distancia aparente de un código cíclico es precisamente la distancia aparente de un polinomio asociado al idempotente generador del código (concretamente, la transformada de Fourier). Hay ejemplos que muestran que, en el caso multivariable, dicha igualdad no se verifica, así que es natural preguntarse si en ese caso puede obtenerse la distancia aparente a partir de ciertas manipulaciones sobre dicho polinomio o específicamente sobre la hipermatriz (de coeficientes) asociada a la imagen bajo la transformada de Fourier del idempotente generador, respecto de ciertas raíces de la unidad prefijadas. Éste es el objetivo principal alcanzado en este trabajo: presentar un algoritmo para calcular la distancia aparente de un código abeliano basándose en el manejo de hipermatrices, de tal forma que la cantidad de operaciones involucradas se reduzca notablemente. De hecho, en el caso caso de dos variables se reduce hasta el orden lineal. Una vez que el algoritmo ha sido desarrollado, el siguiente paso natural ha sido presentar una noción de código BCH multivariable que nos ha permitido extender muchos de los resultados clásicos sobre códigos BCH cíclicos. Además, hemos encontrado aplicaciones de nuestras técnicas en la construcción de códigos abelianos con distancia aparente predeterminada. REFERENCIAS [1] P. Camion, Abelian Codes, MRC Tech. Sum. Rep. \# 1059, University of Wisconsin, 1971. [2] R. Evans Sabin, On Minimum Distance Bounds for Abelian Codes, Applicable Algebra in Engineering Communication and Computing, Springer-Verlag, 1992. ABSTRACT The main goal of this work is the study of the computation of the apparent distance of an abelian code, which is a bound for its minimum distance. Other contribution of this work is the development of a notion of multivariate BCH bound and multivariate BCH code. We also present a way to construct these type of multivariate codes and some applications to cyclic codes which are derived from the mentioned notions. First, we deal with the problem of determining when the maximum of the BCH bounds of a cyclic code equals its minimum distance. In this sense, we have found conditions in terms of the divisors of the polynomial xr-1 in some field extensions of the ground field of the code. Moreover, from this results we show a method of construction of codes such that the maximum of its BCH bounds coincide with its minimum distance. In 1970, P. Camion [1] extended the study of the BCH bound to the family of abelian codes by introducing the notion of apparent distance of an abelian code. For any cyclic code, its apparent distance is equal to the maximum of its BCH bounds. The apparent distance of an abelian code, in a semisimple ring, is the minimum of the apparent distances of certain polynomials. These polynomials correspond to the discrete Fourier transform of the elements of all subsets in the set of the idempotents in the code. This implies that the computation has exponential order. Consequently, it is pertinent to consider the search of an alternative method which simplifies the original one. In [2], R. E. Sabin made the first reduction of the computations required to obtain the apparent distance of a fixed polynomial by using some matrix manipulations. Her work is applied to "2-D cyclic codes" (abelian codes in two variables). Even though Sabin's method simplifies the original one, it does not reduce the number of computations needed to get the apparent distance of a code. So, the problem of complexity is still open. In the mentioned paper of Camion, one may see that the apparent distance of a cyclic code equals the apparent distance of a polynomial associated to the idempotent generator of the code (specifically, its discrete Fourier transform). There are examples which show that in the multivariate case the equality does not hold. Therefore, it is natural to wonder whether it is possible to obtain the apparent distance of a multivariate code from some manipulations on the (coefficients) hypermatrix associated to the discrete Fourier transform of its idempotent generator, with respect to certain fixed roots of unity. This is the most important goal that we have reached in this work: to present an algorithm to compute the apparent distance of an abelian code, based on manipulations on hypermatrices, in such a way that the involved number of computations is reduced significantly. In fact, in the two variables case it is reduced to the linear order. Once the algorithm has been developed, the next natural step has been to present a notion of multivariate BCH code. This concept has allowed us to extend many of the classical results about cyclic BCH codes. Moreover, we have found applications of our techniques to the construction of abelian codes with a fixed apparent distance. REFERENCES [1] P. Camion, Abelian Codes, MRC Tech. Sum. Rep. \# 1059, University of Wisconsin, 1971. [2] R. Evans Sabin, On Minimum Distance Bounds for Abelian Codes, Applicable Algebra in Engineering Communication and Computing, Springer-Verlag, 1992.