Reed-Solomon klaidų taisymas
Reed-Solomon klaidų taisymas yra tiesioginis klaidų taisymo kodas. Jis veikia perrinkdamas iš duomenų sudarytą polinomą. Polinomas įvertinamas keliuose taškuose ir šios vertės siunčiamos arba įrašomos. Atrinkus daugianarį dažniau, nei reikia, daugianaris tampa pertekliniu. Kol imtuvas teisingai priima "daug" taškų, jis gali atkurti pradinį polinomą net ir esant "keliems" blogiems taškams.
Reed-Solomon kodai naudojami įvairiose komercinėse programose, pavyzdžiui, CD, DVD ir "Blu-ray" diskuose, duomenų perdavimo technologijose, pavyzdžiui, DSL ir "WiMAX", ir transliavimo sistemose, pavyzdžiui, DVB ir ATSC.
Apžvalga
Rido Salomono kodai yra blokiniai kodai. Tai reiškia, kad fiksuotas įvesties duomenų blokas apdorojamas į fiksuotą išvesties duomenų bloką. Dažniausiai naudojamo R-S kodo (255, 223) atveju 223 Reed-Solomono įvesties simboliai (kiekvienas iš jų yra aštuonių bitų ilgio) užkoduojami į 255 išvesties simbolius.
- Dauguma R-S ECC schemų yra sisteminės. Tai reiškia, kad tam tikroje išvesties kodinio žodžio dalyje yra įvesties duomenys pradiniu pavidalu.
- Pasirinktas aštuonių bitų Reed-Solomon simbolio dydis, nes didesnio dydžio simbolių dekoderius būtų sudėtinga įdiegti naudojant dabartinę technologiją. Dėl tokio konstrukcinio pasirinkimo ilgiausias kodų žodžio ilgis yra 255 simboliai.
- Standartinis (255, 223) Reed-Solomono kodas gali ištaisyti iki 16 Reed-Solomono simbolių klaidų kiekviename kodo žodyje. Kadangi kiekvienas simbolis iš tikrųjų yra aštuoni bitai, tai reiškia, kad kodas gali ištaisyti iki 16 trumpų klaidų serijų dėl vidinio konvoliucinio dekoderio.
Rydo-Solomono kodas, kaip ir konvoliucinis kodas, yra skaidrus kodas. Tai reiškia, kad jei kanalo simboliai kažkur linijoje buvo apversti, dekoderiai vis tiek veiks. Rezultatas bus pradinių duomenų papildinys. Tačiau Reed-Solomon kodas praranda skaidrumą, jei naudojamas virtualus nulinis užpildymas. Dėl šios priežasties prieš Rydo-Solomono dekodavimą privaloma nustatyti duomenų prasmę (t. y. tikri ar papildyti).
Programos "Voyager" atveju R-S kodai pasiekia beveik optimalų našumą, kai yra sujungti su (7, 1/2) konvoliuciniu (Viterbi) vidiniu kodu. Kadangi kiekvienai taisomai klaidai ištaisyti reikia dviejų kontrolinių simbolių, iš viso viename kodo žodyje reikia 32 kontrolinių simbolių ir 223 informacinių simbolių.
Be to, prieš konvoliucinį kodavimą Reed-Solomono kodų žodžius galima perskirstyti pagal simbolius. Kadangi tokiu būdu atskiriami kodų žodžių simboliai, sumažėja tikimybė, kad Viterbi dekoderio sprogimas sutrikdys daugiau nei vieną Reed-Solomono simbolį bet kuriame viename kodų žodyje.
Pagrindinė idėja
Pagrindinė Rydo-Solomono kodo idėja yra ta, kad koduojami duomenys pirmiausia vaizduojami kaip polinomas. Kodas remiasi algebros teorema, kuri teigia, kad bet k skirtingų taškų vienareikšmiškai nustato daugianarį, kurio laipsnis yra ne didesnis kaip k-1.
Siuntėjas nustato k - 1 laipsnio {\displaystyle k-1}
polinomą baigtiniame lauke, kuris atspindi k {\displaystyle k}
duomenų taškų. Tada polinomas "užkoduojamas" įvertinant jį įvairiuose taškuose, ir šios vertės yra tai, kas iš tikrųjų siunčiama. Perduodant kai kurios iš šių verčių gali būti sugadintos. Todėl iš tikrųjų siunčiama daugiau nei k taškų. Kol pakankamai reikšmių gaunama teisingai, imtuvas gali nustatyti, koks buvo pradinis polinomas, ir iššifruoti pradinius duomenis.
Taip pat, kaip galima ištaisyti kreivę interpoliuojant pro tarpą, Reed-Solomono kodas gali įveikti duomenų bloko klaidų seriją ir atkurti polinomo, kuris nubrėžė pradinę kreivę, koeficientus.
Istorija
Kodą 1960 m. išrado Irvingas S. Ridas ir Gustavas Salomonas, tuo metu dirbę MIT Linkolno laboratorijoje. Jų pagrindinis straipsnis vadinosi "Polinominiai kodai tam tikruose baigtiniuose laukuose". Kai jis buvo parašytas, skaitmeninės technologijos dar nebuvo pakankamai pažengusios, kad būtų galima įgyvendinti šią koncepciją. Pirmasis RS kodų pritaikymas masinės gamybos produktuose 1982 m. buvo kompaktinis diskas, kuriame buvo naudojami du persipynę RS kodai. Efektyvų didelio atstumo RS kodų dekodavimo algoritmą 1969 m. sukūrė Elwyn Berlekamp ir James Massey. Šiuo metu RS kodai naudojami standžiuosiuose diskuose, DVD, telekomunikacijų ir skaitmeninio transliavimo protokoluose.
