Reed-Solomon-fejlkorrektion
Reed-Solomon-fejlkorrektion er en fremadrettet fejlkorrektionskode. Den fungerer ved at oversample et polynomium, der er konstrueret ud fra dataene. Polynomiet evalueres på flere punkter, og disse værdier sendes eller registreres. Ved at prøve polynomiet oftere end nødvendigt bliver polynomiet overbestemt. Så længe modtageren modtager "mange" af punkterne korrekt, kan modtageren genfinde det oprindelige polynomium, selv om der er "få" dårlige punkter til stede.
Reed-Solomon-koder anvendes i mange forskellige kommercielle applikationer, f.eks. i cd'er, dvd'er og Blu-ray-diske, i datatransmissionsteknologier som DSL og WiMAX og i radio- og tv-systemer som DVB og ATSC.
Oversigt
Reed-Solomon-koder er blokkoder. Det betyder, at en fast blok af inddata behandles til en fast blok af uddata. I tilfældet med den mest almindeligt anvendte R-S-kode (255, 223) - 223 Reed-Solomon-indgangssymboler (hver otte bit lang) kodes til 255 udgangssymboler.
- De fleste R-S ECC-ordninger er systematiske. Det betyder, at en del af udgangskodeordet indeholder inputdataene i deres oprindelige form.
- Der blev valgt en Reed-Solomon-symbolstørrelse på otte bit, fordi dekodere til større symbolstørrelser ville være vanskelige at implementere med den nuværende teknologi. Dette designvalg tvinger den længste kodeordslængde til at være 255 symboler.
- Reed-Solomon-standardkoden (255, 223) er i stand til at korrigere op til 16 Reed-Solomon-symbolfejl i hvert kodeord. Da hvert symbol faktisk består af otte bit, betyder det, at koden kan korrigere op til 16 korte fejlbølger som følge af den indre konvolutionelle dekoder.
Reed-Solomon-koden er ligesom den konvolutionelle kode en gennemsigtig kode. Det betyder, at hvis kanalsymbolerne er blevet omvendt et eller andet sted på linjen, vil dekoderne stadig fungere. Resultatet vil være komplementet til de oprindelige data. Reed-Solomon-koden mister imidlertid sin gennemsigtighed, hvis der anvendes virtuel nuludfyldning. Derfor er det obligatorisk, at dataenes betydning (dvs. sand eller komplementeret) skal opløses før Reed-Solomon-dekodning.
I Voyager-programmets tilfælde opnår R-S-koder næsten optimal ydeevne, når de sammenkædes med den indre (7, 1/2)-konvolutionelle (Viterbi)-kode. Da der kræves to kontrolsymboler for hver fejl, der skal korrigeres, resulterer dette i i alt 32 kontrolsymboler og 223 informationssymboler pr. kodeord.
Desuden kan Reed-Solomon-kodeordene interleaved på symbolbasis, inden de konvolutionelt kodes. Da dette adskiller symbolerne i et kodeord, bliver det mindre sandsynligt, at et burst fra Viterbi-dekoderen forstyrrer mere end ét Reed-Solomon-symbol i et kodeord.
Grundlæggende idé
Den centrale idé bag en Reed-Solomon-kode er, at de kodede data først visualiseres som et polynomium. Koden er baseret på en sætning fra algebra, der siger, at k forskellige punkter entydigt bestemmer et polynomium af højst k-1 grad.
Afsenderen bestemmer et polynomium af grad k - 1 {\displaystyle k-1}
over et endeligt felt, som repræsenterer de k {\displaystyle k}
datapunkter. Polynomiet "indkodes" derefter ved at evaluere det i forskellige punkter, og disse værdier er det, der rent faktisk sendes. Under transmissionen kan nogle af disse værdier blive ødelagt. Derfor sendes der faktisk mere end k punkter. Så længe der modtages tilstrækkeligt mange værdier korrekt, kan modtageren udlede, hvad det oprindelige polynomium var, og afkode de oprindelige data.
På samme måde som man kan korrigere en kurve ved at interpolere forbi et hul, kan en Reed-Solomon-kode bygge bro over en række fejl i en blok data for at genvinde koefficienterne i det polynomium, der tegnede den oprindelige kurve.
Historie
Koden blev opfundet i 1960 af Irving S. Reed og Gustave Solomon, som dengang var medlemmer af MIT Lincoln Laboratory. Deres grundlæggende artikel havde titlen "Polynomial Codes over Certain Finite Fields". Da den blev skrevet, var den digitale teknologi ikke tilstrækkelig avanceret til at implementere konceptet. Den første anvendelse i 1982 af RS-koder i masseprodukter var compact disc'en, hvor der anvendes to RS-koder med krydsede RS-koder. En effektiv afkodningsalgoritme for RS-koder over store afstande blev udviklet af Elwyn Berlekamp og James Massey i 1969. I dag anvendes RS-koder i harddisk, DVD, telekommunikation og digitale radio- og tv-protokoller.
