Next: Tästä dokumentista ...
Up: harj9
Previous: harj9
- Määritä binäärisen symmetrisen kanavan BSC(
) kapasiteetti,
kun (a)
, (b)
, (c)
.
- Osoita, että
-bittisten bittijonojen Hamming-etäisyys
on metriikka avaruudessa
, so. että
kaikilla
on voimassa:
,
jos ja vain jos
,
-
,
-
(``kolmioepäyhtälö'').
(Näistä ehdoista on tässä tapauksessa tietenkin ainoastaan
(d) epätriviaali.)
- Luettele Hamming-koodin
(4 viestibittiä, 3 pariteettibittiä,
yhden virheen korjaus) kaikki koodisanat, kun tarkistusmatriisi
on annettu standardijärjestyksessä. (``Standardi'' = pariteettibittejä
vastaava yksikkömatriisi sijaitsee tarkistusmatriisin oikeassa reunassa.)
- Osoita, että 7-bittisessä yhden virheen korjaavassa koodissa
voi olla enintään 16 koodisanaa, ja koodi
on siten omassa luokassaan maksimaalisen tehokas.
- Suunnittele yhden virheen korjaava 5-bittinen binäärikoodi,
jossa on 4 koodisanaa. Onko koodi tehokkaampi vai vähemmän
tehokas kuin Hamming-koodi
?
- Herra
ja neiti
istuvat iltaa hieman meluisassa ravintolassa,
jonka kohinatasoa kuvaa kanava BSC(0.1). Herra
haluaa
lähettää neiti
:lle 4-bittisen viestin ``0101''.
- Mikä on todennäköisyys, että viesti menee virheettömänä perille,
jos herra
ei koodaa sitä millään tavalla?
- Entä jos herra
toistaa viestin 3 kertaa, ja neiti
valitsee kunkin bitin arvoksi sen, joka esiintyy useimmissa
toistoissa? (Tässä tapauksessa siis kahdessa toistossa kolmesta.)
- Entä jos herra
koodaa viestin käyttäen Hamming-koodia
? Esitä tässä tapauksessa myös viestin koodattu versio.
- Dekoodaa luonnollista
-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: Tästä dokumentista ...
Up: harj9
Previous: harj9
Pekka Orponen
2000-11-16