Kimmo Kujala 42933P
Juha Leino 47032J

Virheiden käsittely tietoliikenteessä

Sisällysluettelo

Esittely
Motivaatio
1. Virheiden syyt
2. Virheiden käsittely
2.1 Backward error control
2.2 Forward error control
3 Virheiden havaitseminen
3.1 Parillisuustarkastus
3.1.1 Yksinkertainen pariteetti
3.1.2 Pariteettitaulu
3.2 Syklinen tarkistuskoodi
4. Virheiden korjaus
4.1 Toistokoodaus
4.2 Hamming koodaus
4.3 Konvoluutio koodaus
4.4 Reed-Solomon koodaus
4.5 Golay forward error control correction

Esittely

Digitaalisessa tiedonsiirrossa siirrettävä tieto esitetään binäärisessä muodossa, eli sarjana ykkösiä ja nollia. Koska digitaalista siirtotietä ei ole olemassa, joudutaan tieto aina välittämään analogisena signaalina, esimerkiksi radioaaltoina tai jännitetasoina. Tiedonsiirtovirheiksi kutsutaan tilannetta, jossa epäideaalisuuksista ja muista syistä johtuen välitettävä signaali ei kulje muuttumattomana lähettäjältä vastaanottajalle, jolloin sen sisältämä digitaalinen tieto tulkitaan väärin tai sitä ei pystytä tulkitsemaan lainkaan. Erilaisilla virheenkäsittelymenetelmillä siirtovirheitä pystytään havaitsemaan ja niistä voidaan toipua.

Motivaatio

Virheenkäsittelyn tarpeellisuus riippuu täysin tiedonsiirron sovelluskohteesta. Joissain tilanteissa virheetön siirto on välttämätöntä kun taas toisaalla virheenkäsittelyä ei tarvitse suorittaa lainkaan. Olennaisimmat tekijät virheenkäsittelystä päätettäessä ovat siirretyn tiedon laatu, siirtämisen suorituskykyvaatimukset sekä siirtotien ominaisuudet. Siirrettävä tieto voi asettaa virheenkäsittelylle erilaisia kriteereitä koskien muun muassa virheiden määrää, tiedonsiirtonopeutta tai yhteyden viivettä. Esimerkiksi ohjelmatiedostoja siirrettäessä virheettömyys on välttämätöntä, mutta toisaalta siirron nopeus ei ole kriittistä. Vastaavasti musiikin tai videon reaaliaikainen siirto internetissä asettaa minimivaatimukset yhteyden nopeudelle ja viiveelle, mutta kohtuullinen määrä virheitä on hyväksyttävissä ilman lähetyksen laadun merkittävää laskua.

1. Virheiden syyt

Eri siirtoteiden fyysiset ominaisuudet vaihtelevat suuresti. Tavat joilla signaali voi siirron aikana muuttua ja näin aiheuttaa tiedonsiirtovirheen voidaan siirtotiestä riippumatta yleistää tiettyihin perustyyppeihin. Kaikki fyysiset häiriöt lisääntyvät siirtotien pituuden kasvaessa.

Signaali vaimenee (attenuation), jolloin sitä on vaikeampi tulkita. Vaimenemista tapahtuu aina, erityisesti sitä aiheuttavat rakenteelliset virheet siirtotiessä ja komponenteissa.

Signaali vääristyy (distortion). Yleisin syy tähän on siirtotien epäyhtenäinen taajuusvaste signaalissa esiintyville taajuuskomponenteille johtuen hajakapasitanssista tai induktanssista. Eri taajuiset signaalikomponentit kulkevat siirtotien läpi eri viiveillä tai niiden amplitudi vaimenee epätasaisesti. Tällöin vastaanotettava kokonaissignaali on vääristynyt.

Signaaliin summautuu häiriöitä (interference) kuten siirtotien valkoista kohinaa tai muita ulkoisia häiritseviä tekijöitä kuten rinnakkaisten kaapelien interferenssi, elektromagneettinen pulssi ja heijastumat.

Virheitä voi syntyä myös muualla kuin itse siirtotiessä. Esimerkiksi mobiilipuhelimissa tehon säästämiseen käytettävä epäjatkuvan lähetyksen (DTX) voice activity detection-ominaisuus voi tulkita käyttäjän puheen taustahuminaksi ja lopettaa lähetyksen, jolloin vastaanottaja kuulee puheen katkeilevana. Tässä tapauksessa sovelluskerrokselta tiedonsiirtoa ohjaavan komponentin voidaan ajatella aiheuttavan systemaattista tiedonsiirtovirhettä.

2. Virheiden käsittely

Virheiden käsittelyllä tarkoitetaan virheiden havaitsemista ja niiden korjausta. Virhe täytyy aina ensin havaita ennen kuin se voidaan korjata. Virheiden käsittely voi tapahtua kahdella tavalla; havaittaessa virhe pyydetään lähettäjää tekemään uudelleenlähetys (BEC), tai havaittaessa virhe pyritään korjaamaan se itse (FEQ). Käytännön tiedonsiirrossa sovelletaan yleensä jonkinlaista hybridiä edellä mainituista. Näiden optimaalinen tasapaino tiedonsiirtojärjestelmässä riippuu sovelluskohtaisista vaatimuksista ja siirtoreitin ominaisuuksista kuten tiedonsiirtonopeudesta ja -viiveestä. Esimerkiksi jos viive on lyhyt, mutta nopeus pieni, voi uudelleenlähettämiseen nojautuva menetelmä tuottaa paremman suorituskyvyn kuin virheenkorjaukseen perustuva.

Virheenkäsittely johtaa aina suorituskyvyn laskuun tiedonsiirtonopeuden tai -viiveen suhteen, sillä virheenkäsittely vaatii redundanttia dataa varsinaisen siirrettävän tiedon lisäksi. Virheiden käsittely voidaan tehdä joko software- tai hardware tasolla. Nykyään suuntaus näyttää olevan kohti hardwarea ja ASIC piirejä, joissa yhdistyvät hardwaren nopeus ja softwaren

2.1 Backward error control

Toimii siten, että lähetettävään dataan lisätään riittävästi redundanttia dataa, jonka avulla virheet voidaan havaita. Vastaanottaja pyytää sitten lähettäjää tekemään uudelleenlähetyksen (ARQ - Automatic Repeat Request) johonkin osaan dataa. Vaatii 2-suuntaisen siirtotien. On olemassa 3 tyyppistä ARQ:ia:

Idle RQ : lähetetään paketti ja odotetaan että vastaanottajalta tulee ACK enenkuin lähetetään uusi paketti. Jos vastaanottajalta tulee NACK, tai ei tule mitään (Timeout), lähetetään sama paketti uudestaan. Ratkaisu on yksinkertainen, mutta aikaa tuhlaava.
Go-back-N : Lähettäjällä lupa lähettää tietty ikkunakoko dataa ennenkuin vaaditaan kuittauksia. Paketteihin merkitään juokseva numero. Vastaanottaja ilmoittaa mihin pakettiin asti lähetykset hyväksyttiin, jolloin niitä vastaava tila vapautuu lähettäjän ikkunassa. Esimerkiksi TCP toimii tällä periaatteella. (window size on 5 pakettia. lähettäjä lähettää paketit 1,2,3,4,5 eikä voi siis lähettää kerralla enempää. vastaanottaja sai kaikki paketit kunnossa, se vastaa että ACK-5. lähettäjä jatkaa lähettämällä paketit 6,7,8,9,10. vastaanottaja huomaa paketissa 8 virheen ja vastaa REJ 8. lähettäjä lähettää seuraavaksi paketit 8,9,10,11,12 jne).
Selective reject : lähettäjä lähettää paketteja tietyn ikkunakoon puitteissa. Vastaanottaja ilmoittaa lähettäjälle niistä paketeista joissa havaittiin virhe, lähettäjä lähettää valikoivasti uudestaan vain ne, joissa oli virhe. Käytännössä tämä on osoittautunut liian raskaaksi ja vaikeaksi toteuttaa.

Erilaisia virheenhavaitsemismenetelmiä esitellään kohdassa 3. Virheiden havaitseminen.

2.2 Forward error control (FEQ)

Dataan lisätään riittävästi redundanttia tietoa, jotta vastaanottaja voi sen perusteella havaita ja korjata siirrossa tapahtuneita virheitä. Tämä on käytännöllinen erityisesti jatkuva-aikaisissa sovelluksissa, jossa dataa ei haluta lähettää uudestaan (kuva/ääni). Erilaisia FEQ korjausmenetelmiä esitellään kohdassa 4. Virheiden korjaus.

