Reed-Solomonove kode: definicija, delovanje in praktična uporaba

Reed-Solomonove kode: kako delujejo korekcije napak in praktična uporaba v CD, DVD, Blu-ray, DSL in DVB — zanesljiva obnova podatkov ter odpornost prenosa.

Reed-Solomonova korekcija napak je koda za sprotno korekcijo napak. Deluje tako, da se iz podatkov izdela polinom s presežnim vzorčenjem. Polinom se oceni v več točkah, te vrednosti pa se pošljejo ali zapišejo. Če polinom vzorčimo pogosteje, kot je potrebno, je polinom prekomerno določen. Dokler sprejemnik pravilno sprejme "veliko" točk, lahko obnovi prvotni polinom tudi ob prisotnosti "nekaj" slabih točk.

Kaj je Reed–Solomonova koda?

Reed–Solomon (RS) je razredu linearnih blokovnih kod, ki delujejo na simbolih iz končnega polja (najpogosteje GF(2^m), torej simboli po m bitov). Koda RS je primer evaluacijske kode: sporočilo predstavimo kot polinom stopnje manjše od k, nato pa ga ocenimo v n različnih vrednostih polja. Rezultat je kodna beseda dolžine n.

Matematična osnova in lastnosti

• Parametri: RS(k, n) ali pogosteje RS(n, k), kjer je k dolžina sporočila (v simbolih) in n dolžina kodne besede (v simbolih). Število paritetnih simbolov je n − k.
• Maksimalna dolžina: Za polje GF(2^m) je največja možna dolžina n = 2^m − 1 (če ne uporabljamo skrajševanja).
• Minimum razdalje: Reed–Solomonova koda je MDS (maximum distance separable), kar pomeni, da ima najmanjšo razdaljo d = n − k + 1. S tem doseže Singletonovo mejno vrednost.
• Zmožnost popravljanja napak: Koda z n − k paritetnimi simboli lahko popravlja do t = floor((n − k)/2) poljubnih simbolskih napak. Pri znanih pozicijah izbrisanih/izgubljenih simbolov (erasures) lahko poravna do n − k izbrisanih simbolov. Splošna omejitev za kombinacijo napak (e) in izbrisanih simbolov (s) je: 2e + s ≤ n − k.

Kako se kodira

Osnovni postopek kodiranja:

• Sporočilo interpretiramo kot koeficiente polinoma m(x) stopnje manjše od k.
• Izberemo n različnih elementov polja (ocenjevalne točke) α_1, …, α_n in izračunamo c_i = m(α_i) za vse i. Kodna beseda je (c_1, …, c_n).
• V praksi se pogosto uporablja tudi sistematično kodiranje, kjer so originalni simboli prisotni v kodni besedi, paritetni simboli pa so dodani ločeno (to se doseže z uporabo generator-polinoma ali z ustreznim izračunom paritet).

Kako se dekodira

Postopek dekodiranja je sestavljen iz več korakov (poenostavljeno):

• Izračun simptomov (syndromes) — preveri se, ali so prisotne napake.
• Iskanje polinoma za določitev položajev napak (error-locator polynomial). Algoritmi: Berlekamp–Massey, Peterson–Gorenstein–Zierler, ali uporaba evklidskega algoritma.
• Iskanje korenov tega polinoma (npr. s Chien's search) za ugotovitev položajev napak.
• Izračun velikosti napak (error magnitudes) — pogosto s Forneyjevo formulo.
• Popravek napak in obnova prvotnega polinoma/sporočila.

Algoritmi so učinkoviti in v praksi uporabljajo tabelo log/antilog za hitro množenje v GF(2^m). Implementacije se razlikujejo glede na zahteve po hitrosti, pomnilniku in odporu na napake.

Praktične značilnosti in optimizacije

• Simbolne napake in gruče: Ker RS deluje na simbolih (npr. bajtih), je zelo primeren za popravilo zaporednih bitnih napak (burst errors). Eno napačen simbol lahko pokvari več bitov, a ga koda obravnava kot eno enoto.
• Interleaving: Če so napake grozdene (npr. dolgi bloki napak), se uporablja prepletanje (interleaving) več RS kod, kar razprši grozdo po več kodnih besedah in poveča odpornost.
• Skrajševanje: V mnogih aplikacijah se uporablja skrajšana različica kode (shortened RS), kjer je n manjše od maksimalnega 2^m−1, da se prilega konkretni dolžini sporočila.
• Kompozitne sheme: V mnogih komunikacijskih sistemih se RS kode uporabljajo v kombinaciji s konvolucijskimi kodami ali LDPC kot del večstopenjskega (concatenated) sistema za izboljšanje zmogljivosti pri nizkih stopnjah napak.

Primeri in tipične konfiguracije

• Pogosto uporabljeno polje je GF(256) (m = 8), ker je simbol en bajt. Tipičen primer je RS(255, 223) — n − k = 32, torej t = 16, kar pomeni popravljanje do 16 napačnih bajtov v kodni besedi.
• V praksi se pogosto uporabljajo tudi kratkejše (skrajšane) različice iste kode za specifične potrebe (npr. QR kode, skrajšane RS za optične medije in pomnilnike).

Praktična uporaba

Reed-Solomonove kode se uporabljajo v številnih komercialnih aplikacijah, na primer v CD-jih, DVD-jih in Blu-ray diskih, v tehnologijah prenosa podatkov, kot sta DSL in WiMAX, ter v sistemih oddajanja, kot sta DVB in ATSC. Poleg tega so RS kode prisotne v:

• QR in drugih 2D črtnih kodah (za popravilo poškodb črtne slike).
• V satelitskih in vesoljskih komunikacijah (pogosto v kombinaciji z močnejšimi kodami za daljše povezave).
• V sistemih za shranjevanje podatkov (npr. nekateri RAID-6 režimi, flash pomnilnik in optični mediji).
• V komunikacijskih standardih, kodnih knjižnicah in v kriptografskih aplikacijah za razprševanje podatkov in toleranco napak.

Zaključek

Reed–Solomonove kode so vsestransko uporabne, ker so MDS kode z visoko odpornostjo proti simbolskim napakam in zmožnostjo popravljanja skupinskih napak. Zaradi matematične lepote (polinomska predstavitev, lastnosti končnih polj) in učinkovitih dekodirnih algoritmov so še vedno standardna izbira v mnogih terminalnih in industrijskih sistemih za zanesljiv prenos in trajno shranjevanje podatkov.

Išči po črki