Nonlinear codes: representation, constructions, minimum distance computation and decoding

Resum La teoria de codis estudia el disseny de codis correctors d'errors per a la transmisió fidedigne d'informació per un canal amb soroll. Un codi corrector d'errors (o simplement codi) es un proces que consisteix en expressar una seqüència d'elements sobre un alfabet de tal manera que qualsevol error que sigui introduït pot ser detactat i corregit (amb limitacions), i està basat en la tècnica d'afegir elements redundants. Aquest proces inclou la codifcació, la transmisió i la descodifcació de la seqüència d'elements. La majoria dels codis utilitzat són codis bloc i la majoria d'ells tenen una estructura lineal, que facilita el procés de codifcació i descodifcació. En aquesta memòria, estudiarem codis correctors d'errors no lineals. Mal¬grat els codis no lineals no tenen les mateixes bones propietats per codifcar i descodifcar com els lineals, el codis no lineals tenen interes ates que alguns dels millors codis no son lineals. La primera qüestió que apareix quan s'utilitzen codis no lineals és la seva representació. Els codis lineals poden ser representats utilitzant una matriu generadora o una matriu de control. La millor manera de representar un codi no lineal és utilitzar la representacio kernel/caset, que permet represen¬tar un codi mitjan ant unes quantes paraules-codi representatives del codi en lloc de totes les paraules-codi. En aquesta memòria, s'estudia aquesta representació i es proposen algorismes efcients per calcular el kernel i els representants dels casets a partir de la llista de totes les paraules-codi. A més, s'utilitza aquesta representació per estudiar algunes propietats com la igualtat, inclusió, intersecció i unió de codis no lineals. També són analitzades algunes construccions ben conegudes (codi estès, codi punctured,...) manipulant directament el kernel i els representants dels casets dels codis no lineals que en formen part. Per identifcar un codi (lineal o no lineal), els paràmetres més importants són la longitud n, el nombre de paraules-codi M i la distància mínima d. La longitud n i la mida M són comparativament fàcils de calcular. Però, calcular la distància mínima d'un codi no és tant fàcil. De fet, s'ha demostrat que és un problema NP-hard [37]. No obstant, alguns algorismes han estat desenvolupats per calcular la distància mínima dels codis lineals utilitzant diversos mètodes: bases de Gröbner [7], arbres [25], algorismes probabilístics [13, 23] i enumeració de vectors [39]. Però, per als codis no lineals, excepte per a algunes famílies, no s'han desenvolupat algorismes generals per calcular la distància mínima. Utilitzant la representació kernel/caset i l'algorisme Brouwer-Zimmermann per calcular la distància mínima dels codis lineals, s'han descrit nous algorismes per calcular la distància mínima dels codis no lineals. El problema més costós en el procés de transmisió de la informació és la descodifcació. Per als codis lineals, la descodifcació via síndrome és el mètode més general. No obstant, no existeix un algorisme de descodifcacio general per a codis no lineals. Basats en la representació kernel/caset i en el càlcul de la distància mínima, es proposen nous algorismes per descodifcar codis lineals i no lineals. Per a alguns codis lineals (codis amb una codimensió gran) els algorismes proposats tenen un comportament millor que la descodifcació via sindrome. Per als codis no lineals, es el primer metode general de descodifcacio proposat comparable amb la descodifcacio via sindrome per a codis lineals. Finalment, la majoria d'aquests algorismes han estat avaluats usant el sistema MAGMA i s'ha desenvolupat un nou modul de MAGMA basat en els resultats d'aquesta tesis.Coding theory deals with the design of error-correcting codes for the reliable transmission of information across noisy channels. An error-correcting code (or code) is a process, which consists on expressing a sequence of elements over an alphabet in such a way that any introduced error can be detected and corrected (with limitation), and it is based on adding redundancy elements. This process includes encoding, transmitting and decoding the sequence of elements. Most of the used codes are block codes and most of them have a linear structure, which facilitates the process of encoding and decoding. In this dissertation, nonlinear error-correcting codes are studied. Despite non¬linear codes do not have the same good properties for encoding and decoding as linear ones, they have interest because some of best codes are nonlinear. The frst question that arises when we use nonlinear codes is their repre-sentation. Linear codes can be represented by using a generator or parity¬check matrix. The best way to represent a nonlinear code is by using the kernel/coset representation, which allows us to represent it through some representative codewords instead of all codewords. In this dissertation, this representation is studied and efcient algorithms to compute the kernel and coset representatives from the list of codewords are given. In addition, prop¬erties such as equality, inclusion, intersection and union between nonlinear codes are given in terms of this representation. Also, some well known code constructions (extended, punctured,...) are described by manipulating directly the kernel and coset representatives ofthe constituent nonlinearcodes. In order to identify a code (linear or nonlinear), the length n, number of codewords M and minimum distance d are the most important parameters. The length n and size M are comparatively easy to compute. On the other hand, to determine the minimum distance of a code is not so easy. As a matter offact, it has been proven to be an NP-hard problem [37]. However, some algorithms have been developed to compute the minimum distance for linear codes using diferent approaches: Grabner bases [7], tree structure [25], probabilistic algorithms [13, 23] and vector enumeration [39]. For nonlinear codes, except for some special families, no general algorithms have been developed to compute their minimum distance. Using the kernel/coset representation and the Brouwer-Zimmermann's algorithm to compute the minimum dis¬tance for linear codes, new algorithms to compute the minimum distance for nonlinear codes are described. The hardest problem in the process of transmitting information is de¬coding. For linear codes, a general decoding algorithm is the syndrome de¬coding. However, there is not any general decoding method for nonlinear codes. Based on the kernel/coset representation and the minimum distance computation, new general algorithms to decode linear and nonlinear codes are proposed. For some linear codes (codes with a big codimension), the proposed algorithms have better performance than the syndrome decoding algorithm. For nonlinear codes, this is the frst general method for decoding, which is comparable to syndrome decoding for linear ones. Finally, most of these algorithms have been evaluated using the MAGMA software, and a new MAGMA package to deal with binary nonlinear codes has been developed, based in the results given in this dissertation