Parámetros y decodificación eficiente de códigos afines

Abstract

La Teor´ıa de C´odigos busca transmitir de manera eficiente y sin errores un mensaje entre un emisor y un receptor a trav´es de un canal con ruido. Este ruido puede causar errores en el mensaje, luego el objetivo es recuperar el mensaje original a pesar de los errores que se hayan cometido. El emisor transformar´a el mensaje original mediante un proceso llamado codificaci´on, a˜nadiendo informaci´on redundante, y lo enviar´a por el canal. Una vez se reciba el mensaje, comienza el proceso m´as dif´ıcil, la decodificaci´on, que consiste en recuperar el mensaje original a partir del mensaje recibido. Esta teor´ıa busca familias de c´odigos que permitan corregir una cantidad considerable de errores y realizar los procesos de codificaci´on y decodificaci´on de manera eficaz. Una forma eficiente de realizar el proceso de codificaci´on es utilizar aplicaciones lineales, lo que se traduce en usar, en particular, c´odigos lineales. En el cap´ıtulo dos introduciremos este tipo de c´odigos y sus propiedades. Una familia interesante de c´odigos lineales son los c´odigos afines, en los que nos centraremos en el cap´ıtulo tres. En este cap´ıtulo uno de los objetivos ser´a dar una cota para la distancia m´ınima de estos c´odigos. En la literatura esta cota es conocida, pero hace uso de herramientas algebraicas potentes como son las bases de Gr¨obner. Una de las novedades de este trabajo es presentar este resultado sin emplear esta herramienta. Al final del cap´ıtulo tres introduciremos las familias m´as conocidas de c´odigos afines. Para algunas de estas familias, presentaremos, en el cap´ıtulo cuatro, decodificadores eficientes.

The main goal of Coding Theory is to efficient transfer reliable information through a channel with noise. This noise may distort the message so the aim is to recover the original message despite of the errors that may have occurred. The source will change the original message by a process called encoding, adding redundant information and, after that, the source will send the message through the channel. Once the encoded message is recieved, it starts the most difficult problem, decoding. The goal of this process is to obtain an estimate of the original message from the received message. This theory looks for families of codes that allow detecting and correcting as many errors as possible and that have efficient encoding and decoding procedures. An efficient way of encoding is to use linear maps, which is translated as using linear codes. This family of codes and its properties are introduced in Chapter two. An interesting family of linear codes are affine codes, we will focus our attention to these codes in Chapter three. One of the main goals of this Chapter is to give an lower bound of the minimum distance. In the literature this bound is known, but it makes use of powerful algebraic tools such as Gr¨obner bases. One of the key ideas of this Chapter is to present this result but free of Gr¨obner tools. At the end of Chapter three we will introduce some well known families of affine codes. For some of these families we will present, in Chapter four, efficient decoding algorithms.