Šiame taip vadinamame Informacijos amžiuje niekam nereikia priminti koks svarbus ne tik informacijos perdavimo greitis, bet taip pat duomenų saugojimo ar siuntimo tikslumas. Mašinos daro klaidas, ir šios antžmogiškos klaidos kitu atveju pilnaverčius duomenis gali paversti šiukšlėmis, netgi padaryti pavojingais. Todėl duomenys turi būti saugūs lygiai taip pat kaip architektai paskaičiuoja pastato stabilumą žemės drebėjimo atveju.
Šias problemas pradeda nagrinėti Irving S. Reed ir Gustave Solomon (MIT Linkolno laboratorijos darbuotojai) savo penkių lapų darbe (kuris išspausdintas ”Journal of the Society for Industrial and Applied Mathematics” žurnale išleistame 1960 metais). Šiame darbe: “Polynomial Codes over Certain Finite Fields” supažindinama su klaidų taisymo idėjomis. Pastarąją klaidų koregavimo techniką galima pritaikyti tiek kompiuterio kietąjame diske, tiek kompaktinių diskų grotuve, tiek kitose srityse. Reed-Solomono kodų (o taip pat technikų) pagalba buvo galima gauti pritrenkiančių kitų planetų nuotraukų (kurias padarė Voyager II), ar klausytis įbrėžto kompaktinio disko. Ir netolimoje ateityje tai leido kabelinėms televizijoms suspausti 500 kanalų į jų sistemas.
“Kai kalbame apie kompaktinių diskų gotuvus, skaitmeninius garso įrašus, skaitmeninę televiziją ar apie kitą artėjančią skaitmeninę techniką, kuri artėja – visur reikėtų vartoti reed-Solomon kodus kaip integruotą sistemos dalį”, sako Robert McEliece, dirbantis kodavimo teoretiku Caltech elektrinės inžinerijos departamente.
Kodėl? Ogi todėl, kad skaitmeninė informacija sudaryta iš “bitų” eilių ( nuliukų ir vienetukų) ir fizinio įrenginio, nesvarbu kaip kruopščiai pagaminto, vieną kartą gali pavesti. Klaidų koregavimo kodai tai tam tikras saugumo garantas, matematinis apsidraudimas šiame netobulame materialiniame pasaulyje.
Raktas į klaidų taisymo kodus yra pertekliškumas. Ir ištiesų, patys paprasčiausi klaidų taisymo kodai tiesiog viską keletą kartų pakartoja. Jei pvz. tikimasi, kad bus ne daugiau vienos klaidos pranešime, ir jei kiekvieną bitą pranešime pakartosime tris kartus, tai būsime tikri, kas pranešimas bus priimtas teisingai (111 000 011 111 bus teisingai suprastas kaip 1011). Taigi n klidų galime kompensuoti pasiuntus pranešimą 2n+1 karto. Bet šis grubus klaidų taisymas prieštarauja greitaeigiam, daugiasluoksniam informacijos apdorojimui.
1960 m. klaidų taisymo kodų teorija buvo tik vienos dekados senumo. Šios teorijos pagrindus vėlyvais 1940 m. padėjo Claude Shannon. Tuo pačiu metu Richard Hamming supažindino su pavienės-klaidos korekcijos ir dvigubos-klaidos detekcijos teorija. Nuo 1950m. prasidėjo daugelis tyrimų susijusių su klaidų taisymo kodais. Tačiau jau anksčiau minėtas žurnalas Reed-Solomon kodų atradimą pavadino šūviu į taikinį.
Ši kodavimo sistema rėmėsi bitų grupėmis, rečiau pavieniais “0” ir “1”. Tai leido Reed-Solomon kodams gerai taisyti klaidų srautus. Šešios nuoseklios bitų klaidos, pvz. gali paveikti daugiausiai du baitus. Be to dvigubą-klaidą koreguojanti Reed-Solomon versija gali duoti dar didesnį saugumą (dabartinių Reed-Solomon kodų pritaikymas CD technologijoje leidžia dirbti jei klaidų srautas iki 4000 nuoseklių bitų).
Matematiškai, Reed Solomon kodai yra pagrįsti aritmetinių laukų ribotumu. Iš tiesų, 1960m. straipsnis buvo pradėtas apibrėžiant kodą kaip “vektorių nuo dimensijos m per ribotą K lauką iki to vektoriaus aukštesnės dimensijos per tą patį lauką”. Pradedant “pranešimu” (a_0, a_1, … , a_{m-1}), kur kiekvienas a_k yra K lauko elementas. Reed Solomon kodas padaro (P(0), P(g), p(g^2),… P(g^{N-1})), kur N yra elementų skaičius K lauke, g yra ciklinių grupių nenulinių elementų K lauke generatorius, ir P(x) yra polinomas a_0+a_1x+ …+ a_{m-1} x^{m-1}. Jei N yra didesnis nei m, nei P polinomo vertės ir riboti laukai garantuoja, kad koeficientai P gali būti atstatyti iš bet kurios m vertės.
Nepaisant visų Reed Solomon kodų privalumų, jie negalėjo būti staigiai pradėti naudoti, nes turėjo palaukti “geležies” techninio išsivystymo lygio. “1960m. nebuvo tokio dalyko kaip, kad greitaeigė elektronika” – bent jau tikrai nebuvo lyginant su šiandieniniais standartais, teigia McEliece. Reed Solomon darbas “pasiūlė keletą gerų būdų kaip apdoroti informaciją, bet niekas negalėjo pasakyti ar tai buvo galima praktiškai panaudoti. 1960m. to greičiausiai nebuvo galima.”
Bet štai technika pasivijo ir pradedamas didelis kiekis tyrimų kodavimo srityje. Vienas iš tokių mokslinikų yra Elwyn Berlekamp’as elektronikos inžinierijos profesorius iš University of California at Berkeley, kuris atrado veiksmingą Reed-Solomon kodo dekodavimo algoritmą. Berlekamp’o algoritmas buvo naudojamas Voyger II sistemoje bei yra pagrindas kompaktinių diskų grotuvų dekodavime.
Reed-Solomon kodus galima panaudoti daugelyje sistemų:
1. duomenų saugojimo įrenginiuose (juostos, kompaktiniai diskai, DVD, štrichkodai ir t.t.)
2. belaidėse ar mobiliosiose komunikacijose (mobilūs telefonai, mikrobangų ryšiai ir t.t.)
3. palydovinėse komunikacijose
4. skaitmeninėje televizijoje
5. greitaeigiuose modemuose kaip ADSL,xDSL ir t.t.

