Reed-Solomonova korekcija napak

Pregled

Reed-Solomonove kode so blokovne kode. To pomeni, da se fiksni blok vhodnih podatkov obdela v fiksni blok izhodnih podatkov. V primeru najpogosteje uporabljene kode R-S (255, 223) se 223 vhodnih Reed-Solomonovih simbolov (vsak dolg osem bitov) kodira v 255 izhodnih simbolov.

• Večina shem R-S ECC je sistematičnih. To pomeni, da določen del izhodne kodne besede vsebuje vhodne podatke v izvirni obliki.
• Izbrana je bila velikost simbola Reed-Solomon osem bitov, saj bi bilo dekoderje za večje velikosti simbolov težko izvesti s trenutno tehnologijo. Zaradi te izbire je najdaljša kodna beseda dolga 255 simbolov.
• Standardna (255, 223) Reed-Solomonova koda lahko v vsaki kodni besedi popravi do 16 napak Reed-Solomonovih simbolov. Ker je vsak simbol dejansko osem bitov, to pomeni, da lahko koda popravi do 16 kratkih izbruhov napak zaradi notranjega konvolucijskega dekoderja.

Reed-Solomonova koda je tako kot konvolucijska koda pregledna koda. To pomeni, da bodo dekoderji še vedno delovali, če so bili simboli kanala nekje na poti obrnjeni. Rezultat bo dopolnilo prvotnih podatkov. Vendar pa Reed-Solomonova koda izgubi svojo preglednost, če se uporabi navidezno ničelno polnjenje. Zato je obvezno, da se pred dekodiranjem Reed-Solomonove kode določi smisel podatkov (tj. pravi ali dopolnjeni).

V primeru programa Voyager kode R-S dosežejo skoraj optimalno zmogljivost, ko so združene z (7, 1/2) konvolucijsko (Viterbijevo) notranjo kodo. Ker sta za vsako popravljeno napako potrebna dva kontrolna simbola, je tako na kodno besedo skupaj 32 kontrolnih simbolov in 223 informacijskih simbolov.

Poleg tega se lahko kodne besede Reed-Solomon pred konvolucijskim kodiranjem prepletajo po simbolih. Ker se s tem ločijo simboli v kodni besedi, je manj verjetno, da bo izbruh iz Viterbijevega dekoderja zmotil več kot en Reed-Solomonov simbol v posamezni kodni besedi.

Osnovna ideja

Ključna ideja Reed-Solomonove kode je, da se kodirani podatki najprej predstavijo kot polinom. Koda se opira na trditev iz algebre, ki pravi, da poljubnih k različnih točk enolično določa polinom stopnje največ k-1.

Pošiljatelj določi polinom stopnje k - 1 {\displaystyle k-1} nad končnim poljem, ki predstavlja k {\displaystyle k} podatkovnih točk. Polinom je nato "kodiran" z vrednotenjem v različnih točkah, te vrednosti pa so dejansko poslane. Med prenosom se lahko nekatere od teh vrednosti poškodujejo. Zato se dejansko pošlje več kot k točk. Dokler je dovolj vrednosti prejetih pravilno, lahko sprejemnik sklepa, kakšen je bil prvotni polinom, in dekodira prvotne podatke.

Podobno kot lahko krivuljo popravimo z interpolacijo mimo vrzeli, lahko Reed-Solomonova koda premosti vrsto napak v bloku podatkov in obnovi koeficiente polinoma, ki je narisal prvotno krivuljo.

Zgodovina

Kodo sta leta 1960 izumila Irving S. Reed in Gustave Solomon, ki sta bila takrat člana laboratorija MIT Lincoln Laboratory. Njun temeljni članek je imel naslov "Polinomske kode nad določenimi končnimi polji". Ko je bil članek napisan, digitalna tehnologija še ni bila dovolj napredna, da bi lahko izvedli ta koncept. Prva uporaba kod RS v množično proizvedenih izdelkih leta 1982 je bila kompaktna plošča, na kateri sta uporabljeni dve prepleteni kodi RS. Učinkovit dekodirni algoritem za kode RS velikih razdalj sta leta 1969 razvila Elwyn Berlekamp in James Massey. Danes se kode RS uporabljajo v trdih diskih, DVD-jih, telekomunikacijah in protokolih za digitalno oddajanje.