Códigos Goppa
Identificadores
URI: http://hdl.handle.net/10481/76351Metadatos
Mostrar el registro completo del ítemAutor
Pozo González, CristianDirector
Lobillo Borrero, Francisco JavierMateria
Códigos Goppa Algoritmos
Fecha
2022Patrocinador
Universidad de Granada. Facultad de Ciencias. Grado en Matemáticas. Curso académico 2021-2022Resumen
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.