Tesis doctorales: TESEO

Ayuda Salir

Ficha de Tesis

Imprimir

Ministerio de Educación, Cultura y Deporte - Gobierno de España

Título: NONLINEAR CODES: REPRESENTATION, CONSTRUCTIONS, MINIMUM DISTANCE COMPUTATION AND DECODING
Autor: Zeng, Fanxuan
Universidad: Universidad Autónoma de Barcelona
Departamento: INGENIERIA DE LA INFORMACION Y DE LAS COMUNICACIONES
Fecha de Lectura: 10/09/2014
Programa de doctorado: Informática
Dirección:
- PUJOL CAPDEVILA, JAUME (Codirector)
- VILLANUEVA GAY, MERCE (Codirector)
Tribunal:
- Fernández Córdoba, Cristina (presidente)
- VALLS MARSAL, MAGDA (secretario)
- MARTÍNEZ MORO, EDGAR (vocal)
Descriptores:
- CODIGO Y SISTEMAS DE CODIFICACION
- CONSTRUCCION DE ALGORITMOS
Localización: BIBLIOTECA DE COMUNICACIÓN Y HEMEROTECA GENERAL UAB
Marcador: https://www.educacion.gob.es/teseo/mostrarRef.do?ref=1110267Añadir a favoritos.
Resumen:
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 nonlinear 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 first question that arises when we use nonlinear codes is their representation. 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 efficient algorithms to compute the kernel and coset representatives from the list of codewords are given. In addition, properties 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 of the constituent nonlinear codes. 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 of fact, it has been proven to be an NP-hard problem \cite{NP}. However, some algorithms have been developed to compute the minimum distance for linear codes using different approaches: Gr\"{o}bner bases \cite{Edgar_ComputingCosetLeaders, Edgar_CosetLeaders}, tree structure \cite{MM_MinDis}, probabilistic algorithms \cite{StatisDecode, Proba_Aron, Probabilistic} and vector enumeration \cite{White}. 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 distance 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 decoding. For linear codes, a general decoding algorithm is the syndrome decoding. 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 first general method for decoding, which is comparable to syndrome decoding for linear ones. Finally, most of these algorithms have been evaluated using the \textsc{Magma} software, and a new \textsc{Magma} package to deal with binary nonlinear codes has been developed, based in the results given in this dissertation.

Imprimir

Modificar Consulta Nueva Consulta

versión 4.2