Nonlinear codesrepresentation, constructions, minimum distance computation and decoding

Abstract

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.