Reed-Solomoni veaparandus
Reed-Solomoni veaparandus on edasi suunatud veaparanduskood. See toimib andmete põhjal konstrueeritud polünoomi ületamplitseerimise teel. Polünoomi hinnatakse mitmes punktis ja need väärtused saadetakse või salvestatakse. Kui polünoomist võetakse proovid sagedamini kui vaja, siis on polünoom ülemääratud. Niikaua kui vastuvõtja saab "paljud" punktid õigesti kätte, saab vastuvõtja taastada algse polünoomi isegi "mõne" halva punkti olemasolul.
Reed-Solomon-koode kasutatakse paljudes erinevates ärirakendustes, näiteks CD-des, DVD-des ja Blu-ray-diskides, andmeedastustehnoloogiates, nagu DSL ja WiMAX, ning ringhäälingusüsteemides, nagu DVB ja ATSC.
Ülevaade
Reed-Solomoni koodid on plokk-koodid. See tähendab, et fikseeritud sisendandmete plokk töödeldakse fikseeritud väljundandmete plokiks. Kõige sagedamini kasutatava R-S-koodi (255, 223) puhul kodeeritakse 223 Reed-Solomoni sisendsümbolit (igaühe pikkus kaheksa bitti) 255 väljundsümboliks.
- Enamik R-S ECC-skeeme on süstemaatilised. See tähendab, et mingi osa väljundkoodisõnast sisaldab sisendandmeid algsel kujul.
- Reed-Solomoni sümboli suurus on kaheksa bitti, sest suurema sümboli suuruse dekoodreid oleks praeguse tehnoloogiaga raske rakendada. Selline disainivalik sunnib pikima koodisõna pikkuseks 255 sümbolit.
- Standardne (255, 223) Reed-Solomoni kood on võimeline parandama kuni 16 Reed-Solomoni sümboli viga igas koodisõnas. Kuna iga sümbol koosneb tegelikult kaheksast bitist, tähendab see, et kood suudab parandada kuni 16 lühikest veapartiid, mis tulenevad sisemisest konvolutsioonilisest dekooderist.
Reed-Solomoni kood, nagu ka konvolutsiooniline kood, on läbipaistev kood. See tähendab, et kui kanali sümbolid on kuskil inverteeritud, töötavad dekoodrid ikkagi. Tulemuseks on algsete andmete komplement. Reed-Solomoni kood kaotab aga läbipaistvuse, kui kasutatakse virtuaalset nulltäitmist. Seetõttu on kohustuslik, et enne Reed-Solomoni dekodeerimist tuleb lahendada andmete tähendus (st tõene või komplementaarne).
Programmi Voyager puhul saavutavad R-S koodid peaaegu optimaalse jõudluse, kui neid ühendatakse (7, 1/2) konvolutsioonilise (Viterbi) sisekoodiga. Kuna iga parandatava vea jaoks on vaja kaks kontrollsümbolit, siis on ühe koodisõna kohta vaja kokku 32 kontrollsümbolit ja 223 infosümbolit.
Lisaks sellele võib Reed-Solomoni koodisõnu enne konvolutsioonilist kodeerimist sümbolite kaupa interleaveerida. Kuna see eraldab koodisõnas olevad sümbolid, on vähem tõenäoline, et Viterbi dekooderist lähtuv purunemine häirib rohkem kui ühte Reed-Solomoni sümbolit ühes koodisõnas.
Põhiidee
Reed-Solomoni koodi põhiidee seisneb selles, et kodeeritud andmed kujutatakse kõigepealt polünoomina. Kood tugineb algebrast pärit teoreemile, mis väidab, et mis tahes k erinevat punkti määrab üheselt polünoomi, mille aste on maksimaalselt k-1.
Saatja määrab k - 1. astme {\displaystyle k-1}
polünoomi, mis esindab k {\displaystyle k}
andmepunkti. Seejärel "kodeeritakse" polünoomi selle hindamisega erinevates punktides ja need väärtused on see, mis tegelikult saadetakse. Edastamise käigus võivad mõned neist väärtustest kahjustuda. Seetõttu saadetakse tegelikult rohkem kui k punkti. Kui piisavalt palju väärtusi on õigesti vastu võetud, saab vastuvõtja järeldada, milline oli algne polünoom, ja dekodeerida algsed andmed.
Samamoodi, nagu saab kõverat parandada, interpoleerides lünka mööda, saab Reed-Solomoni koodiga ületada andmeplokis esinevad vead, et taastada algse kõvera joonistanud polünoomi koefitsiendid.
Ajalugu
Koodi leiutasid 1960. aastal Irving S. Reed ja Gustave Solomon, kes olid tollal MIT Lincolni laboratooriumi töötajad. Nende põhjapanev artikkel kandis pealkirja "Polünoomikoodid teatud piiratud väljadel". Selle kirjutamise ajal ei olnud digitaaltehnoloogia veel piisavalt arenenud, et seda kontseptsiooni rakendada. Esimene RS-koodide rakendus 1982. aastal masstoodangus oli kompaktplaat, kus kasutatakse kahte omavahel põimitud RS-koodi. Elwyn Berlekamp ja James Massey töötasid 1969. aastal välja tõhusa dekodeerimisalgoritmi suurte vahemaade RS-koodide jaoks. Tänapäeval kasutatakse RS-koode kõvakettal, DVD-l, telekommunikatsioonis ja digitaalringhäälingu protokollides.
