MetadataShow full item record
AuthorPozo González, Cristian
DirectorLobillo Borrero, Francisco Javier
SponsorshipUniversidad de Granada. Facultad de Ciencias. Grado en Matemáticas. Curso académico 2021-2022
Whatever the channel through which information is transmitted will be a noisy channel, that is, the information received will not be the same as the one sent. Even in person-to-person communication there are environmental factors that prevent us from hearing each and every syllable of a conversation. To solve this problem, error correction codes appear, which are able to correct as many errors as possible in the transmission from the received word. Another big problem that arises is that of the security of the transmission of information, for this there are many secure encryption techniques, until nowadays, although with the development of quantum computers some of the most commonly used encryption algorithms are vulnerable, so it is necessary to bet on more secure algorithms, such as those based on error correction codes. One of the encryption algorithms based on codes, is the one proposed by McEliece that uses the Goppa codes, because they are very similar to the random codes and also present an efficient decoding algorithm, so this work is the link between the error correction codes and the encryption methods. The title of this work, encompasses a large part of code theory, so we will make a journey from linear codes to Goppa codes, passing by cyclic codes, BCH, Reed-Solomon and evaluation codes among others. In the first chapter, we will deal with linear codes describing all their properties and giving preliminary concepts about code theory, that will serve us for all the work. Also, we will give techniques to find the generating matrix and the parity control matrix of a linear code, which will allow us to encode and decode words with ease into any linear code. At the end of this chapter we will introduce the concept of spheres that will help us determine the number of words that can be corrected by a code and we will also give dimensions for the size of the code, such as the Singelton height. In the second chapter, we will develop the theory of cyclic codes that will serve us in the following chapters. Unlike linear codes, cyclics have an extra structure, they can be seen by an isomorphism, as ideals of Fnq which will allow us to make a more exhaustive study. Finally we will finish the chapter by giving some techniques to obtain the parity control matrix, using the polynomial and the generator matrix of a cyclic code. In the third chapter, we will continue a bit inside the cyclic codes, we will start developing the BCH codes, which unlike the cyclic ones, has a predefined minimum distance, characteristic that makes them very important since we have to determine exactly the minimum distance of a code is a NP problem and, unless P = NP, we cannot determine it in time. polynomial. We will continue with the Reed-Solomon codes that can be seen as a restriction of the BCH and finally we will move on to the evaluation codes and to the GRS (a generalization of the Reed-Solomon codes), which include within them most of the linear codes. Finally, in the last chapter, we will discuss in depth about the Goppa codes. We will start by defining ourselves and introducing its generating matrix, once we have got an efficient coding system, we will move on to decoding. Thanks to Euclid’s extended algorithm, we will develop a decoding algorithm, the Sugiyama algorithm, which will allow us to obtain the polynomials locator and evaluator, that is, to decode the received word. Finally we will talk about heights at the minimum distance (asymptotic and non-asymptotic) and we will show that the Goppa codes reach the Gilbert-Varshamov heights.