Reed-Solomon-koodit: miten polynomipohjainen virheenkorjaus toimii

Reed–Solomon-virheenkorjaus: miten polynominäytteistä palautetaan data virheistä — käytännön selitys CD/DVD/Blu-ray-, DSL- ja lähetysjärjestelmissä.

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.

Miten Reed–Solomon toimii käytännössä

Perusidea on yksinkertainen ja intuitiivinen: datasta muodostetaan polynomi P(x), jonka aste on pienempi kuin k (datasymbolien määrä). Polynomi arvioidaan n eri pisteessä (eri x-arvoilla) ja saadut arvot muodostavat koodisanan, jonka pituus on n. Vastaanottaja yrittää rekonstruoida alkuperäisen polynomin näiden pisteiden perusteella. Koska pisteitä on enemmän kuin tarvitaan, pieni määrä virheellisiä pisteitä ei estä alkuperäisen polynomin palauttamista.

Teknisesti operaatiot tehdään äärellisessä kentässä, yleensä GF(2^m), eli symbolit ovat tavallisesti tavun (8 bitin) kokoisia kun m = 8. Yleinen merkintä on RS(n, k), jossa n on koodisanan pituus symboleina ja k alkuperäisten datasyMBOLien määrä. Usein pätevä vaatimus on n ≤ 2^m − 1.

Virheenkorjauskapasiteetti

• Virheiden korjaus: Reed–Solomon voi korjata enintään t = floor((n − k) / 2) symbolivirhettä (eli virheellisiä symboleja tuntemattomissa paikoissa).
• Puuttuvien symbolien (erasure) korjaus: Jos vastaanottaja tietää, missä paikoissa symbolit ovat kadonneet tai epäluotettavia, voidaan korjata jopa n − k erasurea.
• Esimerkki: RS(255,223) -koodissa on 32 pariteettisymbolia, joten se voi korjata enintään 16 symbolivirhettä tai 32 tunnetuksi ilmoitettua puuttuvaa symbolia.

Osa-algoritmeja ja toteutus

Rekonstruktion käytännön algoritmeja ovat muun muassa Berlekamp–Massey- ja Eukleideen algoritmi virhesijaintien löytämiseksi sekä Forneyn kaava virheinformaatioiden laskemiseen. Nykyisempiä tai erikoistapauksia ovat Gao-algoritmi ja listadekoodaukseen liittyvät Guruswami–Sudan -menetelmät, jotka voivat löytää useampia ehdokkaita tapauksissa, joissa virheitä on enemmän kuin t.

Käytännössä toteutus vaatii äärellisen kentän laskutoimituksia (lisäys, kertolasku, käänteislasku), jotka on optimoitu taulukoinnilla tai erikoisrutiineilla sulautetuissa järjestelmissä. Monet ohjelmisto- ja laitteistokirjastot tarjoavat valmiita RS-implementaatioita.

Ominaisuudet ja käyttötarkoitukset

• Reed–Solomon on erityisen hyvä käsittelemään symboli- eli ryhmävirheitä, joten se soveltuu erinomaisesti tilanteisiin, joissa virheet tulevat peräkkäisinä "burst"-tyyppisinä, kuten optisissa levyissä tai kanavan kohinan aiheuttamina bittiryppäinä.
• Sitä käytetään laajasti digitaalisessa tallennuksessa ja lähetyksessä: esimerkiksi optisilla levyillä RS-koodit yhdessä interleaving-menetelmien kanssa hajauttavat bittivirheitä, jolloin yksittäiset virheet eivät riko pitkiä tietojaksoja.
• Reed–Solomonin rinnalla käytetään nykyaikaisissa järjestelmissä myös tehokkaampia koodeja (esim. LDPC, turbo-koodit) erityisesti pitkissä blokkikoodeissa ja lähetyksissä, mutta RS pysyy suosittuna kun tarvitaan luotettavaa symbolipohjaista korjausta ja yksinkertaista determinististä käyttäytymistä.

Käytännön esimerkki (yksinkertaistettu)

Ajatellaan kolmesta datasybolista muodostettua polynomia P(x) = a0 + a1 x + a2 x^2 (aste < 3). Arvioidaan tämä polynomi viidessä pisteessä x = 1,2,3,4,5 ja lähetetään arvot. Vastaanottaja saa viisi symbolia, joista korkeintaan yksi voi olla virheellinen. Koska vastaanottaja tarvitsee vain kolme oikeaa pistettä polynomin interpolointiin, hän voi tunnistaa ja korjata yhden virheen ja rekonstruoida alkuperäiset a0,a1,a2.

Rajoituksia ja huomioita

• Reed–Solomon käsittelee symboleja kerrallaan, ei yksittäisiä bittejä — tämä tekee siitä tehokkaan ryppäiden korjauksessa mutta vähemmän tehokkaan erittäin korkean bittivirhesuhteen tilanteissa ilman muita mekanismeja (kuten bittitason koodaus tai interleaving).
• Koodin tehokkuus ja virheenkorjauskapasiteetti riippuvat valituista n ja k -arvoista sekä symbolikentän koosta.
• Suurempi korjauskyky vaatii lisää pariteettisymboleja, mikä kasvattaa ylikuormaa (overhead).

Yhteenvetona Reed–Solomon on vahva ja monipuolinen symbolipohjainen virheenkorjausmenetelmä, joka perustuu polynomien arviointiin ja interpolaatioon äärellisissä kentissä. Se tarjoaa ennustettavan ja tehokkaan tavan korjata sekä satunnaisia että ryppävirheitä ja siksi sitä käytetään edelleen laajalti tallennus- ja tiedonsiirtotekniikoissa.

Hae kirjaimella