Reed–Solomon-koodit
Reed-Solomon-virheenkorjaus on eteenpäin suuntautuva virheenkorjauskoodi. Se toimii ylinäytteistämällä datasta muodostettua polynomia. Polynomi arvioidaan useissa pisteissä, ja nämä arvot lähetetään tai tallennetaan. Jos polynomista otetaan näytteitä useammin kuin on tarpeen, polynomi on ylideterminoitu. Kunhan vastaanotin vastaanottaa "monet" pisteet oikein, se voi palauttaa alkuperäisen polynomin, vaikka "muutama" piste olisi huono.
Reed-Solomon-koodeja käytetään monissa erilaisissa kaupallisissa sovelluksissa, esimerkiksi CD-, DVD- ja Blu-ray-levyissä, tiedonsiirtotekniikoissa, kuten DSL- ja WiMAX-verkoissa, sekä lähetysjärjestelmissä, kuten DVB ja ATSC.
Yleiskatsaus
Reed-Solomon-koodit ovat lohkokoodeja. Tämä tarkoittaa sitä, että kiinteä tulotietolohko jalostetaan kiinteäksi tulotietolohkoksi. Yleisimmin käytetyn R-S-koodin (255, 223) tapauksessa 223 Reed-Solomon-sisääntulosymbolia (kukin kahdeksan bittiä pitkä) koodataan 255 lähtösymboliksi.
- Useimmat R-S ECC-järjestelmät ovat järjestelmällisiä. Tämä tarkoittaa, että jokin osa ulostulokoodisanasta sisältää syöttötiedot alkuperäisessä muodossaan.
- Reed-Solomon-symbolin koko valittiin kahdeksan bittiä, koska suurempien symbolien dekooderit olisi vaikea toteuttaa nykytekniikalla. Tämä suunnitteluvalinta pakottaa pisimmän koodisanan pituudeksi 255 symbolia.
- Normaali (255, 223) Reed-Solomon-koodi pystyy korjaamaan enintään 16 Reed-Solomon-symbolin virhettä kussakin koodisanassa. Koska kukin symboli on itse asiassa kahdeksan bittiä, tämä tarkoittaa, että koodi voi korjata jopa 16 lyhyttä virhepätkää, jotka johtuvat sisäisestä konvoluutiodesektorista.
Reed-Solomon-koodi on konvoluutiokoodin tavoin läpinäkyvä koodi. Tämä tarkoittaa sitä, että jos kanavasymbolit on käännetty jossain vaiheessa, dekooderit toimivat edelleen. Tulos on alkuperäisen datan komplementti. Reed-Solomon-koodi menettää kuitenkin läpinäkyvyytensä, jos käytetään virtuaalista nollatäyttöä. Tästä syystä on pakollista, että datan merkitys (ts. tosi tai täydennetty) ratkaistaan ennen Reed-Solomon-dekoodausta.
Voyager-ohjelman tapauksessa R-S-koodit saavuttavat lähes optimaalisen suorituskyvyn, kun ne yhdistetään (7, 1/2) konvoluutiokoodin (Viterbi) kanssa. Koska jokaista korjattavaa virhettä kohti tarvitaan kaksi tarkistussymbolia, saadaan koodisanaa kohti yhteensä 32 tarkistussymbolia ja 223 informaatiosymbolia.
Lisäksi Reed-Solomon-koodisanat voidaan lomittaa symbolikohtaisesti ennen konvoluutiokoodausta. Koska näin koodisanan symbolit erotetaan toisistaan, on epätodennäköisempää, että Viterbi-dekooderin purske häiritsee useampaa kuin yhtä Reed-Solomon-symbolia yhdessä koodisanassa.
Perusajatus
Reed-Solomon-koodin keskeinen idea on, että koodattu tieto esitetään ensin polynomina. Koodi perustuu algebran lauseeseen, jonka mukaan k eri pistettä määrittää yksikäsitteisesti enintään k-1-asteisen polynomin.
Lähettäjä määrittää äärellisen kentän yli k - 1 asteen {\displaystyle k-1}
polynomin, joka edustaa k {\displaystyle k}
datapistettä. Polynomi "koodataan" sen jälkeen arvioimalla se eri pisteissä, ja nämä arvot ovat se, mitä todella lähetetään. Lähetyksen aikana jotkin näistä arvoista voivat korruptoitua. Tämän vuoksi lähetetään todellisuudessa enemmän kuin k pistettä. Kunhan tarpeeksi monta arvoa vastaanotetaan oikein, vastaanottaja voi päätellä, mikä alkuperäinen polynomi oli, ja purkaa alkuperäisen datan.
Samaan tapaan kuin käyrää voidaan korjata interpoloimalla aukon ohi, Reed-Solomon-koodi voi kuroa umpeen sarjan virheitä tietolohkossa ja palauttaa alkuperäisen käyrän piirtäneen polynomin kertoimet.
Historia
Koodin keksivät vuonna 1960 Irving S. Reed ja Gustave Solomon, jotka kuuluivat tuolloin MIT:n Lincolnin laboratorioon. Heidän uraauurtava artikkelinsa oli nimeltään "Polynomial Codes over Certain Finite Fields". Kun artikkeli kirjoitettiin, digitaalitekniikka ei ollut vielä tarpeeksi kehittynyttä käsitteen toteuttamiseksi. Ensimmäinen RS-koodien sovellus massatuotteissa vuonna 1982 oli CD-levy, jossa käytetään kahta lomitettua RS-koodia. Elwyn Berlekamp ja James Massey kehittivät tehokkaan dekoodausalgoritmin suurten etäisyyksien RS-koodeille vuonna 1969. Nykyään RS-koodeja käytetään kiintolevyissä, DVD-levyissä, televiestinnässä ja digitaalisten lähetysten protokollissa.
