PMT/K1 2021

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

Prvi kolokvijum 2021. godine održan je 6. novembra 2021. i trajao je 2 sata.

Pitanje 1

1. (2p) Blok šema telekomunikacionog sistema sa stanovišta teorije informacija. Na šta se misli kada se kaže da je cilj obezbediti efikasan, bezbedan i pouzdan prenos podataka?
2. (3p) Objasniti šifru transpozicije, monoalfabetsku i polialfabetsku šifru. Kako se analizom kriptograma može zaključiti koja je šifra primenjena? Kako se može napraviti šifra kod koje se iz kriptograma nikako ne može dobiti poruka bez poznavanja ključa?

Pitanje 2

U cilju povećanja pouzdanosti prenosa podataka primenjuje se kod čija je generišuća matrica:

$G=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 1& 0 & 1 & 0 & 1 & 0\\ 1& 1& 1 & 1 &0 & 0 \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 ispraviti, a koliko detektovati?

Zadatak 1

Posmatra se izvor bez memorije koji emituje dva simbola sa sledećim verovatnoćama:

Si	S₁	S₂
P(Si)	0.75	0.25

1. (2p) Odrediti entropiju izvora, efikasnost i stepen kompresije binarnog statističkog koda koji odgovara originalnom izvoru.
2. (2p) Odrediti entropiju izvora, efikasnost i stepen kompresije binarnog statističkog koda koji odgovara drugom proširenju originalnog izvora.
3. (2p) Nacrtati kodno stablo koje odgovara kodu iz prethodne tačke (koji odgovara drugom proširenju) i označiti hijerarhijske nivoe. Da li je ovaj kod trenutan?
4. (2p) Ako bi bio primenjen optimalni statistički kod, koliki je minimalni broj binarnih simbola kojim se može predstaviti 1000 simbola koje emituje ovaj izvor?

Zadatak 2

1. (3p) Niz informacionih bita 001 kodovati Hemingovim (6,3) kodom. Kao posledica šuma koji deluje u kanalu, 3. bit u sekvenci koja se pojavljuje na izlazu kodera nije ispravno primljen. Kakvi zaključci se mogu doneti nakon procesa dekodovanja?
2. (4p) Konstruisati kod (5,1), dobijen skraćivanjem Hemingovog koda (7,4) ѕa tri pozicije i dodavanjem jednog bita ukupne provere parnosti. Napisati sekvencu koja se pojavljuje na izlazu odgovarajućeg kodera, ako je sekvenca na njegovom ulazu ista kao u prvom delu zadatka. Kolika je verovatnoća da se u kodnoj reči pojavi greška koju nije moguće ni korigovati ni detektovati, ako je verovatnoća greške u kanalu p=10⁻³?