Zps-Linear Codes. Generalizations and Permutation Decoding

Abstract

Els codis lineals sobre anells han despertat un gran interès en els darrers 30 anys, després de la publicació d'uns resultats que connectaven els codis lineals sobre Z4, també anomenats codis quaternaris, amb algunes famílies importants de codis binaris no lineals. Els conceptes principals que descriuen els codis quaternaris es poden generalitzar als codis lineals sobre l'anell Zps. Un codi lineal sobre l'anell Zps de longitud n és un subgrup de Zps^n, i s'anomena codi Zps-additiu. Per altra banda, un codi Zps-linear és un codi sobre Zp, no necessàriament lineal, que és alhora la imatge d'un codi Zps-additiu a través d'una generalització del Gray map.

L'estudi dels codis Zps-lineals i Zps-additius representa el tema central d'aquesta tesi doctoral. En particular, explorem el mètode de descodificació per permutacions aplicat als codis Zps-lineals, juntament amb algunes propietats necessàries per aconseguir que el mètode sigui viable i eficient. Per exemple, demostrem l'existència d'una codificació sistemàtica i donem construccions per obtenir PD-sets adients. Per obtenir bons PD-set cal conèixer l'estructura del grup d'automorfismes per permutació d'un codi, cosa que no és fàcil en general. No obstant això, algunes famílies de codis Zps-lineals presenten un grup d'automorfismes amb una estructura més simple. Hem estat capaços de descriure el grup d'automorfismes per permutació dels codis Zps-lineals que pertanyen a la família de Hadamard generalitzats, permetent-nos trobar r-PD-sets per a aquests codis.

Simultàniament, hem estat desenvolupant un paquet de Magma que proporciona noves funcionalitats per als codis Zps-lineals i Zps-additius. Els resultats obtinguts en aquesta tesi també s'han implementat com a funcions en aquest paquet, és a dir: codificació sistemática i descodificació per permutations per a qualsevol codi Zps-lineal, una computació més eficient de la matriu de control per a qualsevol codi Zps-additiu, i diverses construccions de r-PD-sets per a qualsevol codi Zps-lineal que pertanyi a la família de Hadamard generalitzats. També s'ha dedicat una atenció especial al càlcul de la distància mínima homogènia dels codis Z2Z4-additius, que són codis amb algunes coordenades sobre Z2 i altres sobre Z4.

Los códigos lineales sobre anillos han recibido mucha atención en los últimos 30 años, después de la publicación de unos resultados que relacionaban los códigos lineales sobre Z4, también llamados códigos cuaternarios, con algunas familias importantes de códigos binarios no lineales. Los conceptos principales que describen a los códigos cuaternarios se pueden generalizar a los códigos lineales sobre el anillo Zps. Un código lineal sobre Zps de longitud n es un subgrupo de Zps^n, y también se le puede llamar código Zps-aditivo. Por otra parte, un código Zps-lineal es un código sobre Zp, no necesariamente lineal, que es a su vez la imagen de un código Zps-aditivo a través de una generalización del Gray map.

El estudio de los códigos Zps-lineales y Zps-aditivos constituye el tema central de esta tesis doctoral. En particular, exploramos el método de decodificación por permutaciones aplicado a los códigos Zps-lineales, junto a algunas propiedades necesarias para conseguir que el método sea factible y eficiente. Por ejemplo, demostramos la existencia de una codificación sistemática y mostramos cómo se pueden construir unos PD-sets adecuados. Para obtener buenos PD-sets se necesita conocer la estructura del grupo de automorfismos por permutación de un código, lo que suele ser difícil en general. Sin embargo, ciertas familias de códigos Zps-lineales ofrecen una representación más manejable de este grupo. Hemos sido capaces de describir el grupo de automorfismos por permutación de los códigos Zps-lineales pertenecientes a la familia de Hadamard generalizados, lo que nos ha permitido encontrar r-PD-sets para estos códigos.

Al mismo tiempo, hemos estado desarrollando un paquete de Magma, proporcionando nuevas funcionalidades para códigos Zps-lineales y Zps-aditivos. Los resultados obtenidos en esta tesis también han sido implementados como funciones en este paquete, es decir: codificación sistemática y decodificación por permutaciones para cualquier código Zps-lineal, una computación más eficiente de la matriz de control para cualquier código Zps-aditivo, y varias construcciones de r-PD-sets para cualquier código Zps-lineal perteneciente a la familia de Hadamard generalizados. También se ha prestado especial atención al cálculo de la distancia mínima homogénea de los códigos Z2Z4-aditivos, que son códigos con algunas coordenadas sobre Z2 y otras sobre Z4.

Linear codes over rings have gained much attention over the last 30 years following some results that connected linear codes over Z4, also called quaternary codes, with some important families of nonlinear binary codes. The main concepts describing quaternary codes can be generalized to linear codes over Zps. A linear code over Zps of length n is a subgroup of Zps^n, and is also called a Zps-additive code. A Zps-linear code is a code over Zp, not necessarily linear, which is the generalized Gray map image of a Zps-additive code.

The study of Zps-linear codes and Zps-additive codes constitutes the central topic of this PhD thesis. In particular, we explore the permutation decoding method for Zps-linear codes, along with some necessary properties such that it becomes feasible and efficient. That is, we prove the existence of a systematic encoding and give a construction of suitable PD-sets. Obtaining good PD-sets requires a good understanding of the permutation automorphism group of a code, which is generally a difficult task. However, certain families of Zps-linear codes offer a more manageable representation of this group. We have been able to describe the permutation automorphism group of Zps-linear generalized Hadamard codes, allowing us to find r-PD-sets for these codes.

At the same time, a Magma package has been developed, providing new functionality for Zps-linear and Zps-additive codes. The results obtained in this thesis are also implemented as functions in this package, namely: systematic encoding and permutation decoding for any Zps-linear code, a more efficient computation of a parity-check matrix for any Zps-additive code, and constructions of r-PD-sets for any Zps-linear generalized Hadamard code. Moreover, special attention is given to the computation of the minimum homogeneous distance for Z2Z4-additive codes, which are codes with some coordinates over Z2 and others over Z4.