A Combinatorial Commutative Algebra Approach to Complete Decoding
Irene Márquez-Corbella · 2013
En primer lugar quiero expresar mis más sinceros agradecimientos a mis directores, Dr. Antonio Campillo López y Dr. Edgar Martínez-Moro, por todo su apoyo, confianza en mi trabajo y sabios consejos.Han sido un referente no solamente para el desarrollo de esta tesis sino en mi formación, ofreciéndome una visión más amplia del mundo académico y permitiéndome descubrir cuánto me motiva.I would also like to express my sincere gratitude to Prof. Ruud Pellikaan for his fundamental role in my work during the last four years.Prof. Ruud Pellikaan provided me with the guidance, the assitance and the expertise that I needed during my doctoral time.It has been a pleasure to work with him and I hope we will continue our collaboration in future projects.Al Ministerio de Educación que ha financiado esta tesis a través de una beca de Formación de Profesorado Universitario (FPU) con referencia AP2008-01598.Y al Ministerio de Ciencia e Innovación por su contribución económica a través del proyecto Geometría algebraica de las singularidades, computación e información con referencia MTM2007-64704.Me gustaría dar las gracias de manera especial a todos mis profesores de la ULL por su inestimable ayuda y, lo más importante, por enseñarme que con trabajo todo es posible.A toda mi familia, a mis padres, a mi hermana y a Franchy, por su paciencia, por su apoyo incondicional y por su ayuda al equilibrar la balanza.Gracias porque nunca me he sentido lejos, por perder el miedo a viajar y por buscar conmigo soluciones a las adversidades.Y por último, aunque no por ello menos importante, a mis amigos, que han sabido disculpar mis ausencias y siempre han tenido una palabra de ánimo.Si de algo puedo presumir es de haber hecho grandes amigos en todas mis paradas, soy muy afortunada.Last but not least I want to thank my friends who have been able to excuse all my absences and always had a word of encouragement.If I can presume of something is to have made great friends in all my stops, I'm very lucky.Pour terminer, mais non moins important, à mes amis qui ont excusé toutes mes absences et qui ont toujours trouver un mot d'encouragement.S'il est une chose que je peux affirmer, c'est d'avoir noué de belles amitiés partout où je suis allée, j'ai beaucoup de chance.Ed infine, ma non per importanza, ai miei amici, i quali sono sempre stati comprensivi quando non ho potuto essere presente e mi hanno sempre incoraggiata nei momenti piú difficili.Se posso vantarmi di qualcosa, è di aver stretto grandi amicizie durante questo percorso di studio e di questo mi ritengo molto fortunata.Tot slot, maar zeker niet onbelangrijk, voor mijn vrienden, die in staat zijn geweest mij te vergeven voor mijn afwezigheid en altijd een bemoedigend woord hadden.Ik prijs mezelf gelukkig dat ik goede vrienden heb gemaakt tijdens al mijn verblijven.Und nicht zuletzt danke ich meinen Freunden, die mir mein Fehlen immer verziehen und mich stets ermutigt haben.Wenn ich mit Recht behaupten kann, dass ich während aller meiner Aufenthalte wunderbare Freunde gefunden habe, so kann ich mich sehr glücklich schätzen. Summary (English)This thesis aims to explore the bridge between the algebraic structure of a linear code and the complete decoding process.Complete decoding is an NP-problem [6] for an arbitrary linear code, even if preprocessing is allowed [23].Our goal is to make an algebraic analysis of the decoding process.To that end, we associate different mathematics structures to certain families of codes.From a computational point of view, our description does not provide an efficient algorithm since our problem is NPcomplete.However we propose alternative algorithms and new techniques to reduce the space and time needed to handle such problem.By , s , and q where q is a prime power, we denote the ring of integers, the ring of integers modulo s, an arbitrary field and a finite field with q elements, respectively.Complete decoding has many applications not only in Coding Theory but also in other areas of Information Security: