TKK | Tietoverkkolaboratorio | Opetus

Miten virheitä korjataan

Sisällys: Virheen lähteet Virheen havaitseminen Parillisuustarkistus Lohkotarkistukset Tarkistussumma Syklinen tarkistus Virheen korjaus ja uudelleen lähetys Forward error control Hammingin koodi Konvoluutio koodit Backward error control Idle RQ Continuous RQ

1.Virheen lähteet Ideaalisessa siirtotiessä ei tapahdu mitään virheitä, mutta kuten harva tässä maailmassa on ideaalista eivät myöskään siirtotiet ole ideaalisia. Signaalit ovat alttiita monille häiriöille matkatessaan siirtotiellä. Yleensä signaalin amplitudi pienenee siirtotiellä, mitä kutsutaan vaimenemiseksi. Jos signaali vaimenee liikaa sitä ei pystytä havaitsemaan. Signaalin muoto voi myös muuttua, jos siirtotiellä oleva viive ei ole lineaarinen. Tällöin eri taajuuskomponentit saapuvat vastaanottimelle eri järjestyksessä kuin mitä ne lähetettiin ja vastaanotettu sanoma vääristyy. Siirtotiellä voi ilmetä myös häiritsevää interferenssiä. Interferenssissä siirtotiestä riippuen joko rinnakkaisesta kaapelista tai läheisestä radiolähettimestä tulee häiritsevää signaalia, joka summautuu lähetettävään signaaliin aiheuttaen virhettä. Radioaaltoja käytettäessä voi esiintyä monitie-etenemistä, jossa signaali interferoi itsensä kanssa.Yleensä myös itse siirtotiessä esiintyy eri tyyppisiä kohinoita esim. valkoista kohinaa. 2.Virheen havaitseminen 2.1 Parillisuustarkistus Parillisuustarkistus on yksinkertaisin virheen havaitsemismenetelmä. Ylimääräinen bitti, ns pariteettibitti, lisätään lähetettävään lähdesanaan. Pariteettibitti on joko 0 tai 1 riippuen onko merkin ykkösten määrä, eli paino, parillinen vai pariton. Jos käytetään parillista pariteettia ykkösten määrä on aina parillinen ja parittomassa pariteetissa ykkösiä on aina pariton määrä. Näin saadun koodisanan purkaminen takaisin lähdesanaksi tapahtuu yksinkertaisesti tarkistamalla koodisanan parillisuus tai parittomuus ja poistamalla ylimääräinen bitti. Pariteettibitin avulla voidaan koodisanasta havaita vain pariton määrä virheitä ja luotettavasti vain yhden virheen. Pariteettitarkistusta käytetään merkkipohjaisessa tiedonsiirrossa. 2.2 Lohkotarkistukset Lohkotarkistukset ovat myös yksinkertaisia virheenhavaitsemismenetelmiä. Siinä data jaetaan lohkoihin ja jokaiseen lohkoon lisätään tarkistusbittejä lohkon perään. Vastaanottaja suorittaa vastaavan tarkistusoperaation ja vertaa tulosta vastaanotettuhin tarkistusbitteihin. Jos nämä eroavat toisistaan voidaan päätellä virheen tapahtuneen. Koska tarkistusbittejä on vähemmän kuin itse lohkossa, useilla eri lohkoilla voi olla samat tarkistusbitit. Joten usean bitin pituinen virhepurske voi vääristää oikean lohkon vääräksi lohkoksi, jolla on samat tarkistusbitit. Tällöin virhe jää havaitsematta. Tämän todennäköisyyttä voidaan pienentää käyttämällä tehokkaampaa tarkistusalgoritmia ja enemmän tarkistusbittejä. 2.2.1 Tarkistussumma Lohkotarkistussumma (BCS, Block check sum) on periaatteessa kehittyneempi versio pariteettibitin laskemisesta. Siinä lohkon kaikki merkit summataan biteittäin yhteen ja saatu tarkistussummamerkki (BCC, Block check character) lisätään lohkon perään. Tarkistussumman laskeminen on hyvin helppoa ja se voidaan suorittaa pelkällä ohjelmistolla. Mutta huonona puolena on, että useiden virheiden havaitseminen ei ole kovin luotettavaa. [1] 2.2.2 Syklinen tarkistus Syklinen tarkistus (CRC, Cyclic redundancy check) on kehittynyt vaihtoehto tarkistussummalle. Syklisen tarkistuksen tarkistusbitit generoidaan jakamalla tulevan sanoman bittijono muodostajapolynomilla ja sijoittamalla tarkistubiteiksi saatava jakojäännös. Jakojäännös on yhden bitin lyhyempi kuin itse muodostajapolynomi. Muodostajapolynomin pituudella pystytään määrittämään kuinka monta virhettä sillä pystytään havaitsemaan ja sen valitsemisessa tarvitsee olla huolellinen. Syklistä tarkistusta käytään hyvin paljon tietoliikenteessä virheiden havaitsemiseen. Sen laskeminen on hankalampaa kuin lohkotarkistuksen ja se voidaan toteuttaa sekä laitteistolla että ohjelmistolla. Yleisesti voidaan sanoa, että syklisellä tarkistuksella pystytään havaitsemaan kaikki yhden bitin virheet ja virheet joiden lukumäärä on pienempi kuin muodostajapolynomin pituus. Lisäksi voidaan havaita useimmat virhepurskeet. Yleisin muodostajapolynomi on CCITT:n CRC-16, jossa polynomi on 16 bitin pituinen. Sillä voidaan havaita siis kaikki 16 bitin virheet ja myös pidemmän virhepurskeen havaitseminen on mahdollista. CRC-32 on riittävä useimpiin nykyajan tietoliikenteen sovelluksiin. 3. Virheen korjaus ja uudelleen lähetys Virheenkorjauksen tarkoituksena on havaitun virheen jälkeen saada alkuperäinen data virheettömäksi. Tähän on käytössä kaksi erilaista lähestymistapaa: forward error control (FEC) ja backward error control. FEC eli eteenpäin suuntautuvassa virheenkorjauksessa dataan lisätään niin paljon ylimääräisiä bittejä, että useimmat virheet voidaan havaita ja korjata luotettavasti. Backward error control eli taaksepäin suuntautuvassa virheenkorjauksessa dataan lisätään vain sen verran bittejä, että virheelliset paketit voidaan havaita. Nämä virheelliset paketit täytyy lähettää uudelleen ja tämän varmistamiseksi on useita eri metodeja. 3.1 Forward error control Käytettäessä FEC metodia tarvitaan vain yksisuuntainen siirtokanava. Virheenkorjauksen mahdollistaa dataan lisättävät ylimääräiset bitit joiden avulla pystytään havaitsemaan ja korjaamaan virheet. Huonona puolena tästä on, että siirtotehokkuus pienee, kun joudutaan laittamaan paljon tarkistusbittejä. Etuna on että FEC toimii jatkuvasti ilman viiveen muutoksia, mikä on tärkeää siirrettäessä reaaliaikaista dataa esim. ääntä. On kehitetty useita koodeja joilla pystytään toteuttamaan FEC metodi, yleisimpiä ovat lohkokoodit ja konvoluutio koodit. 3.1.1 Hammingin koodi Hammingin koodi kuuluu lohkokoodeihin ja siinä lähdesana koodataan koodisanaksi kertomalla se muodostajamatriisin kanssa. Se on myös systemaattinen eli muodostajamatriisin alkiot on valittu siten, että koodisanan alkioista voidaan suoraan lukea tarkoitettu lähdesana. Vastaanotossa koodisanat kerrotaan parillisuusmatriisin kanssa. Jos tulo on nolla, virhettä ei ole ja koodisana voidaan muuttaa normaalisti lähdesanaksi. Jos tulo eroaa nollasta, saadaan aikaiseksi oirejono, josta voidaan päätellä virheen paikka ja korjata virhe. Koodin virheiden korjaamiskykyyn pystytään vaikuttamaan kasvattamalla muodostajamatriisia eli samalla myös koodisanan pituutta. Bittipaikkojen määrää, joissa koodisanat eroavat toisistaan sanotaan Hammingin etäisyydeksi. Virheet, joiden lukumäärä on pienempi kuin Hammingin etäisyys pystytään havaitsemaan. Joten koodin Hammingin etäisyyden pitää olla suurempi kuin virheitten määrä. Jos virheitä on n kappaletta, tarvitaan havaitsemiseen koodi, jonka Hammingin etäisyys on n+1. Korjaamiseen vaadittava etäisyys on 2*n+1. 3.1.2 Konvoluutio koodit Lähdesanat voidaan koodata koodisanoiksi niin, että koodisana riippuu edellisistä lähdesanoista. Eli jokainen lähetettävä bitti riippuu koodattavasta bitistä ja aikaisemmin koodatuista biteistä. Kyse on muistillisesta prosessista ja operaatio voidaan toteuttaa yksikertaisesti siirtorekistereillä. Dekoodauksessa on tarkoituksena päätellä todennäköisin lähetetty lähdesana vastaanotetusta koodisanasta. Siinä vertaillaan vastaanotettua koodisanaa kaikkiin mahdollisiin koodisanoihin ja valitaan se jonka Hammingin etäisyys on pienin. Menetelmää kutsutaan Viterbi algoritmiksi. 3.2 Backward error control Käytettäessä backward error controllia pitää olla kaksisuuntainen siirtoyhteys, jolloin vastaanottaja voi pyytää datan uudelleenlähettämistä. Lähettäjä ensin jakaa datan lohkoiksi ja lisää käytettävän virheenhavaitsemiskäytännön mukaiset tarkistusbitit lohkoihin. Vastaanottaja suorittaa virheentarkistuksen. Jos se huomaa virheen tapahtuneen, se pyytää lähettäjää lähettämään virheellisen paketin uudestaan. Mekanismi tunnetaan ARQ:na (Automatic repeat request). ARQ avulla voidaan aina varmistaa virheellisen datan uudelleenlähetys, mutta se aiheuttaa viivettä ja kuluttaa lähetystien resursseja. Käytössä on kaksi perusversiota ARQ:sta ja ne ovat idle RQ ja continuos RQ. Monissa datasiirtoprotokollissa käytetään backward error controllia takaamaan, että saavutetaan virheetön siirto. 3.2.1 Idle RQ Idle RQ on perusversio bacward error menelmästä. Siinä lähettäjä jakaa datansa paketteihin ja lisää tarkistusbitit niihin. Vastaanottaja tarkistaa tarkistusbittien avulla onko virheitä taphtunut siirrossa. Jos virheitä ei ole, lähetetään kuittaussanoma (ACK, acknowledgement) lähettäjälle ja virheen tapauksessa lähetetään negatiivinen kuittaus (NACK) ja hylätään paketti. Jos lähettäjä saa tietyssä ajassa vahvistuksen, se voi lähettää seuraavan paketin ja jos se ei saa vahvistusta tai se saa vastaanottajalta negatiivisen vahvistuksen se lähettää paketin uudestaan. Idle RQ on hyvin yksinkertainen mekanismi, mutta erittäin tehoton virheen uudelleenlähetysmenetelmä, koska lähettää voidaan vain yhteen suuntaan kerrallaan. Tässä menetelmässä kuluu hyvin paljon siirtokapasiteettia siihen, että vain odotellaan vahvistusta lähetyksen onnistumisesta. Menetelmän suorituskyky heikkenee siirtotien viiveen kasvaessa eli esim etäisyyden kasvaessa. 3.2.2 Continuous RQ Voidakseen käyttää Continuos RQ:ta siirtoyhteyden pitää olla duplex-yhteys eli molempien pitää pystyä lähettämään samaan aikaan. Continuos RQ on kehittyneempi versio idle RQ:sta. Siinä lähetettävät paketit numeroidaan, joka mahdollistaa pakettien lähettämisen jatkuvasti odottamatta kuittausta. Vastaanottaja vastaanottaa myös paketteja jatkuvasti ja aina vastaanotettuaan virheettömän paketin se lähettää siitä kuittauksen, joka sisältää vastaanotetun paketin numeron. Jos kuittausta ei tule uudelleenlähetys voidaan hoitaa kahdella eri tapaa. Selektiivisessä lähetyksessä lähetetään vain ne joista ei tule kuittausta tai tulee negtiivinen kuittaus. Tämä vaatii sen, että vastaanottajalla pitää olla jonkinlainen puskurimuisti, jotta paketit saadaan järjestettyä oikeaan järjestykseen. Toinen uudelleen lähetysmenetelmä on ns. go-back-n, jossa virheellisen paketin ilmaannuttua lähetys siirtyy takaisin viimeiseen onnistuneesti kuitattuun pakettiin.Vastaanottaja hylkää kaikki virheellisen paketin jälkeen saamansa paketit ja jää odottamaan uudelleenlähetystä. Tällöin paketit tulevat automaattisesti oikeassa järjestyksessä perille. Selektiivinen uudelleenlähetys on monimutkaisempi toteuttaa, mutta käytännöllisempi jos virheitä tapahtuu usein. [2] Viitteet: [1] Seppo J. Halme: Televiestintäjärjestelmät [2] Fred Halsall: Data communications, computer networks and open systems.

Tekijät:
Ilkka Miettinen
Antti Hassinen
Mikko Malinen