ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-10012014-160110


Thesis type
Tesi di laurea magistrale
Author
NERI, ALESSANDRO
URN
etd-10012014-160110
Thesis title
Decoding Reed Solomon and BCH codes beyond their error-correction radius: an euclidean approach
Department
MATEMATICA
Course of study
MATEMATICA
Supervisors
relatore Prof.ssa Gianni, Patrizia
Keywords
  • list decoding
  • codici correttori
  • teoria dei codici
Graduation session start date
17/10/2014
Availability
Full
Summary
In questo lavoro viene presentato un algoritmo alternativo per il list decoding di codici Reed-Solomon e BCH
basato sull'algoritmo di divisione euclidea. Fissato un numero e, e data una parola ricevuta, l'obiettivo e' quello di dare in output una lista di parole del codice che abbiano distanza al piu' e da essa. Per i codici BCH la decodifica avviene attraverso
la ricerca del polinomio locatore dell'errore, un particolare polinomio che si trova nel nucleo della matrice delle sindromi e che ha tutte le radici nel campo di partenza. Utilizzando queste proprieta', e attraverso l'algoritmo di divisione euclidea, siamo in grado di elencare tutti i possibili polinomi locatori dell'errore, e quindi tutte le parole del codice che abbiano la distanza desiderata.
Vengono poi analizzati gli aspetti computazionali di tale algoritmo, nel caso generale e in alcuni casi particolari.
Infine vengono fatti dei confronti con gli algoritmi gia' esistenti, e vengono studiati dei bound sul numero massimo di parole che l'algoritmo restituisce.
File