3. Virheiden havaitseminen

3.1 Parillisuustarkistus

3.1.1 Yksinkertainen pariteetti

Parillisuustarkistus on yksinkertaisin virhesuojausmenetelmä. Jos ykkösten määrää sanassa nimitetään sanan painoksi, sana on parillinen jos sen paino on parillinen luku.
Sanan loppuun lisätään pariteettibitti merkitsemään tätä. Ei kovin käyttökelpoinen koska virheitä ei tietysti usein havaita.

3.1.2 Pariteetti taulu

Data asetetaan tauluun ja lasketaan rivelille ja sarakkeille pariteetti. Tarjoaa yksinkertaisen tavan virheen paikantamisen taulussa. Käytännössä kuitenkin koko taulu lähetetään yleensä uudestaan jos löydetään virhe. Kyseessä on ns. lohkotarkistus, jossa lohkoon dataa lisätään ylimääräinen tarkistuslohko, jota vastaanottaja voi verrata dataan ja havaita poikkeaman mikäli virhe on tapahtunut.

1 0 0 1
1 0 1 0
0 1 0 1
1 0 0 1
0 1 1 0
1 0 0 0

3.2 Syklinen tarkistuskoodi (CRC)

CRC:n periaate on, että jokaiselle koodisanalle lasketaan tarkistussumma erityisen generaattoripolynomin avulla. Lähetettävä sana jaetaan generaattoripolynomilla ja saatu jakojäännös on tarkistussumma. Yhdessä raamissa lähetetään data+crc. Generaattoripolynomi on valittava huolellisesti jotta menetelmä toimisi hyvin. Kansainvälisen standardin saavuttaneita polynomeja ovat mm:

CRC-12=x^12+x^11+x^3+x^2+x^1+1
CRC-16=x^16+x^15+x^2+1
CRC-CCITT=x^16+x^12+x^5+1

32 bittinen CRC on jo äärimmäisen varma (99.99999998%), sen avulla huomataan melkein varmasti kaikki virheet. 64 bittinen CRC on käytännössä täysin varma.

Esimerkki CRC:n laskemisesta generaattoripolynomilla x^4+x+1 (10011) datalle 1010110.

      ***********1011000
      *******___________
      *10011/10101100000
      *******10011
      *******----
      ********01101
      ********00000
      ********----
      *********11010
      *********10011
      *********----
      **********10010
      **********10011
      **********----
      ***********00010
      ***********00000
      ***********----
      ************00100
      ************00000
      ************----
      *************01000
      *************00000
      *************----
      **************1000<----CRC

Eli lähetetään frame: (data+crc) 10101101000

Shift-Register menetelmä tuottaa CRC:n siirtämällä bittejä vasemmalle ja summaamalla niitä generaattoripolynomin mukaisesti. Hyvin helppo ja tehokas toteuttaa matalalla softatasolla (asm).

4. Virheiden korjaus

4.1 Toistokoodaus

Lähetetään jokainen lähetettävä bitti monistettuna. Vastaanottaja päättelee bitin arvon sen perusteella, mitä arvoa monistetussa lohkossa on eniten. Menetelmä on tehoton ja epävarma, mutta hyvin yksinkertainen toteuttaa.

4.2 Hammingin koodi

Hamming koodaus on laajasti käytetty lohkokoodausmenetelmä. Siinä koodisana saadaan kertomalla lähdesana erityisella generaattori matriisilla, tarkemmin sanottuna sen transpoosilla. Generaattori G matriisin alkuosa on yksikkömatriisi I ja jäljellejäävä osa P tuottaa redundanssin osan. Vastaanotettu sana kerrotaan parillisuustarkistusmatriisilla H=[P;I]', jolloin saadaan oirevektori eli syndrooma. Mikäli tämä poikkeaaa nollavektorista, todetaan virheen tapahtuneen. Virheen korjaus perustuu oirevektorin, parillisuustarkistusmatriisin ja tuntemattomän häiriövektorin muodostavan yhtälön ratkaisemiseen.

Hammingin koodilla tarkoitetaan yleensä hamming(7,4) koodia, jossa lohkon pituus on 4 bittiä ja koodisanan pituus 7 bittiä, eli 3 bittiä käytetään redundanttiin tietoon. Tällä koodilla kyetään korjaamaan yhden bitin virheet, mutta runsaasti virheitä sisältävällä jaksolla koodaus on tehoton.

