Decoding Reed Solomon and BCH codes beyond their error-correction radius: an euclidean approach

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