1. (Liisa Marttinen)
a) Kuparikaapelin kaistanleveys on 3000 Hz. Sen signaalikohinasuhde (signal to noise ratio) SNR on 30 dB. Kanavan BER on 10**-5. Mikä on kaapelin suurin teoreettinen tiedonsiirtonopeus, jos yhteen signaalikomponenttiin koodataan 3 bittiä? Esitä tarkoin lausekkein, kuinka lasket kanavan maksimaalisen siirtonopeuden. Anna vastaus niin tarkasti kuin ilman laskinta pystyt. (4p)

a) Tarkastellaan kaapelin teoreettista siirtonopeuden maksimia sekä Nyquistin että Shannonin kaavojen perusteella:

 Nyquist: teoreettinen maksiminopeus = 2*W*P, missä
            W = kaapelin kaistanleveys = 3000 Hz
            P = yhteen signaalikomponenttiin koodattujen bittien määrä = 3
              = log2(erilaisten signaalikomponenttien ('signaalin
                tasojen')määrä) 
          maksimi = 2*3000*3 = 18000 bps 
          
 Shannon: teoreettinen maksiminopeus = W *log2(1+S/N),  missä
           SNR = 10 * log10(S/N) = 30 dB  => log10(S/N)= 3 => 
           S/N = 10**3 = 1000 
          
           maksimi = 3000 *log2(1001)
           2**9 = 512 < 1001 < 2**10 = 1024 => saadaan arvio log2(1001) ~ 10
           maksimi siirtonopeus ~ 3000 *10 = 30000 bps
 
 Näistä Nyquist rajoittaa enemmän, joten maksimaalinen siirtonopeus = 18000
 bps.
 
 BER:llä ei ole mitään tekemistä maksimaalisen siirtonopeuden kanssa.  
 
 Arvostelusta:  maks. siirtonopeus Nyquistin kaavasta => 1 piste
                      kaava => 1/2 p
                      bittien määrä => 1/2 p
                maks. siirtonopeus Shannonin kaavasta => 1 1/2 pistettä
                      kaava => 1/2 p 
                      SNR => S/N =>  1/2 p
                      log2(1001) => 1/2 p
                BER ei sotkettu laskuihin             => 1/2 pistettä
                oikea vastaus, molemmat laskettu ja oikea valittu => 1 piste
                pienet laskuvirheet tai muut erheet => -         
                                  

* muuttaa analogisen signaalin digitaaliseksi => 1/2 p
* käytetään puhelinverkossa => 1/2 p
* tarkempi selvitys toiminnasta ja käytöstä 1/2 - 1 p

CRC (Cyclic Redundancy Check) on polynomeihin perustuva tarkistussumma. Tunnetuimpia CRC menetelmiä on CCITT:n CRC-32, jota käytetään mm. HDLC:ssä ja ZMODEMissa.

CRC laskenta perustuu tekniikkaan, jossa datablokin bitit ovat pitkän polynomin kertoimia. Esimerkiksi heksadesimaalinen tavu F0H on polynomina:
X^7 + X^6 + X^5 + X^4

Polynomien eksponentit eivät haittaa laskentaa, koska niitä ei tarvita tarkistussumman laskennassa. CRC lasketaan jakamalla data toisella yleisesti tunnetulla polynomilla, ns. "generator polynomial" tai G(X). Dataa esittävä polynomi jaetaan G(X):llä, jolloin saadaan tulos ja jakojäännös.

Jakojäännös on lähetettävä tarkistussumma. Sekä lähettäjällä että vastaanottajalla on sama tekniikka ja sama G(x) tiedossa.

Perusideana on että lähetettävä kehys (data + jakojäännös) on jaollinen G(x):llä. Jos vastaanottajan tekemän jakolaskun tuloksena on jakojäännös,kehys sisältää virheitä.

CRC-32:n generator polynomial:
X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+1

CRC lasketaan usein laitteistolla, mutta se saadaan myös tavallisilla pöytäkoneilla nopeaksi käyttämällä hakutauluja. Jakolaskussa käytetään modulo-2 aritmetiikkaa.

Pisteet määräytyivät seuraavasti (suuntaa-antava kuvaus):
1/2p Lasketaan tarkistussumma kaikkien bittien yli ja se lähetetään datan mukana verkon yli.
1/2p tarkistussumma perustuu tunnettuun avaimeen, ja polynomien jakojäännökseen
1p vastaanottaja suorittaa samalla avaimella vastaavan jako-operaation. Virhe on tapahtunut jos jakojäännös ei ole 0.

b) Mikä on Hamming-etäisyys? Mitä vaikutusta sillä on siirtovirheen havaitsemiseen ja korjaukseen? (2 p)

Hamming-etäisyys kertoo kahden bittijonon poikkeavien bittien lukumäärän. Hamming-etäisyys siis kertoo montako yhden bitin bittimuutosta (virhettä) tarvitaan muuttamaan annettu jono toiseksi jonoksi. Kahden jonon Hamming etäisyyden voi kätevästi laskea XOR:lla.

Hamming-etäisyyttä tarvitaan virheen korjaavien koodien rakentamiseen. Koodisana (codeword) on databitit ja tarkistusbitit. Koodisanan pituus on n = m + r. Tiedonsiirrossa kaikki 2**m viestiä ovat mahdollisia, mutta 2**n:stä koodisanasta vain osa on käytössä. Kun tiedetään käytetty algoritmi tarkistusbittien laskemiseen voidaan määrittää lista sallituista koodisanoista.

Koodiston (joukko koodeja) Hamming etäisyys on sen koodien välinen pienin mahdollinen Hamming etäisyys (d). Koodisto havaitsee d virhettä, kun Hamming etäisyys on d+1. Tällöin mikään d bitin virhe ei pysty muuttamaan hyväksyttävää koodisanaa toiseksi hyväksyttäväksi koodisanaksi. Koodisto pystyy korjaamaan d virhettä, jos Hamming-etäisyys on 2d+1. Kyse on redundanssista. Koodeissa on ylimääräistä redundanssia, jolla virheet havaitaan ja pystytään korjaamaan.

1p Hammingin selitys
1p Esitys Hamming-etäisyyden vaikutuksesta virheiden havaitsemiseen - korjaamiseen.

c) Onko mahdollista, että vastaanottaja tarkistusummasta huolimatta hyväksyy datakehyksen oikeana, vaikka siinä on tapahtunut runsaasti bittivirheitä? Entä onko mahdollista, etta tarkistussummaa käytettäessä yksi ainoa bittivirhe voi aiheuttaa virheellisen datakehyksen hyväksymisen oikeana? Perustele vastauksesi. (2 p)