Reed-Solomon enkoderis paima skaitmeninių duomenų bloką ir prideda ekstra “perteklinių” bitų. Klaidos atsiranda duomenų perdavimo arba saugojimo metu dėl įvairių priežasčių. Reed-Solomon dekoderis apdoroja kiekvieną duomenų bloką, bando taisyti klaidas ir atstatyti pradinius duomenis. Klaidų skaičius ir tipas kurios gali būti ištaisytos priklauso nuo Reed-Solomon kodo charakteristikų.

2. REED-SOLOMON KODŲ SĄVYBĖS

Reed-Solomon kodai yra linijiniai blokų kodai,tai BCH kodų dalis. Reed-Solomon kodas yra apibrėžiamas kaip RS(n,k) su s bitų simboliais.
Tai reiškia, kad encoderis paima k duomenų simbolių iš kiekvieno s bito ir prideda lyginius simbolius, padarydamas n simbolio kodinį žodį. Yra n-k lyginumo simboliai iš kiekvieno s bito. Reed-Solomon dekoderis gali ištaisyti iki t simbolių, kurių kodiniame žodyje yra klaidų, kur 2t = n-k.

Sekanti diagrama rodo tipinį Reed Solomon kodinį žodį (tai sistematinis kodas, kadangi duomenys paliekami nepakitę, o pridedami tik lyginumo simboliai):

Pavyzdys: Populiarus Reed-Solomon kodas yra RS(255, 223) su 8-bitų simboliais. Kiekvienas kodinis žodis turi 255 kodinio žodžio baitų, iš kurių 223 baitai yra duomenys, o 32 lyginumo baitai. Šiam kodui:

