Reed-Solomon klaidų taisymo kodas: apibrėžimas, veikimo principas ir taikymai
Sužinokite, kaip Reed–Solomon klaidų taisymo kodas atkūria duomenis per polinomus ir kur taikomas (CD/DVD/Blu‑ray, DSL, WiMAX, DVB, ATSC).
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.
Kaip tai veikia (supaprastinta)
- Žinutė (k simbolių) interpretuojama kaip daugianario koeficientai lauke GF(q) (dažniausiai q=2^m, pavyzdžiui GF(256)).
- Kodavimas: daugianaris įvertinamas n skirtingų taškų (n>k), gaunamas kodinis žodis iš n simbolių. Perteklinių simbolių kiekis yra n−k.
- Korekcijos galia: Reed–Solomon kodas gali pataisyti iki t = (n − k)/2 simbolių klaidų arba iki n − k žinomų praleidimų (erozijų).
- Dekodavimas: gavus simbolių seką, imtuvas atlieka sindromų skaičiavimą, randa klaidų lokatorių polinomą, nustato klaidų vietas ir dydžius, tada pataiso klaidas ir atkuria pradinį daugianarį (interpoliuoja).
Parametrai ir savybės
- n – bendras kodinio žodžio ilgis (simboliais); dažnai maksimumas n = q − 1 laukui GF(q).
- k – duomenų simbolių skaičius.
- n − k – pariteto (perteklinių) simbolių skaičius.
- t = (n − k)/2 – maksimali pataisomų simbolių klaidų skaičiaus riba (kai klaidų pozicijos nežinomos).
- Simbolinis lygmuo: Reed–Solomon dirba simboliais (pvz., baitais), todėl ypač gerai aptinka ir taiso spiečių (burst) klaidas — vienas simbolis gali atstovauti kelioms bitų klaidoms.
- Systematinis kodavimas: dažniausiai naudojama sisteminė forma, kai originalūs duomenys yra aiškiai matomi kodiniame žodyje, o papildomi pariteto simboliai pridedami šalia.
Dekodavimo algoritmai (dažniausi)
- Petersono–Gorenšteino–Zierlerio metodas (Peterson–Gorenstein–Zierler).
- Berlekamp–Massey algoritmas — efektyviai randa klaidų lokatorių polinomą.
- Euclido algoritmas (panaudojamas, kad spręsti polinomų lygtis dekodavimo metu).
- Chien paieška — greitas klaidų pozicijų nustatymas.
- Forney algoritmo taikymas klaidų amplitudžių (magnitudžių) skaičiavimui ir pataisymui.
Šie žingsniai paprastai atliekami seka: sindromų skaičiavimas → klaidų lokatoriaus radimas → klaidų vietų nustatymas (Chien) → klaidų dydžių skaičiavimas (Forney) → pataisymai.
Pritaikymas praktikoje
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.
- Skaitmeniniuose laikmenose ir magnetiniuose/flash kaupikliuose (dėl gebėjimo taisyti spiečių klaidas).
- Optinėse plokštelėse ir vaizdo laikmenose — kombinuojant su interliavimo schemomis, siekiama ištverti ilgus klaidų ruožus.
- Duomenų perdavimo kanalai (palydovinė, mobili, DSL) — patikimumo didinimas linke su trumpos ar ilgos trukmės trukdžiais.
- QR ir kiti 2D brūkšninių kodų standartai naudoja RS pagrįstą klaidų taisymą.
- Archyvavimo ir RAID sistemose — papildomas duomenų atsparumas gedimams.
- Giluminės kosmoso misijos ir kiti aukšto patikimumo ryšiai — dėl stiprios klaidų korekcijos galimybės.
Privalumai ir trūkumai
- Privalumai: stipri simbolinė klaidų korekcija, efektyvi prieš spiečių klaidas, plačiai ištirtas ir patikimas algoritmų rinkinys, lankstūs parametrai (n, k).
- Trūkumai: skaičiavimai atliekami laukuose GF(q), tad sudėtingumas didėja su didesniais laukais; realiuoju laiku pritaikant reikia optimizuotų įgyvendinimų arba aparatinės įrangos; kai klaidų skaičius viršija t, dekodavimas gali nepavykti arba duoti neteisingą rezultatą.
Apibendrinant, Reed–Solomon kodai yra universalus ir galingas įrankis duomenų patikimumui užtikrinti ir plačiai taikomas tiek saugojimo, tiek perdavimo srityse. Dėl savo simbolinio pobūdžio jie ypač tinkami situacijoms, kur dažnai pasitaiko spiečių klaidos ar praleidimai.
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.
Ieškoti