4.3 Konvoluutio koodaus

Lohkokoodeissa jokainen lohko on riippumaton muista lohkoista. Konvoluutiokoodauksessa koodisanat riippuvat sekä senhetkisestä lähetettävästä datasta, että aiemmin lähetetystä datasta. Konvoluutiokoodaaja sisältää siirtorekisterin, jota siirretään aina lisättäessä uusi bitti. Siirtorekisterin pituus on kooderin pituusraja, eli se on ainoa koodaukseen käytetty muistialue. Uusi bitti koodataan rekisterissä olevien bittien kanssa käyttäen mod-2 yhteenlaskuja. Kovoluutiomallissa ei voida tarkasti sanoa, että esimerkiksi jokainen yhden bitin virhe lohkossa tulee korjattua, vaan ainoastaan, että keskimääräisesti tietty osuus bittivirheitä onnistutaan pitkällä aikavälillä korjaamaan. Tässä menetelmässä dekoodaus on huomattavasti hankalampaa kuin koodaus ja siinä käytetään ns. Viterbin algoritmia.

Myös konvoluutiokoodaus on altis virhepurskeille. Tehokkaaksi menetelmäksi on havaittu konvoluutiokoodauksen ja lohkokoodauksen (vrt hamming koodi) yhdistäminen, jolloin purskeiset virhejaksot kyetään hallitsemaan paremmin.

4.4 Reed-Solomon koodaus

Reed-Solomon forward error correction with interleaving on forward error control menetelmä, joka on tarkoitettu käytettäväksi korkeatasoisissa videoyhteyksissä. Koodauksessa käytetään taulukkoa, joka koostuu 128*47 oktetista. Joka rivillä on 124 dataoktettia ja 4 oktettia redundanttia tarkistusdataa. Koodaus tehdään täyttämällä taulukko sarakkeittain 47 oktettia kerrallaan. Kun tämä on toistettu 124 kertaa, taulukko on täysi ja redundantit oktetit lasketaan rivi kerrallaan.

Tämä menetelmä mahdollistaa kahden solun korjaamisen tai neljän solun uudelleenrakentamisen. Koodatessa tarvitaan kahta lomituspuskuria, koska yhtä puskuria voidaan samanaikaisesti vain joko lukea tai kirjoittaa. Myös enkoodatessa tarvitaan kahta puskuria samasta syystä. Enkoodatessa kirjoitetaan rivi kerrallaan. Kun taulukko on täynnä, suoritetaan mahdollinen virheenkorjaus ja luetaan taulukko sarakkeittain.

Menetelmän haittapuolena sekä koodaus että enkoodaus aiheuttavat tiedonsiirtoon ylimääräisen viiveen, jonka pituus vastaa yhden puskurin siirtoon kuluvaa aikaa. Tämä koodaus ei korjaa kaikkia virheitä, mutta se turvaa laadukkaan siirron reaaliajassa. Voyager II kuvat lähetettiin käyttäen tätä Reed-Solomon koodausta.

4.5 Golay forward error correction

Golay-koodit ovat lohkokoodeja, jotka sallivat lyhyet koodisanat. Täydellinen Golay-koodi koodaa 12 bittiä 23 bitiksi ja siitä käytetään merkintää (23,12). Se mahdollistaa enintään kolmen bitin korjaamisen.
Laajennettu Golay-koodi sisältää ylimääräisen pariteettibitin, joka mahdollistaa enintään neljän bitin virheen havaitsemisen. Koodia merkitään (24,12) ja sitä kutsutaan myös nimellä half-rate golay.

Dekoodaus voidaan suorittaa käyttäen joko kovia tai pehmeitä päätöksia. Pehmeitä päätöksiä käyttämällä saavutetaan parempi virheenkorjaus, mutta kulutetaan enemmän prosessointitehoa. Golay-koodit soveltuvat sovelluksiin, jotka vaativat pientä latenssia ja lyhyttä koodisanan pituutta. Tämän vuoksi niitä käytetään reaaliaikasovelluksissa sekä radioliikennöinnissä.

Tämä sivu on tehty Teletekniikan perusteet -kurssin harjoitustyönä.
Sivua on viimeksi päivitetty 08.12.2000 10:29
URL: http://www.netlab.tkk.fi/opetus/s38118/s00/tyot/37/index.shtml.html