Espectro de códigos cíclicos y grafos asociados

Abstract

Una de las clases más importante e implementada de códigos, es la clase de los códigos cíclicos, debido a su eficiente codificación, y por la existencia de buenos algoritmos para decodificarlos. Por otro lado, entender la distribución de pesos de códigos permite en algunos casos, calcular el error de probabilidad a la hora de decodificar. Por ello, es importante conocer la distribución de pesos de códigos cíclicos. En general, el problema de calcular distribuciones de pesos es computacionalmente complejo, inclusive en el caso de códigos cíclicos. Sin embargo, es posible atacar este problema si pedimos ciertas condiciones al código cíclico.Esta tesis se centra en el estudio del espectro o distribución de pesos de códigos cíclicos, y de las distintas relaciones que tienen estos espectros con otros objetos que aparecen en el estudio de cuerpos finitos tales como sumas exponenciales, caracteres, curvas algebraicas y grafos de Cayley.Específicamente, en primer lugar estudiaremos formas cuadráticas sobre cuerpos finitos. Veremos sus principales propiedades e invariantes, la simplicidad del estudio de las formas cuadráticas en cuerpos finitos están caracterizadas (salvo equivalencia) e inclusive en algunos casos hay invariantes absolutos. Luego, veremos algunas sumas exponenciales definidas a partir de formas cuadráticas que ser´an de importancia a la hora del cálculo del espectros de ciertos códigos cíclicos, veremos que tanto la evaluación de estas sumas como su distribución sólo dependen de invariantes de la forma cuadrática.En segundo lugar, veremos que los pesos de una palabra de códigos definidos a partir de formas cuadráticas están relacionados directamente por una ecuación con las sumas exponenciales anteriormente definidas, reduciendo el cálculo de distribución de pesos al cálculo de distribución de invariantes de formas cuadráticas variando en una cierta familia parametrizada. Veremos que no sólo se obtiene el espectro de un sólo código, sino que también de algunos otros asociados a este.En tercer lugar, interpretaremos los resultados obtenidos sobre estos códigos en distintos ambitos. Por un lado, veremos que en el caso binario el código dual de una de los códigos resulta ser optimal en el sentido que su distancia es la mayor posible, esto permite relacionar el cero elegido del código cíclico con cierta clase especial de función booleana. También veremos que los pesos de las palabras de una de las familias están relacionadas directamente con la cantidad de puntos racionales de una curva algebraica de tipo Artin-Schreier. En algunos casos, encontraremos curvas maximales en el sentido de Hasse-Weil.Finalmente, construiremos distintas clases de grafos de Ramanujan no bipartitos. En un principio usaremos una forma cuadrática para calcular el espectro de cierto grafo de Cayley, veremos que dicho grafo resulta ser Ramanujan si nos restringimos a los casos binario y ternario. En el caso binario, usando el hecho de la optimalidad del dual del código C1, veremos que es posible extender la construcción de grafos de Ramanujan para diferentes tipos de funciones Booleanas especiales (APN, AB y PN). En el caso de características superiores también construiremos otros grafos de Ramanujan con ideas similares a las anteriores usando en este caso funciones planares.