Nonlinear Codes: Representation, Construction, Minimum Distance Computation and Decoding    

Abstract

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.

Date of Award	10 Sept 2014
Original language	English
Supervisor	Mercè Villanueva (Director) & Jaume Pujol Capdevila (Director)