|
|
VIRHEIDEN KORJAUS
|
|
Kun virhe on havaittu, se täytyy korjata mikäli se on
mahdollista.
Virheiden korjaukseen on olemassa useita menetelmiä. Virheiden
korjausmenetelmät voidaan kuitenkin jakaa kahteen ryhmään:
uudelleenlähetys (retransmission) ja suora virheenkorjaus (forward error
correction).
|
|
Uudelleenlähetys
|
|
Uudelleenlähetys on yksinkertainen, halpa, tehokas ja
yleisesti käytetty
virheenkorjausmenetelmä. Uudelleenlähetyksessä on käytännössä kyse siitä,
että vastaanottaja virheen havaittuaan pyytää lähettäjää lähettämään
virheen sisältäneen viestin uudelleen niin kauan kunnes viesti on tullut
virheettä perille. Uudelleenlähetys on hyvä ratkaisu virheenkorjaukseen
silloin, kun alkuperäisestä tiedosta ei ole selkeää käsitystä. Menetelmä
toimii myös silloin, kun lähettäjä ylikuormittaa vastaanottajaa, jolloin
osa viesteistä voi hukkua.
Uudelleenlähetysmenetelmistä käytetään usein myös ilmaisua Automatic
Repeat reQuest (ARQ). ARQ mentelmät voidaan toteuttaa useilla tavoilla.
Seuraavassa esitetään yleisiä periaatteita kuinka ARQ voidaan toteuttaa.
Stop And Wait ARQ
Stop And Wait ARQ:ssa lähettäjä odottaa jokaisen lähetetyn viestin jälkeen
vastaanottajan vaustausta. Vastaanottaja lähettään kuittauksen
(acknowledgment, ACK), jos viesti tuli perille virheettä, tai negatiivisen
kuittauksen (negative acknowledgment, NAK) virheellisen viestin
tapauksessa. Jos vastaus on NAK, lähettäjä lähettää viestin uudelleen.
Uudelleen lähetys tapahtuu myös, jos kuittausta ei saada jonkin ajan
kuluessa. Muutoin lähettäjä siirtyy seuraavaan viestiin.
Stop And Wait ARQ on yksinkertainen menetelmä ja helppo toteuttaa, mutta
sen ongelma on tehottomuus.
Go Back N ARQ
Tässä menetelmässä lähettäjä lähettää viestejä odottamatta vastausta
jokaisesta viestistä erikseen. Vastaanottaja tulkitsee viestit ja lähettää
ACK:n kyseisestä viestistä, jos se saapui perille ongelmitta. Jos taas
viestissä oli virhe tai sitä seuraava viesti saapui ensin, lähettää
vastaanottaja NAC:n ja hylkää kaikki virheellisen viestin jälkeet
saapuneet viestit. Lähettäjä NAC:n saatuaan lähettää virheellisen viestin
uudelleen ja myös kaikki sen jälkeen jo kertaalleen lähetetyt viestit.
Tällä menetelmällä päästään huomattavasti parempaan tehokkuuteen kuin Stop
And Wait ARQ:ssa ja se onkin yleisesti käytetty mentelmä.
Selective Reject ARQ
Selective Reject ARQ on samantapainen mentelmä kuin Go Back N ARQ, mutta
siinä lähetetään uudelleen vain vialliset viestit. Tällä päästään
parempaan tehokkuuteen, mutta sen toteutus on huomattavasti
monimutkaisempaa kuin Go Back N ARQ:n ja se asettaa laitteistolle enemmän
vaatimuksia. Go Back N ARQ onkin siten huomattavasti enemmän käytetty
mentelmä.
|
|
Suora virheenkorjaus
|
|
Joissakin tapauksissa ei tiedon uudelleenlähetys tule kysymykseen
esimerkiksi reaaliaika vaatimusten vuoksi. Tällöin vastaanottajan on
tavalla tai toisella määritettävä mikä viestin oikea sisältö on. Jotta
virhetapaukset voidaan korjata, on lähettävään tietoon sisällytettävä
ylimääräistä tietoa. Nämä ylimääräiset bitit ovat useimmiten myös osa
virheen tunnistusta.
Mitä enemmän korjaustietoa viestiin laitetaan, sitä paremmin virheet
voidaan periaatteessa korjata. Mutta liika lisäys tuo enemmän herkkyyttä
häiriöille ja vähentää tehokkuutta ja siten virheiden todennäköisyys
kasvaa. Tämän vuoksi korjattavien virheiden määrä on rajoittunut.
Lohkokoodit (Block codes)
Suoran virheenkorjauksen menetelmien perustana ovat niin sanotut
lohkokoodit (block codes) ja niiden eri variaatitot. Lohkokoodien
ideana on,
että lähetettävä data (viesti, paketti) jaetaan k:n bitin kokoisiin
osiin. Nämä lohkot syötetään kooderiin, joka muuttaa ne n-bitin
kokoisiksi, siten että jokaiselle erilaiselle k :n bitin pituiselle
jonolle on olemassa vain yksi n -bitin jono. Tämä voidaan ilmaista (n,k)
lohkokoodina. Esimerkiksi (15,11) lohkokoodi tarkoittaa 15 bitin
koodisanaa, johon lisätään 4 bittiä tarkistusinformaatiota.
Vastaanottaja päässä koodisanoille lasketaan tarkistusbitit uudelleen ja
verrataan niitä vastaanotettuihin. Jos eroja ilmenee, vastaanottaja
päättelee todennäköisimmän vastineen virheelliselle koodisanalle. Mikäli
päättelyä ei voi suorittaa, voi vastaanottaja pyytää uudelleen lähetystä.
Lohkokoodien variaatioista mainittakoon Cyclic koodit ja Reed -
Salomon koodit, joita voidaan käyttää myös tallenteiden tiedon korjaamiseen,
esimerkiksi CD-levyjen ja kovalevyjen virheen korjaus perustuu Reed
-Salomon koodeihin.
|
|