n = 255, k = 223, s = 8
2t = 32, t = 16

Dekoderis gali ištaisyti bet kuriuos 16-ka simbolių kodiniame žodyje. Iki 16-kos klaidų bet kurioje kodinio žodžio vietoje bus automatiškai ištaisytos.

Duodant simboliui dydį s, maksimalus kodinio žodžio ilgis (n) Reed-Solomon kodui bus: n = 2s – 1

Pavyzdys: Kodo su 8-ių bitų (s=8) simboliais maksimalus ilgis yra 255 baitai.

Reed-Solomon kodai gali būti sutrumpinti, paverčiant dalį duomenų simbolių nuliais encoderyje, nesiunčiant jų, o po to juos įterpiant dekoderyje.

Pavyzdys: Kodas (255,223) nagrinėtas aukščiau, gali būti sutrumpintas iki (200,168). Enkoderis paima bloką iš 168-ų duomenų baitų, prideda 55-ų nulių baitus, sukuria (255,223) kodinį žodį ir siunčia tik 168-is duomenų ir 32 lyginumo baitus.

Proceso “jėgos” kiekis reikalaujamas koduoti ir dekoduoti Reed-Solomon kodus priklauso nuo lyginumo simbolių skaičiumi kodiniame žodyje. Didele t reikšmė rodo, kad gali būti ištaisytas didelis klaidų skaičius, bet tai reikalauja didelės apskaičiuojamosios galios, nei kad tai būtų tuo atveju jei t būtų maža.

2.1. Simbolių klaidos

Viena simbolio klaida laikoma tada kai vienas bitas simbolyje blogas, arba visi bitai yra klaidingi.

Pavyzdys: Kodas RS(255,223) gali ištaisyti 16-a simbolio klaidų. Blogiausiu atveju gali atsirasti 16-a bitų klaidų, po vieną atskirame simbolyje (baite), kad dešifratorius galėtų ištaisyti 16-a bitų klaidų. Geriausiu atveju 16-os pilnų baitų klaidų atsiranda taip, kad dešifratorius ištaiso 16 x 8 bitų klaidų.

Reed-Solomon kodai ypatingai gerai pritaikyti taisyti srautines (kai serija bitų kodiniame žodyje gaunama su klaidomis).

2.2. Dekodavimas

Reed-Solomon algebros dekodavimo procedūros gali ištaisyti klaidas ir ištrynimus. Ištrynimas atsiranda tuomet, kai klaidingo simbolio pozicija arba vieta yra žinoma. Dekoderis gali ištaisyti iki t klaidų arba iki 2t ištrynimų. Ištrynimų informacija dažnai yra palaikoma demoduliatoriaus skaitmeninių komunikacijų sistemose, t.y. demoduliatorius pažymi gautus simbolius, kuriuose yra klaidų tikimybė.

