Il problema della decodifica e della correzione degli errori per il codice di Reed-Solomon

In questo elaborato vengono analizzati i principali approcci utilizzati per la decodifica e la correzione degli errori dei codici di Reed-Solomon, una particolare classe di codici ciclici ampiamente diffusi nelle applicazioni. Il primo metodo preso in considerazione, basato sull'interpolazione polinomiale, fu teorizzato nello stesso articolo del 1960 in cui Irving S. Reed e Gustav Solomon introdussero per la prima volta questo tipo di codice. Tuttavia, l’alta complessità di questo approccio ne limitò drasticamente l'utilità pratica, stimolando immediatamente la ricerca di alternative più efficaci. Nello stesso anno, infatti, il metodo di decodifica proposto da Reed-Solomon venne soppiantato dal metodo di Peterson-Gorenstein-Zierler, incentrato sulla risoluzione di sistemi lineari, e successivamente dal metodo iterativo di Berlekamp-Massey. A questo punto viene introdotta l'equazione chiave, la cui risoluzione consente la ricostruzione del vettore di errore. Questo porta al metodo di Sugyiama et. al., che sfrutta l'efficacia dell'algoritmo di Euclide esteso per raggiungere tale obiettivo. Infine, viene approfondito un metodo altrettanto efficace che si basa sulla ricerca delle basi di Gröbner per i moduli.