Codice Reed-Solomon

Article on other languages:

• Reed-Solomon
• Reed-Solomon-Code
• Reed–Solomon_error_correction
• Reed-Solomon
• Code_de_Reed-Solomon
• リード・ソロモン符号
• 리드_솔로몬_부호
• Reed-Solomoncode
• Reed–Solomon_error_correction
• Код_Рида-Соломона
• Reed-Solomon_error_correction

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Questa voce di informatica è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Il codice Reed-Solomon è un codice utilizzato per correggere errori di flusso in svariate applicazioni di comunicazione digitale e memorizzazione di dati.

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.

Attualmente viene utilizzato in diversi sistemi quali:

• Supporti di memorizzazione (p.es. compact disc, DVD)
• Dispositivi mobili e wireless (p.es. telefoni cellulari)
• Comunicazioni satellitari
• Connessioni a banda larga xDSL

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

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

• Emissione dei dati
• Codifica Reed-Solomon
• Trasmissione dei dati (con possibili errori)
• Decodifica Reed-Solomon
• Ricezione

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

Il codice nei compact disc

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. Questo "interlacciamento" serve a fare in modo che errori consecutivi sul CD (dovuti a graffi o impronte) in fase di lettura si trovino ad essere sparsi per il flusso di dati ricostruito, aumentando così grazie al codice Reed-Solomon (e altri) la probabilità di correzione.

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 loro storico articolo fu "Codici polinomiali su alcuni campi finiti" (Polynomial Codes over Certain Finite Fields). All'epoca dell'articolo, la tecnologia digitale non era sufficientemente avanzata per realizzare il concetto. L'applicazione dei codici di Reed-Solomon fu resa possibile dall'invenzione di un efficiente algoritmo di decodifica da parte di Elwyn Berlekamp, professore di ingegneria elettrica all'Università della California di Berkeley.

Collegamenti esterni

Un software che usa il codice Reed-Solomon è ICE ECC. ICE ECC è uno strumento di verifica e riparazione files: consente di proteggere i dati importanti / sensibili affinché, sui supporti digitali, non si corrompano col tempo. ICE ECC basa il suo funzionamento sul codice Reed-Solomon.