Kai kodinis žodis dekoduojamas, yra trys galimi rezultatai:
1. jeigu 2s + r < 2t (s klaidos, r išrynimai), tuomet pradinis perduodamas kodinis žodis visada bus atstatytas, Kitu atveju 2. dekoderis nustatys, kad jis negali atstatyti pradinio kodinio žodžio ir tai praneš. Arba 3. dekoderis neiššifruos ir atstatys klaidingą kodinį žodį be jokių pranešimų. Visų trijų variantų galimybė priklauso nuo konkretaus Reed-Solomon kodo, taip pat nuo klaidų skaičiaus bei jų tipo. 2.3. Kodavimo pliusai Reed-Solomon kodų panaudojimo privalumas yra tas, kad klaidų pasitaikymo tikimybė iššifruotuose duomenyse yra dažniausiai žymiai mažesnė nei tuomet, kai Reed-Solomon kodai nenaudojami. Tai apibūdinama kaip kodavimo pliusais. Pavyzdys: Skaitmeninė komunikacijų sistema yra suprojektuota dirbti prie bitų klaidų koeficiento (BER) 10-9 , t.y. ne daugiau kaip vienas iš 109 bitų yra gaunami su klaidomis. Tai gali būti pasiekta padidinant perdavimo galią arba pridedant Reed-Solomon kodą (arba panaudojant kitą tolesnių klaidų korekciją – FEC). Reed-Solomon kodavimas leidžia sistemai pasiekti toki patį bitų klaidų koeficientą prie mažesnio perdavimo galingumo. Galios “sutaupymas” ir yra kodavimo pliusas. 3.REED-SOLOMON KODAVIMO IR DEKODAVIMO ARCHITEKTŪRA Reed-Solomon kodavimas ir dekodavimas galimas tiek programiškai tiek panaudojant specializuotą aparatūrą. 3.1. Riboto (Galois) lauko aritmetika Reed-Solomon kodai pagrįsti Galois lauko arba kitaip baigtinio lauko pagrindu. Baigtinis laukas turi savybę, kad aritmetinės operacijos (+, -, x, / ir t.t.) lauko elementuose, visada turi rezultatą lauke. Reed-Solomon koderis ir dekoderis turi atlikti tas aritmetines operacijas. Šioms operacijoms atlikti reikalinga atitinkama programinė ar aparatūrinė įranga. 3.2. Polinominis generatorius Reed-Solomon kodinis žodis yra generuojamas naudojant specialų polinomą. Visi galimi kodiniai žodžiai yra dalūs generuojančiam polinomui. Šis generuojantis polinomas atrodo taip: g(x) = (x-ai)(x-ai+1)…(x-ai+2t) o kodinis =odis konstruojamas naudojant: c(x) = g(x).i(x) kur g(x) yra generuojantis polinomas, i(x) yra informacinis blokas, c(x) yra galiojantis kodinis žodis ir priklauso pirminiam lauko elementui. Pavyzdys: Generatorius kodui RS (255,249) g(x) = (x-a0)(x-a1)(x-a2)(x-a3)(x-a4)(x-a5) g(x) = x6+g5x5+g4x4+g3x3+g2x2+g1x1+g0 3.3. Enkoderio architektūra Sistematiniame Reed-Solomon kodiniame žodyje 2t lyginumo simbolius duoda polinomas: p(x) = i(x)xn-k mod g(x) Sekanti diagrama vaizduoja sistematinio RS (255,249) enkoderio architektūrą: Kiekvienas iš 6 registrų saugo simbolį (8 bitus). Aritmetiniai operatoriai atlieka baigtinio lauko sudėtį arba daugybą baigtiniam simboliui. 3.4. Dekoderio architektūra Esminė Reed-Solomon dekoderio architektūra atrodo taip: Žymėjimas: r(x) gautas kodinis žodis Si sindromas L(x) klaidos nustatymo polinomas Xi klaidos vieta Yi klaidos reikšmė c(x) atstatytas kodinis žodis v klaidų skaičius Gautas kodinis žodis r(x) yra originalus (siųstas) kodinis žodis c(x) plius klaidos: R(x) = c(x) + e(x) Reed-Solomon dekoderis bando nustatyti iki t klaidų (arba 2t ištrynimų) vietą bei reikšmę ir jas pataisyti. 3.5. Sindromo apskaičiavimas Tai analogiška lygiškumo apskaičiavimui. Reed-Solomon kodinis žodis turi 2t sindromus kurie priklauso tik nuo klaidų (ne nuo siunčiamo kodinio žodžio). Sindromai gali būti apskaičiuojami dalijant 2t šaknis (generuojančio polinomo g(x)) iš r(x). 3.6. Simbolių klaidų vietų radimas Šį uždavinį sudaro vienalaikių lygčių su t nežinomaisiais sprendimas. Keletas greitų algoritmų gali tai padaryti. Šie algoritmai pasinaudoja Reed-Solomon kodų specialia matricine struktūra ir smarkiai sumažina apskaičiavimo pastangas bei operacijų atlikimo greitį. Jie paremti šiais dviem esminiais žingsniais: Randamas klaidų pasiskirstymo polinomas Tai galima padaryti panaudojant Berlekamp-Massey arba Euklid algoritmą. Pastarasis algoritmas plačiau taikomas praktikoje, kadangi jis yra lengviau įdiegiamas įrangoje, tačiau Berlekamp-Massey algoritmas pranašesnis efektyvumu. Randamos polinomo šaknys Tai atliekama panaudojant Chien ieškojimo algoritmą. Norint surasti klaidingų simbolių vertes, taip pat reikia spręsti vienalaikias lygtis su t nežinomaisiais. Labiausiai paplitęs Forney algoritmas. 4. APARATŪRINIS ĮGYVENDINIMAS Egzistuoja didelis skaičius komercinių gaminių. Dauguma jų yra tiesiog integruoti grandynai arba tiesiog mikroschemos sugebančios koduoti ir dekoduoti Reed-Solomon kodus. Šios mikroschemos leidžia tam tikrą programavimą (pavyzdžiui, RS(255,k), kur t = nuo 1-o iki 16-os simbolių). Šiuo metu yra pastebima tendencija vis plačiau naudoti VHDL bei Verilog projektus (vadovaujamasi loginiu bei intelektualiu pagrindu). Pastaroji įranga turi pranašumą standartinių mikroschemų tarpe. Loginis pagrindas gali būti integruotas su kitais VHDL bei Verilog komponentais ir sintezuotas su FPGA (lauko programuojamas užtvaros (gate) išrykiavimas) bei ASIC (specifinės mikroschemos), o tai leidžia panaudoti taip vadinamą “sistemą mikroschemoje” t.y. sudėtingi moduliai gali būti įdiegti vienoje mikroschemoje. Priklausomai nuo produkcijos apimties, loginiu pagrindu dirbančios mikroschemos yra taip pat pranašesnės už standartines mikroschemas mažesne sistemos kaina, t.y. jos gal ir yra brangesnės, tačiau reikia mažiau išlaidų jų priežiūrai, eksploatacijai, jos yra efektyvesnės. 5. PROGRAMINIS ĮGYVENDINIMAS Iki dabar programinis realaus-laiko kodavimas reikalaudavo labai didelios skaičiavimo galios (išimtis paprasti Reed-Solomon kodai, su mažomis t reikšmėmis. Pagrindinė programinio Reed-Solomon kodavimo įgyvendinimo problema yra ta, kad bendros paskirties procesoriai neatlieka Galois lauko aritmetinių operacijų. Žinoma geras dizainas ir galingas procesorius leidžia operuoti santykinai dideliais duomnų srautais. Sekantys duomenys demonstruoja Pentium 166MHz testo rezultatus: Kodas Duomenų srautas RS (255,251) 12 Mbps RS (255,239) 2,7 Mbps RS (255,223) 1,1 Mbps Šie duomenys parodo tik dekodavimo greitį: kodavimas vyksta žymiai greičiau, kadangi reikalauja mažiau skaičiavimų. Šie duomenys buvo gauti naudojant 4i2i Communications Ltd kompanijos greičiui optimizuotas programas. 6. IŠVADOS 1. Naudojant Reed-Solomon kodavimą, galima padidinti duomenų perdavimo spartą ir sumažinti perdavimo galingumą. 2. Šių kodų pritaikymas įvairioms sritimis leidžia sparčiau vystyti algoritmų efektyvumą. NAUDOTA LITERATŪRA http://www.4i2i.com http://www.cs.utk.edu/~shuford/terminal/reed_solomon_codes.html TURINYS 1. ĮVADAS 2 2. REED-SOLOMON KODŲ SĄVYBĖS 3 2.1. Simbolių klaidos 4 2.2. Dekodavimas 5 2.3. Kodavimo pliusai 5 3. REED-SOLOMON KODAVIMO IR DEKODAVIMO ARCHITEKTŪRA 5 3.1. Riboto (Galois) lauko aritmetika 5 3.2. Polinominis generatorius 6 3.3. Enkoderio architektūra 6 3.4. Dekoderio architektūra 6 3.5. Sindromo apskaičiavimas 7 3.6. Simbolių klaidų vietų radimas 7 4. APARATŪRINIS ĮGYVENDINIMAS 8 5. PROGRAMINIS ĮGYVENDINIMAS 8 6. IŠVADOS 9 NAUDOTA LITERATŪRA 9 KAUNO TECHNOLOGIJOS UNIVERSITETAS Telekomunikacijų katedra Atsisiųsti moku.lt_reed_solomon_kodai