next up previous
Next: Tästä dokumentista ... Up: harj9 Previous: harj9

Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 9, 21.-23.11.


  1. Määritä binäärisen symmetrisen kanavan BSC($p$) kapasiteetti, kun (a) $p = 0.01$, (b) $p = 0.1$, (c) $p = 0.4$.

  2. Osoita, että $n$-bittisten bittijonojen Hamming-etäisyys $d(x,y)$ on metriikka avaruudessa $\{0,1\}^n$, so. että kaikilla $x, y, z \in \{0,1\}^n$ on voimassa:
    1. $d(x,y) \geq 0$,
    2. $d(x,y) = 0$ jos ja vain jos $x = y$,
    3. $d(x,y) = d(y,x)$,
    4. $d(x,z) \leq d(x,y) + d(y,z)$ (``kolmioepäyhtälö'').
    (Näistä ehdoista on tässä tapauksessa tietenkin ainoastaan (d) epätriviaali.)

  3. Luettele Hamming-koodin ${\cal H}_4$ (4 viestibittiä, 3 pariteettibittiä, yhden virheen korjaus) kaikki koodisanat, kun tarkistusmatriisi on annettu standardijärjestyksessä. (``Standardi'' = pariteettibittejä vastaava yksikkömatriisi sijaitsee tarkistusmatriisin oikeassa reunassa.)

  4. Osoita, että 7-bittisessä yhden virheen korjaavassa koodissa voi olla enintään 16 koodisanaa, ja koodi ${\cal H}_4$ on siten omassa luokassaan maksimaalisen tehokas.

  5. Suunnittele yhden virheen korjaava 5-bittinen binäärikoodi, jossa on 4 koodisanaa. Onko koodi tehokkaampi vai vähemmän tehokas kuin Hamming-koodi ${\cal H}_4$?

  6. Herra $K$ ja neiti $Y$ istuvat iltaa hieman meluisassa ravintolassa, jonka kohinatasoa kuvaa kanava BSC(0.1). Herra $K$ haluaa lähettää neiti $Y$:lle 4-bittisen viestin ``0101''.
    1. Mikä on todennäköisyys, että viesti menee virheettömänä perille, jos herra $K$ ei koodaa sitä millään tavalla?
    2. Entä jos herra $K$ toistaa viestin 3 kertaa, ja neiti $Y$ valitsee kunkin bitin arvoksi sen, joka esiintyy useimmissa toistoissa? (Tässä tapauksessa siis kahdessa toistossa kolmesta.)
    3. Entä jos herra $K$ koodaa viestin käyttäen Hamming-koodia ${\cal H}_4$? Esitä tässä tapauksessa myös viestin koodattu versio.

  7. Dekoodaa luonnollista ${\cal H}_4$-koodia käyttäen koodattu, yhden virheen sisältävä merkkijono 1001010. (``Luonnollinen'' = tarkistusmatriisin sarakkeet ovat binäärilukuina tulkittuina nousevassa numerojärjestyksessä.) Mikä on vastaava virheetön 4-bittinen viestisana?



Kurssin toinen välikoe pidetään ke 29.11. klo 8-11. Koe kattaa harjoituksissa 6-9 käsitellyt asiat (verkko- ja koodausteoria).


next up previous
Next: Tästä dokumentista ... Up: harj9 Previous: harj9
Pekka Orponen 2000-11-16