PMT/K1N 2022

Ovaj rok nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Nadoknada prvog kolokvijuma 2022. godine održana je 9. decembra i trajala je 2 sata.

Pitanje 1

Ako se za zaštitu informacija pri prenosu podataka primenjuje linearni blok kod čija je generišuća matrica:

$G=\begin{bmatrix} 0 & 1 & 1 & 1 & 0 & 0\\ 1& 0 & 1 & 0 & 1 & 0\\ 1& 1& 0 & 0 &0 & 1 \end{bmatrix}$

1. (1p) Odrediti kodni količnik ovog koda.
2. (2p) Napisati sve kodne reči ovog koda.
3. (1p) Koliko je minimalno Hemingovo rastojanje u kodu?
4. (1p) Koliko najviše grešaka ovaj kod može detektovati, a koliko ispraviti?

Pitanje 2

1. (1p) Šta je Vernamova šifra? Zašto je ona bitna? Koji su njeni nedostaci?
2. (2p) Ukratko opisati DES ili AES algoritam (sami izaberite koji algoritam opisujete).
3. (2p) Zašto je bitna distribucija ključa u simetričnom kriptosistemu? Ukratko objasniti kako se može obaviti sigurna distribucija ključa kroz nesiguran kanal.

Zadatak 1

Binarni izvor s memorijom prvog reda opisan je sledećim dijagramom stanja:

Dijagram stanja u prvom zadatku.

1. (3p) Odrediti entropiju izvora a zatim efikasnost i postignuti stepen kompresije ako se sekvenca koju emituje ovaj izvor propusti kroz koder u kome je primenjen Hafmenov algoritam. Napisati jednu karakterističnu sekvencu koju emituje ovaj izvor.
2. (3p) Da li je moguće postići veći stepen kompresije i koliko on iznosi?
3. (2p) Predložiti postupak kojim se može dostići maksimalan stepen kompresije (u ovom delu zadatka samo dati opis ovog postupka, ne treba računati stepen kompresije).

Zadatak 2

Izvor informacija emituje sekvencu simbola ABCAAAC, koja se pre slanja kroz nepouzdan kanal koduje Hafmenovim statističkim kodom, a zatim i zaštitnim kodom sa ponavljanjem (5,1). Komunikacioni kanal se modeluje kao binarni simetrični kanal u kome je verovatnoća greške p = 0.01.

1. (2p) Nacrtati blok šemu sistema i označiti blokove u predajniku i prijemniku.
2. (2p) Odrediti binarnu sekvencu na izlazu iz zaštitnog kodera.
3. (3p) Odrediti verovatnoću greške koja se postiže nakon zaštitnog dekodovanja.