|
|
|
|
Virheiden havaitseminen
tiedonsiirrossa
| |
|
Paraskin tiedonsiirtotapa on jossain määrin virhealtis. Kaikkien
tiedonsiirtotapojen äiti, puhuttu kieli, on ehkä paras esimerkki
virhealttiista tiedonsiirrosta. Ellei sanottu ollut valhetta jo
lausuttaessa (kirjoitettassa), ei ole mitään takeita siitä että
vastaanottaja tulkitsisi tiedon oikein. Viimeistään tiedon siirtyessä
suusta suuhun tai paperilta toiselle, sisältö muuttuu enemmän tai vähemmän
epätodeksi tiedon välittäjän ja uuden vastaanottajan tulkinnan mukaan.
Analogisen tiedonsiirron virheiden havaitseminen on hankalaa paitsi
ihmiselle, myös koneille, koska siirretty tieto ei ole yksikäsitteistä.
Siksi keskitymme tässä yhteydessä vain binääriseksi muunnetun,
bittitasolla yksikäsitteisesti tulkittavissa olevan abstraktin tiedon
siirtoon. Bittien yhteydessä on mahdollista määrittää virhe
yksikäsitteisesti ilman analogiseen tiedonsiirtoon liittyvää syvällistä
filosofista pohdintaa siitä, mikä oikeastaan on virhe. Binäärisessä
tiedonsiirrossa virhe on yksinkertaisesti bitin arvon muuttuminen nollasta
ykkökseksi tai päinvastoin.
Vaikka puolikkaista ei tarvitsekaan siis huolehtia, valitettavasti myös
binäärisen tiedon siirrossa virheen todennäköisyys on parhaissakin
olosuhteissa suurempi kuin nolla. Siirrettyjen bittien määrän lähestyessä
ääretöntä lähestyy virheen esiintymisen todennäköisyys yhtä, s.o varmaa
tapahtumaa.
Jotta virheen esiintyessä tiedon eheys säilyisi, on tärkeää pystyä
havaitsemaan virheet ajoissa ja toimimaan tilanteen vaatimalla tavalla.
Tilanteesta riippuen tämä voi tarkoittaa esimerkiksi korjausta,
uudelleenlähetystä tai jopa arvausta.
Virheiden havaitsemiseen on ajan saatossa kehitetty erilaisia menetelmiä.
Niistä vanhin, yksinkertaisin ja yleisimmin tunnettu, on pariteetin
käyttö.
|
|
|
Pariteetti
|
|
Pariteettia muodostettaessa lasketaan tietynkokoisten bittiryhmien
ykkösten määrä ja lisätään jokaisen ryhmän jälkeen tarkistusbitti.
Käytettäessä parillista pariteettia tarkistusbitti valitaan siten, että
bittiryhmän sekä tarkistusbitin ykkösten summa on parillinen. Vastaavasti
paritonta pariteettia käytettäessä tarkistusbitti valitaan siten että
ykkösten summaksi jää pariton luku.
Esim. 7 bittiä dataa ja parillinen pariteetti:
Data Pariteetti
1010101 0
Vastaava parittomalla pariteetilla:
Data Pariteetti
1010101 1
Pariteetista voidaan havaita parittoman virhemäärän esiintyminen. Jos
tiedetään että käytössä on parillinen pariteetti 7 bitin datalohkolle,
lasketaan ykkösten määrä kahdeksalle bitille ja mikäli summa on pariton,
tiedetään että tiedonsiirrossa tapahtui virhe. Vastaavasti toimitaan
käytettäessä paritonta pariteettia.
Pariteetin käytön suurin ongelma on siinä, että parillisia virhemääriä ei
ole mahdollista havaita. Käytännössä tästä on seurauksena se, että
pariteetti soveltuu vain tiedonsiirtoon jossa tapahtuu vain vähän
virheitä.
On myös mahdollista käyttää pariteettia hieman tehokkaammin laskemalla
pariteetti esim. bittitaulukon riveille ja sarakkeille. Käytännön
merkitystä tällä ei juuri ole, koska nykyään pariteettia ei juurikaan
käytetä. On olemassa huomattavasti tehokkaampia
virheenhavaitsemismenetelmiä, kuten tarkistussumma ja
CRC.
|
|
|
Tarkistussumma
| |
Tarkistussummaa käytettäessä ideana on laskea lähetettyjen tavujen (8bit)
summa yhteen ja jakaa luku esimerkiksi luvulla 255. Jakojäännös on
tarkistussumma, joka tiedonsiirrossä lähetetään viimeisenä. Vertaamalla
itse laskemaansa ja siirrettyä tarkistussummaa keskenään, vastaanottaja
voi päätellä tapahtuiko tiedonsiirrossa virheitä.
Data tarkistussumma
46+50+80+13+10=199 (/255) -> 199
Mikäli tiedonsiirrossa tapahtuu virheitä, niiden seurauksena
tarkistussumma muuttuu joksikin arvoksi väliltä 0-255, minkä seurauksena
voidaan sanoa että on 1/256 todennäköisyys että virhe jää havaitsematta.
Äkkiseltään voisi ajatella, että laskemalla tavujen summa isompaan
rekisteriin ja jakamalla isommalla luvulla (esim 2^16) saavutettaisiin
pienempi, 1/ 2^16 todennäköisyys virheen päästä läpi, mutta näin ei ole.
Esim:
Data tarkistussumma
46+50+80+6+17=199 (/2^16) -> 199
46+50+80+10+13=199 (/2^16) -> 199
Yhteenlasku ei yksinkertaisesti ole riittävän satunnainen
menetelmä.
Tyypillisesti tarkistussummalla havaitaan kuitenkin jopa 95% virheistä.
|
|
|
Cyclic Redundancy Check
|
|
Paljon tehokkaampi menetelmä virheiden havaitsemiseen on kuitenkin ns.
CRC-tarkistussumman käyttö.
Myös CRC-tarkistussumma perustuu jakojäännöksen käyttöön tarkistussummana,
mutta se eroaa monelta osin perinteisestä tarkistussummasta. Suurin ero on
siinä että jakojäännöstä ei lasketa siirrettyjen tavujen summasta, vaan
tavuja käsitellään aivan kuin ne olisivat osa valtavaa binäärilukua. Esim.
8 tavun merkkijonoa käsitellään 64 bitin lukuna. Toinen ero on siinä että
jakojäännöstä laskettaessa ei käytetä perinteistä jakolaskua, vaan
normaalista poikkeavaa polynomiaritmetiikkaa. Myöskään nimittäjänä ei
yleensä käytetä pelkästään ykkösiä täynnä olevaa bittijonoa, vaan jotkut
jakajat ovat parempia kuin toiset. Muuten idea vastaa tavallista
tarkistussummaa, eli vastaanottaja laskee CRC-tarkistussumman siirretylle
datalle ja vertaa sitä siirrettyyn tarkistussummaan.
CRC-tarkistussumman tehokkuus riippuu paljolti käytettyjen bittien
lukumäärästä. Käytännössä 8-bitin CRC:llä (jaetaan 8 bittisellä jakajalla,
saadaan 8 bittinen tarkistussumma) havaitaan yli 99.9 prosenttia
virheistä. 16-bitillä havaitaan yli 99.99 prosenttia virheistä.
CRC on tehokkuudestaan johtuen kaikkein yleisin virheiden havaitsemiseen
käytetty menetelmä.
|
|
|