On mahdollista. Tarkistussumman koodin pituus määrittää, kuinka paljon erilaisia bittivirheitä se päästää läpi oikeina. CRC:ssä, jos virheellinen datan CRC polynomien jakojäännöksestä tulee nolla (eli saatu data on jaollinen G(X):llä), virheellinen data päästetään läpi.

Esimerkiksi ATM:n 8 bittinen HEC-koodi päästää virheellisen solun läpi todennäköisyydellä 1/256. CRC-32 ei päästä yksiä bittivirheitä (tilanne jossa Hamming-etäisyys on yksi) läpi.

On mahdollista, että bittivirhe tapahtuu kehyksen alku- tai loppulipussa, jolloin tulee useampia virheitä. Tällöin yksi virhe voi aiheuttaa useampia virheitä.

1p Virheellinen data voidaan päästää läpi. Yksi esimerkki.
1p Bittivirhe kehyksien alku-/loppulipussa.

3. (Sampo Pyysalo)
a) Siirtoyhteystason (link layer) protokolla käyttää valikoivan toiston (Selective Repeat) - menetelmää. Häiriöistä pyritään toipumaan mahdollisimman nopeasti, vastaanottaja ilmoittaa siis lähettäjälle havaitsemistaan ongelmista niin pian kuin mahdollista. Käytettävissä ovat kuittauskehykset "kumulatiivinen ACK" ja "NAK". Ikkunan koko on 5. Simuloi tietoliikenteen eteneminen ja toipuminen tilanteesta, jossa katoaa ensin kehys N ja sitten kehyksen N+1 aiheuttama kuittaus. Vastauksesta tulee käydä selvästi ilmi tapahtumien järjestys ja puskurien sisältö kussakin vaiheessa. (4 p)
b) Kun ikkunan koko on 5 ja käytetään valikoivaa toistoa, niin riittääkö tällöin numeroida sanomat 0-7? Perustele vastauksesi. (2 p)

4.(Tiina Niklander)
a) Piirrä kaaviokuva OSI-mallin kerroksista. Esitä lyhyesti kunkin OSI-kerroksen tärkeimmät tehtävät. (4 p)
b) Missä OSI-mallin kerroksessa MAC-alikerros sijaitsee. Mitkä ovat MAC-kerroksen tehtävät? (2p)