PMT/K1 Januar 2023

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

Popravni prvi kolokvijum 2023. godine održan je 18. januara i trajao je 2 sata.

Pitanje 1

Postavka

Neka se pri prenosu podataka primenjuje zaštitni blok kod čija je generišuća matrica:

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

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

Pitanje 2

Postavka

1. (1p) Objasniti monoalfabetsku šifru. Kako se ona može razbiti?
2. (2p) Objasniti polialfabetsku šifru. Šta je to Vernamova šifra i zašto je ona bitna?
3. (2p) Opisati ukratko RSA algoritam. U čemu se ogleda njegova sigurnost? Kako se mogu kombinovati simetrični i asimetrični kriptosistem?

Zadatak 1

Postavka

Izvršiti Hafmenovo kodovanje izvora informacija bez memorije koji emituje sedam simbola sa sledećim verovatnoćama:

Si	S1	S2	S3	S4	S5	S6	S7
P(Si)	0.2	0.3	0.2	0.05	0.1	0.1	0.05

1. (3p) Odrediti entropiju izvora a zatim i efikasnost i stepen kompresije dobijenog koda.
2. (2p) Nacrtati odgovarajuće kodno stablo i označiti hijerarhijske nivoe. Da li je dobijeni kod trenutan? Da li je dobijeni kod kompaktan?
3. (1p) Ako izvor emituje sekvencu simbola S₂, S₆, S₄, S₁, S₅ i kanal greši pri prenosu prvog bita, odrediti dekodovanu sekvencu.
4. (2p) Ako se na izlaz Hafmenovog kodera priključi zaštitni koder sa ponavljanjem tri puta a zatim kanal u kome je verovatnoća greške p=10^-1, odrediti ukupan broj bita koji se šalje kroz kanal za primer iz prethodne tačke. Koliku verovatnoću greške tada registruje korisnik (dekoder radi po principu većinskog odlučivanja)? Kako se menja broj binarnih simbola prenetih kroz kanal a kako verovatnoća greške koju registruje korisnik ako se umesto ponavljanja tri puta primeni kod sa ponavljanjem tri puta?

Zadatak 2

Postavka

1. (4p) Niz informacionih bita 00100100 kodovati Hemingovim (8,4) kodom. Kao posledica šuma koji deluje u kanalu, 2, 7. i 10. bit u sekvenci koja se pojavljuje na izlazu kodera nisu ispravno primljeni. Kakvi zaključci se mogu doneti nakon procesa dekodovanja?
2. (2p) Ako se greške u kanalu pojavljuju sa verovatnoćom p=10^-3, izračunati verovatnoću da se pojavi greška koju nije moguće ni korigovati ni detektovati.