Códigos grupo no abelianos/non-abelian group codes

• Autores: Cristina García Pillado
• Directores de la Tesis: Consuelo Martínez López (dir. tes.)
• Lectura: En la Universidad de Oviedo ( España ) en 2015
• Idioma: español
• Tribunal Calificador de la Tesis: Llorenç Huguet Rotger (presid.) , Ignacio Fernández Rúa (secret.) , Massimiliano Sala (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • El tratamiento matemático de la teoría de la información data de 1948. En el trabajo de Shannon `A mathematical theory of communications¿ se estudia por primera vez desde este punto de vista el problema de transmitir de un mensaje a través de un canal de comunicación. Ligados a él surgen varios: la confidencialidad de los mensajes, la eficacia de la transmisión (tratando de ocupar el canal el menor tiempo posible) y la fidelidad de la información, del que se ocupa la teoría de códigos correctores de errores, campo en el que se enmarca esta tesis.

    Para detectar y corregir posibles alteraciones de los mensajes, se codifica la información usando un alfabeto usualmente binario. Ligados al código (C) aparecen los parámetros longitud (n) y eficiencia (c) o dimensión combinatoria (k). El receptor al descodificar la información puede detectar y corregir errores, siempre dentro de la capacidad correctora de C. Esta capacidad está ligada a d, la distancia de Hamming de C. Así, hablamos de un (n,c,d) o (n,k,d)-código.

    El objetivo es encontrar un equilibrio entre k,d y n, de forma que k y d sean grandes y n no crezca demasiado, para evitar un uso prolongado del canal. En efecto, la cota de Singleton nos dice que n es mayor o igual que k+d-1.

    En general, se utilizarán códigos lineales, en cuyo caso el alfabeto es un cuerpo finito F_q y C es un subespacio vectorial de F_q^n .

    El objetivo de esta tesis doctoral es el estudio de códigos grupo, extensión natural de los códigos cíclicos. Si G es un grupo finito, F un cuerpo finito e I un ideal del anillo de grupo F_q G, un código C(I) de longitud n por está formado por las n-tuplas (a_0, a_1,...a_{n-1}) tales que el elemento a_0g+a_1g_1+...+a_{n-1}g_{n-1} pertenece al ideal.

    Identificaremos I y C(I). Dos códigos son equivalentes por permutación si existe una permutación que transforma uno en el otro. El grupo de automorfismos permutación PAut(C) es el grupo de las permutaciones que transforman palabras del código en palabras del código. Dado un grupo G, un G-código (a izquierda) es un código equivalente por permutación a un ideal (a izquierda) de FG. Es sabido que existen códigos grupo a izquierda no abelianos, pero no se conocía si el resultado es cierto para códigos grupo.

    Existe una caracterización intrínseca de códigos grupo que utiliza PAut(C), de interés teórico, pero de difícil aplicación práctica por la dificultad que supone el cálculo de PAut(C) en muchos casos. Si un grupo G es descomponible (G=AB, con A y B subgrupos abelianos) todo G-código es abeliano. En este contexto de códigos grupo que no sean abelianos se enmarca la presente tesis.

    Probamos que la propiedad de que todo G-código sobre un cuerpo F sea abeliano se conserva al considerar un sub-cuerpo E de F y establecemos las condiciones bajo las que sigue siendo cierta para una extensión de F. Probamos que todo grupo de orden menor que 24 o p^4 (p primo) es descomponible, pero S_4 no lo es y, si p es impar, existe un grupo de orden p^5 que tampoco lo es. Todo grupo de orden 32 es descomponible pero existen varios de orden 64 que no lo son.

    Se construyen, con ayuda del ordenador, códigos no abelianos en Z_3S_4 , Z_2 S_4 y Z_5 S_4 (su distribución de pesos no coincide con la de ningún código abeliano de longitud 24 y su misma dimensión). Estos códigos tienen peores parámetros que los abelianos. Usando SL(2,3) hemos podido construir, sin la necesidad de ordenador, un código no abeliano de dimensión 6 óptimo en el sentido de que alcanza la cota superior de la distancia mínima (10) de cualquier código binario lineal de su misma longitud y dimensión.

    También se recogen resultados sobre descodificación. En concreto, se construye un algoritmo que permite corregir un error, basado en la descodificación por síndrome.

    The mathematical treatment of the information theory dates from 1948. In the paper `A mathematical theory of communications¿ by Shannon, the transmission problem of a message through a communication channel is mathematically studied for the first time. Several related problems arise: the confidentiality of the messages, the efficiency in the transmission (trying to use the channel the shortest possible time) and the reliability of the received information. The theory of error correcting codes deals with this problem and this is the area that this thesis belongs to.

    To detect and correct possible alterations of the messages, the information is codified using an alphabet which is usually binary. Linked to the code (C) are the parameters length (n) and efficiency (c) or combinatorial dimension (k). The receiver, in the decoding process, can detect and correct errors, provided their number stays under the capacity of the code. This capacity is linked to d, the Hamming distance of C. So we say C is an (n,c,d) or an (n,k,d)-code.

    The aim is to find an equilibrium between k,d and n, in such a way that k and d are large and n is not too large to avoid using the channel for a long period of time. Indeed, the Singleton bound states n is greater than or equal to k+d-1.

    In general, we will use linear codes, for which the alphabet is a finite field F_q and C is a subspace of the vector space F_q^n .

    In this thesis we study group codes, a natural extension of cyclic codes. If F is a finite field, G is a finite group and I an ideal of the group ring F_q G, a code C(I) of length n consists of the n-tuples (a_0, a_1,...a_{n-1}) such that a_0g+a_1g_1+...+a_{n-1}g_{n-1} is an element of I.

    We will identify I and C(I). Two codes are permutation equivalent if there exists a permutation that transforms one code into the other one. The group of permutation automorphisms PAut(C) is the group of permutations that transform words of the code into words of the code. Given a group G, a (left) G-code is a code which is permutation equivalent to a (left) ideal of FG. It is known that there exist left group codes which are not abelian but the same result for group codes was unknown.

    There is an intrinsic characterisation using PAut(C). In spite of its theoretical interest, the result is not very useful in practice, since it is very difficult to find PAut(C) in most cases. If a group G is decomposable (G=AB, where A and B abelian subgroups) every G-code is abelian. In this context of non-abelian group codes we can include this thesis.

    We prove that the property that every G-code over a field F is abelian is kept when we consider any subfield E of F and we find some conditions that guarantee the same property for an extension of F. We prove that any group of order 24 or p^4 (p prime) is decomposable, but S_4 is not and, if p is odd, there exists a group of order p^5 which is not. Every group of order 32 is decomposable but there exist several groups of order 64 that are not.

    We have constructed non-abelian codes in Z_3S_4 , Z_2 S_4 and Z_5 S_4 ( using computer we could check that their weight distribution does not coincide with the weight distribution of any abelian code of length 24 and same dimension). The parameters of these non-abelian codes are worse than those of abelian codes of the same length. Considering the group SL(2,3), we could construct a non-abelian code of dimension 6 that is optimal in the sense that it achieves the upper bound of the minimum distance for binary linear codes of the same length and dimension. The proof of those facts does not require the use of a computer.

    Finally we include some results on decodification. Concretely, we present an algorithm to correct one error, based on decodification by syndrome, reducing the problem to the search of a solution of minimum Hamming weight in a key equation.