Partial permutation decoding for Z4-linear hadamard and kerdock codes

Abstract

El problema més difícil en el procés de transmetre informació és la descodificació. Una de les àrees més importants d'investigació dins de la teoria de la codificació es la recerca d'algoritmes eficients de descodificació. La descodificació per permutacions és una tècnica que depèn totalment de l'existència d'un subconjunt especial, anomenat PD-conjunt, del grup d'automorfismes d'un codi per contribuir a la descodificació dels vectors rebuts. Recentment, s'ha introduït un nou mètode de descodificació per permutacions idoni per a codis Z4-lineals. L'objectiu principal d'aquesta tesis és proporcionar s-PD-conjunts, els quals permeten la correcció de fins a s errors, per a algunes families de codis Z4-lineals per a l'aplicació de la descodificació per permutacions. Es donen fites superiors sobre els valors de s per als quals poden existir s-PD-conjunts de mida mínima s+1 per a codis de Hadamard sistemàtics i codis de Kerdock. Es proporcionen dos criteris diferents per trobar s-PD-conjunts de mida s+1 per a codis Z4-lineals. Es presenten construccions explicites i recursives de s-PD-conjunts de mida s+1 per a codis binaris lineals de Hadamard i per a codis Z4-lineals de Hadamard, que compleixen el primer criteri. Així mateix, es mostren construccions explicites de s-PD-conjunts de mida s+1 per a codis Z4-lineals de Hadamard i de Kerdock que satisfan el segon criteri. Finalment, s'han desenvolupat noves funcions en MAGMA, basades en els resultats obtinguts en aquesta tesis, per treballar amb la descodificació per permutacions per a codis lineals sobre cossos finits i codis Z4-lineals. De la mateixa forma, s'han desenvolupat noves funcions per treballar amb altres mètodes de descodificació adequats per a codis Z4-lineals.

The hardest problem in the process of transmitting information is decoding. One of the major areas of research in coding theory is to find efficient decoding algorithms. Permutation decoding is a technique that strongly depends on the existence of a special subset, called a PD-set, of the permutation automorphism group of a code to assist in decoding received vectors. Recently, a new permutation decoding method suitable for Z4-linear codes was introduced. This dissertation aims to provide s-PD-sets, which enable the correction of up to s errors, for some families of Z4-linear codes to perform permutation decoding. We give upper bounds on s for which s-PD-sets of minimum size s+1 for systematic Hadamard and Kerdock codes can exist. Two different criteria to find s-PD-sets of size s+1 for Z4-linear codes are provided. Explicit and recursive constructions of s-PD-sets of size s+1 for binary linear and Z4-linear Hadamard codes fulfilling the first criterion are presented. Likewise, we show explicit constructions of s-PD-sets of size s+1 for Z4-linear Hadamard and Kerdock codes satisfying the second criterion. Finally, new MAGMA functions to deal with permutation decoding for linear codes over finite fields and Z4-linear codes, among other suitable decoding methods for Z4-linear codes, have been developed based on the results given in this dissertation.