Codice Reed-Solomon

Nella teoria dei codici, il codice Reed-Solomon è un tipo di codice lineare (ciclico) non binario di rilevazione e correzione d'errore, inventato da Irving S. Reed e Gustave Solomon.

Viene utilizzato per correggere errori di flusso in diverse importanti applicazioni di comunicazione digitale e memorizzazione di dati. I suoi impieghi vanno dall'elettronica di consumo alle comunicazioni nello spazio profondo.

Si basa sul sovracampionamento di un polinomio costruito partendo dai dati da trasmettere. Il polinomio è quindi calcolato in più punti di quanti sarebbero sufficienti a identificarlo univocamente; il valore di questi punti viene trasmesso o registrato. Alla ricezione o alla lettura è possibile ricostruire il polinomio originario, e conseguentemente i dati, anche in presenza di errori.

Storia

Il codice fu inventato nel 1960 da Irving S. Reed e Gustave Solomon, che al tempo lavoravano al Lincoln laboratory del Massachusetts Institute of Technology (MIT). Il lavoro fu pubblicato nell'articolo Codici polinomiali su alcuni campi finiti (Polynomial Codes over Certain Finite Fields).^[1]

Ma nel 1960 la tecnologia digitale non era sufficientemente avanzata per realizzare il concetto. L'applicazione dei codici di Reed-Solomon fu resa possibile nel 1969, grazie all'opera di Elwyn Berlekamp e James Massey, che inventarono un efficiente algoritmo di decodifica.

Nel 1977 i codici Reed-Solomon furono applicati mirabilmente nel programma spaziale Voyager, sotto forma di codici concatenati per il controllo degli errori.

Teoria base

L'idea chiave dietro il codice Reed-Solomon è di vedere i dati da "proteggere" come un polinomio. L'algebra lineare dice che un numero k di punti distinti determinano univocamente un polinomio di grado al massimo k-1.

Il polinomio è quindi "codificato" tramite il calcolo di diversi suoi punti e i valori di questi punti sono ciò che viene effettivamente trasmesso. Durante la trasmissione, alcuni di questi punti possono essere corrotti. Per questo motivo sono trasmessi k+n punti, con n che sono i dati aggiunti per la protezione dell'informazione. Il ricevitore analizza i punti ricevuti e determina il polinomio di grado k-1 che meglio approssima la sequenza di punti ricevuti. Finché "non troppi" punti sono ricevuti corrotti, il ricevitore può ricostruire quale fosse il polinomio originario e quindi decodificare i dati. Nel caso di un numero eccessivo di errori comunque il decodificatore ricostruisce un polinomio "simile" a quello di partenza. Quindi l'algoritmo mostra una dipendenza debole dal numero di errori, non vi è un numero di errori oltre la quale la ricostruzione fallisce, ma l'algoritmo ricostruisce sempre un polinomio verosimile, la verosimiglianza del polinomio ricostruito dipende dal numero di errori ricevuti.

Funzionamento

Durante la trasmissione di un qualsiasi segnale analogico o digitale numerosi fattori esterni, quali rumori elettrici, interferenze, righe sulla superficie dei CD/DVD, abrasioni o macchie sui codici a barre, creano una serie di errori che possono compromettere la corretta trasmissione o lettura dei dati.

Il funzionamento del codice Reed-Solomon può essere schematizzato nelle seguenti azioni:

Emissione dei dati
Codifica Reed-Solomon
Trasmissione dei dati (con possibili errori)
Decodifica Reed-Solomon (rilevazione e correzione d'errore)
Ricezione corretta dei dati

Ad esempio, durante la masterizzazione dei CD audio la sequenza di campioni (PCM a 16 bit) viene divisa in blocchi di 24 byte a cui viene applicato un codice di correzione Reed-Solomon di 4 byte che consente la correzione di 4 errori in posizioni note o 2 errori in posizioni ignote per ogni blocco. Successivamente 112 blocchi contigui vengono raggruppati e scambiati tra loro in modo che due blocchi successivi nel flusso dei dati non siano mai vicini tra di loro. Questa disposizione (interleaving) serve a fare in modo che errori consecutivi sul CD (dovuti a graffi o impronte) in fase di lettura si trovino ad essere sparsi lungo il flusso di dati ricostruito, aumentando così le probabilità di correzione.^[2]

Applicazioni

Il codice Reed-Solomon viene utilizzato nelle tecnologie della comunicazione e dell'informazione per la codifica e decodifica dei dati.

Lo strumento è impiegato anche in alcune applicazioni per dispositivi con funzioni scanner come il nintendo e-Reader o i telefoni cellulari e gli smartphone.

Memorizzazione dati

Nell'ambito dell'elettronica di consumo il codice è usato per correggere gli errori di decodifica dovuti a difetti dei supporti di memorizzazione come DAT, CD, DVD, Blu-ray Disc e negli standard RAID.

Il codice Reed-Solomon viene inoltre utilizzato nei codici a barre Postbar o nei codici a barre bidimensionali come il Codice Aztec, il Codice QR,^[3] il Data Matrix, il MaxiCode e il PDF417, per il ripristino dei dati nel caso in cui una parte del codice fosse danneggiato, permettendo una lettura corretta.

Trasmissione dati

Nel campo delle telecomunicazioni il codice Reed-Solomon è usato per la trasmissione e ricezione dei dati nelle comunicazioni satellitari; nelle connessioni a banda larga e wireless come DSL o WiMAX; nei sistemi di trasmissione ATSC e Digital Video Broadcasting; nella trasmissione radio in codifica DAB+^[4] e per aggirare la natura inaffidabile dei dati trasmessi sui canali di comunicazione BEC.

La prima applicazione importante nel campo delle comunicazioni satellitari è stata quella usata per la decodifica delle immagini digitali inviate dalla sonda spaziale Voyager.

Nei sistemi Consultative Committee for Space Data Systems e Space Communications Protocol Specifications, vengono usate varie applicazioni per la stima e l'eliminazione degli errori (FEC).

Altre versioni del codice sono utilizzate nelle missioni spaziali Mars Pathfinder, Galileo, Mars Exploration Rover e Cassini, che operano tra 1 e 1,5 decibel circa del limite imposto dalla capacità di canale.

Note

^ Irving S. Reed, Gustave Solomon. Polynomial Codes over Certain Finite Fields. «Journal of the Society for Industrial and Applied Mathematics» (SIAM), giugno 1960. Vol. 8 (2), pp 300–304. DOI 10.1137/0108018
^ Kees Immink, Reed–Solomon Codes and the Compact Disc, in Reed–Solomon Codes and Their Applications, Wiley-IEEE Press, 1994.
^ (EN) QR Code Outline Specification di Denso-Wave. Consultato il 30 luglio 2010
^ Sergio Cimmino, Dab, radio digitale: la rivoluzione che attende l’Italia, Ci Siamo, 30 gennaio 2019. URL consultato il 3 febbraio 2019 (archiviato dall'url originale il 4 febbraio 2019).