Hadamard, quasi-Hadamard, and generalized Hadamard full propelinear codes

Abstract

Aquesta tesi pertany als camps de la combinatòria algebraica i de la teoria matemàtica de la informació. Motivada per l’avantatge computacional de l’estructura full propelinear, estudiem diferents tipus de codis correctors d’errors dotats d’aquesta estructura. Com que un codi full propelinear és també un grup, és possible generar el codi a partir de les paraules associades als generadors com a grup, fins i tot si el codi és no lineal. Això ofereix els beneficis d’emmagatzematge d’un codi lineal. Rifà i Suárez van definir els codis full propelinear sobre matrius Hadamard binàries (HFP-codis) i van provar una equivalència amb els grups Hadamard. L’existència de matrius Hadamard d’ordres múltiple de quatre segueix sent un problema obert. Per tant, l’estudi de nous codis Hadamard pot contribuir a abordar la conjectura de Hadamard. Un codi amb una estructura full propelinear està compost per dos conjunts; paraules i permutacions. Definim el grup associat d’un HFP-codi com el grup format per les permutacions. Primerament, estudiem els HFP-codis amb un grup associat fixat. El següent pas és generalitzar a cossos finits els HFP-codis binaris. Després vam provar que l’existència de codis Hadamard full propelinear generalitzats és equivalent a l’existència de conjunts de diferències relatius amb paràmetres (v,w,v,v/w). A més, construïm famílies infinites de codis Hadamard full propelinear generalitzats no lineals. Finalment, definim el concepte de codi quasi-Hadamard full propelinear. També donem una equivalència entre els grups quasi-Hadamard i els codis quasi-Hadamard full propelinear. En tots els codis estudiats, analitzem el rang i la dimensió del nucli. Dos paràmetres que proporcionen informació sobre la linealitat d’un codi i sobre la noequivalència de codis.

Esta tesis pertenece a los campos de la combinatoria algebraica y de la teoría matemática de la información. Motivada por la ventaja computacional de la estructura full propelinear, estudiamos diferentes tipos de códigos correctores de errores dotados de dicha estructura. Como un código full propelinear es también un grupo, es posible generar el código a partir de las palabras asociadas a los generadores como grupo, incluso si el código es no lineal. Esto ofrece los beneficios de almacenamiento de un código lineal. Rifà y Suárez definieron los códigos full propelinear sobre matrices Hadamard binarias (HFP-códigos) y probaron una equivalencia con los grupos Hadamard. La existencia de matrices Hadamard de órdenes múltiplo de cuatro sigue siendo un problema abierto. Por tanto, el estudio de nuevos códigos Hadamard puede contribuir a abordar la conjetura de Hadamard. Un código con una estructura full propelinear está compuesto por dos conjuntos; palabras y permutaciones. Definimos el grupo asociado de un HFP-código como el grupo formado por las permutaciones. Primeramente, estudiamos los HFP-códigos con un grupo asociado fijado. El siguiente paso es generalizar a cuerpos finitos los HFP-códigos binarios. Después probamos que la existencia de códigos Hadamard full propelinear generalizados es equivalente a la existencia de conjuntos de diferencias relativos con parámetros (v,w,v,v/w). Además, construimos familias infinitas de códigos Hadamard full propelinear generalizados no lineales. Finalmente, definimos el concepto de código quasi-Hadamard full propelinear. También damos una equivalencia entre los grupos quasi-Hadamard y los códigos quasi-Hadamard full propelinear. En todos los códigos estudiados, analizamos el rango y la dimensión del núcleo. Dos parámetros que proporcionan información sobre la linealidad de un código y sobre la no equivalencia de códigos.

This thesis belongs to the fields of algebraic combinatorics and mathematical information theory. Motivated by the computational advantage of the full propelinear structure, we study different kinds of error-correcting codes endowed with this structure. Since a full propelinear code is also a group, it is possible to generate the code from the codewords associated to the generators as a group, even if the code is nonlinear. This offers the data storage benefits of a linear code. Rifà and Suárez introduced full propelinear codes based on binary Hadamard matrices (HFP-codes) and they proved an equivalence with Hadamard groups. The existence of Hadamard matrices of orders a multiple of four remains an open problem. Therefore, the study of new Hadamard codes may contribute to address the Hadamard conjecture. A code with a full propelinear structure is composed of two sets, i.e., codewords and permutations. We define the associated group of an HFP-code as the group comprised of the permutations. Firstly, we study the HFP-codes with a fixed associated group. The next step is to generalize the binary HFP-codes to finite fields. Subsequently, we prove that the existence of generalized Hadamard full propelinear codes is equivalent to the existence of central relative (v,w,v,v/w)-difference sets. Furthermore, we build infinite families of nonlinear generalized Hadamard full propelinear codes. Finally, we introduce the concept of quasi-Hadamard full propelinear code. We also give an equivalence between quasi-Hadamard groups and quasi-Hadamard full propelinear codes. In all codes studied, we analyze the rank and the dimension of the kernel. Two parameters that provide information about the linearity of a code, and also about the nonequivalence of codes.