Reed-Solomon de corecție a erorilor

Codurile Reed-Solomon sunt coduri bloc. Aceasta înseamnă că un bloc fix de date de intrare este transformat într-un bloc fix de date de ieșire. În cazul celui mai frecvent utilizat cod R-S (255, 223) - 223 de simboluri Reed-Solomon de intrare (fiecare cu o lungime de opt biți) sunt codificate în 255 de simboluri de ieșire.

• Majoritatea schemelor R-S ECC sunt sistematice. Aceasta înseamnă că o parte din cuvântul de cod de ieșire conține datele de intrare în forma lor originală.
• A fost aleasă o dimensiune a simbolului Reed-Solomon de opt biți, deoarece decodificatoarele pentru dimensiuni mai mari ale simbolurilor ar fi dificil de implementat cu tehnologia actuală. Această alegere de proiectare forțează cea mai mare lungime a cuvântului de cod să fie de 255 de simboluri.
• Codul Reed-Solomon standard (255, 223) este capabil să corecteze până la 16 erori de simbol Reed-Solomon în fiecare cuvânt de cod. Deoarece fiecare simbol este de fapt opt biți, acest lucru înseamnă că codul poate corecta până la 16 explozii scurte de erori datorate decodorului convoluțional intern.

Codul Reed-Solomon, ca și codul convoluțional, este un cod transparent. Acest lucru înseamnă că, dacă simbolurile canalului au fost inversate undeva de-a lungul liniei, decodificatoarele vor funcționa în continuare. Rezultatul va fi complementul datelor originale. Cu toate acestea, codul Reed-Solomon își pierde transparența în cazul în care se utilizează umplerea virtuală cu zero. Din acest motiv, este obligatoriu ca sensul datelor (adică adevărat sau completat) să fie rezolvat înainte de decodificarea Reed-Solomon.

În cazul programului Voyager, codurile R-S ating o performanță aproape optimă atunci când sunt concatenate cu codul interior convoluțional (7, 1/2) (Viterbi). Deoarece sunt necesare două simboluri de control pentru fiecare eroare care trebuie corectată, rezultă un total de 32 de simboluri de control și 223 de simboluri de informație pe cuvânt de cod.

În plus, cuvintele de cod Reed-Solomon pot fi intercalate pe bază de simboluri înainte de a fi codificate prin convoluție. Deoarece astfel se separă simbolurile dintr-un cuvânt de cod, devine mai puțin probabil ca o rafală de la decodorul Viterbi să perturbe mai mult de un simbol Reed-Solomon dintr-un cuvânt de cod.

Ideea cheie din spatele unui cod Reed-Solomon este că datele codificate sunt mai întâi vizualizate ca un polinom. Codul se bazează pe o teoremă din algebră care afirmă că orice k puncte distincte determină în mod unic un polinom de cel mult k-1 grad.

Expeditorul determină un polinom de gradul k - 1 {\displaystyle k-1} , pe un câmp finit, care reprezintă cele k {\displaystyle k} puncte de date. Polinomul este apoi "codificat" prin evaluarea sa în diferite puncte, iar aceste valori sunt cele care sunt trimise efectiv. În timpul transmiterii, unele dintre aceste valori pot fi corupte. Prin urmare, se trimit efectiv mai mult de k puncte. Atâta timp cât suficiente valori sunt recepționate corect, receptorul poate deduce care a fost polinomul original și poate decoda datele originale.

În același sens în care se poate corecta o curbă prin interpolarea pe lângă un gol, un cod Reed-Solomon poate acoperi o serie de erori într-un bloc de date pentru a recupera coeficienții polinomului care a desenat curba originală.

Codul a fost inventat în 1960 de Irving S. Reed și Gustave Solomon, care erau pe atunci membri ai Laboratorului Lincoln al MIT. Articolul lor de referință a fost intitulat "Polynomial Codes over Certain Finite Fields". Când a fost scris, tehnologia digitală nu era suficient de avansată pentru a implementa conceptul. Prima aplicație, în 1982, a codurilor RS în produse de masă a fost discul compact, în care sunt utilizate două coduri RS intercalate. Un algoritm eficient de decodare pentru codurile RS de distanță mare a fost dezvoltat de Elwyn Berlekamp și James Massey în 1969. În prezent, codurile RS sunt utilizate în protocoalele pentru unități de hard disk, DVD-uri, telecomunicații și difuzare digitală.