Codice Reed-Solomon
La correzione degli errori Reed-Solomon è un codice di correzione degli errori in avanti. Funziona sovracampionando un polinomio costruito a partire dai dati. Il polinomio è valutato in diversi punti, e questi valori sono inviati o registrati. Campionare il polinomio più spesso del necessario rende il polinomio sovradeterminato. Finché riceve "molti" punti correttamente, il ricevitore può recuperare il polinomio originale anche in presenza di "pochi" punti sbagliati.
I codici Reed-Solomon sono usati in molti tipi diversi di applicazioni commerciali, per esempio nei CD, DVD e Blu-ray Disc, nelle tecnologie di trasmissione dati come DSL e WiMAX, e nei sistemi di trasmissione come DVB e ATSC.
Panoramica
I codici Reed-Solomon sono codici a blocchi. Questo significa che un blocco fisso di dati in ingresso viene trasformato in un blocco fisso di dati in uscita. Nel caso del codice R-S più comunemente usato (255, 223) - 223 simboli di ingresso Reed-Solomon (ciascuno lungo otto bit) sono codificati in 255 simboli di uscita.
- La maggior parte degli schemi R-S ECC sono sistematici. Ciò significa che una parte della codifica di uscita contiene i dati di ingresso nella sua forma originale.
- È stata scelta una dimensione del simbolo Reed-Solomon di otto bit perché i decodificatori per simboli di dimensioni maggiori sarebbero difficili da implementare con la tecnologia attuale. Questa scelta progettuale costringe la più lunga lunghezza di codifica a 255 simboli.
- Il codice Reed-Solomon standard (255, 223) è in grado di correggere fino a 16 errori di simbolo Reed-Solomon in ogni codeword. Poiché ogni simbolo è in realtà otto bit, questo significa che il codice può correggere fino a 16 brevi raffiche di errore dovute al decoder convoluzionale interno.
Il codice Reed-Solomon, come il codice convoluzionale, è un codice trasparente. Questo significa che se i simboli del canale sono stati invertiti da qualche parte lungo la linea, i decodificatori continueranno a funzionare. Il risultato sarà il complemento dei dati originali. Tuttavia, il codice Reed-Solomon perde la sua trasparenza se si usa un riempimento virtuale a zero. Per questo motivo è obbligatorio che il senso dei dati (cioè, vero o complementare) sia risolto prima della decodifica Reed-Solomon.
Nel caso del programma Voyager i codici R-S raggiungono prestazioni quasi ottimali quando sono concatenati con il codice interno (7, 1/2) convoluzionale (Viterbi). Poiché sono necessari due simboli di controllo per ogni errore da correggere, questo risulta in un totale di 32 simboli di controllo e 223 simboli di informazione per ogni parola di codice.
Inoltre, i codici Reed-Solomon possono essere interfogliati su una base di simbolo prima di essere codificati convoluzionalmente. Poiché questo separa i simboli in un codeword, diventa meno probabile che un burst dal decoder Viterbi disturbi più di un simbolo Reed-Solomon in qualsiasi codeword.
Idea di base
L'idea chiave dietro un codice Reed-Solomon è che i dati codificati sono prima visualizzati come un polinomio. Il codice si basa su un teorema dell'algebra che afferma che qualsiasi k punti distinti determinano univocamente un polinomio di grado al massimo k-1.
Il mittente determina un polinomio di grado k - 1 {displaystyle k-1}
, su un campo finito, che rappresenta i k {displaystyle k} punti dati
. Il polinomio è poi "codificato" dalla sua valutazione in vari punti, e questi valori sono ciò che viene effettivamente inviato. Durante la trasmissione, alcuni di questi valori possono essere corrotti. Pertanto, più di k punti sono effettivamente inviati. Finché un numero sufficiente di valori viene ricevuto correttamente, il ricevitore può dedurre quale fosse il polinomio originale e decodificare i dati originali.
Nello stesso senso in cui si può correggere una curva interpolando oltre una lacuna, un codice Reed-Solomon può colmare una serie di errori in un blocco di dati per recuperare i coefficienti del polinomio che ha disegnato la curva originale.
Storia
Il codice fu inventato nel 1960 da Irving S. Reed e Gustave Solomon, che allora erano membri del MIT Lincoln Laboratory. Il loro articolo seminale era intitolato "Polynomial Codes over Certain Finite Fields". Quando fu scritto, la tecnologia digitale non era abbastanza avanzata per implementare il concetto. La prima applicazione, nel 1982, dei codici RS in prodotti di massa fu il compact disc, dove vengono usati due codici RS interfogliati. Un algoritmo di decodifica efficiente per codici RS a grande distanza fu sviluppato da Elwyn Berlekamp e James Massey nel 1969. Oggi i codici RS sono usati in hard disk, DVD, telecomunicazioni e protocolli di trasmissione digitale.
