Osnovi teorije informacija: Šenonove teoreme i principi kodovanja

Prva Šenonova teorema i kompresija podataka

Prva Šenonova teorema: l̄ ≥ H(S) objašnjava koliko najviše možemo da smanjimo (kompresujemo) podatke.

• Teorema tvrdi da je prosečna dužina kodnih reči l̄ uvek veća ili jednaka entropiji izvora H(S).
• Koeficijent kompresije: Što je veći, kompresija je bolja.
• Efikasnost: Što je veća, kod je bliži teorijskoj granici zadatoj Prvom Šenonovom teoremom. Kod bolje iskorišćava bitove i bliži je idealnom kodovanju.

Entropija i parametri telekomunikacionog kanala

Apriorna entropija

Apriorna entropija ulaznih lista simbola u telekomunikacioni kanal predstavlja prosečnu količinu informacija po simbolu na ulazu u kanal. To je mera neizvesnosti izvora pre prenosa kroz kanal. Označava se sa H(X) i zavisi samo od verovatnoća pojavljivanja ulaznih simbola. Što je entropija veća, izbor ima više informacija.

Ekvivokacija

Ekvivokacija predstavlja prosečnu količinu informacija o ulaznom simbolu koja ostaje nepoznata nakon prijema izlaznog simbola. Označava se sa H(X|Y) i predstavlja neizvesnost o ulazu kada je izlaz poznat. Nastaje zbog šuma u kanalu; ako je ekvivokacija velika, kanal je nepouzdan.

Prenesena informacija

Prenesena informacija je količina informacija koja je uspešno prenesena sa ulaza na izlaz kanala. Označava se sa I(X;Y) i predstavlja zajedničku informaciju između ulaza i izlaz. Što je prenesena informacija veća, prenos je uspešniji.

Kapacitet kanala i Druga Šenonova teorema

Kapacitet kanala (C) je maksimalna količina informacija koja se može pouzdano preneti kroz kanal u jedinici vremena.

Druga Šenonova teorema

Moguće je ostvariti potpuno pouzdan prenos informacija kroz kanal sa šumom ako je brzina prenosa manja od kapaciteta kanala (R ≤ C). Ako je brzina prenosa veća od kapaciteta kanala, pouzdan prenos nije moguć bez obzira na način kodiranja.

Poređenje kanala i svojstva ekvivokacije

Razmotrimo dva kanala:

• Kanal 1: H1(X|Y) = 0 → I1(X;Y) = H(X)
• Kanal 2: H2(X|Y) = H(X) → I2(X;Y) = 0

Povoljniji je kanal kod koga je H(X|Y) = 0 jer nema neizvesnosti nakon prijema simbola i prijemnik tačno zna koji je simbol poslat, što omogućava brži prenos informacija. Kod drugog kanala, izlaz ne daje nikakvu informaciju o ulazu, odnosno prenos informacija praktično ne postoji.

Da li ekvivokacija može biti veća od apriorne entropije?

Ne može. Ekvivokacija može biti:

• Jednaka nuli (idealni kanal).
• Jednaka entropiji izvora (potpuno nepouzdan kanal).
• Nikada ne može biti veća od entropije izvora.

Efikasnost prenosa i Hemingov kod

Osnovna uloga entropijskih kodova je da smanje prosečne dužine kodnih reči, čime se postiže efikasna kompresija podataka bez gubitka informacija.

Uticaj na kapacitet kontinualnog kanala

Kapacitet zavisi od širine propusnog opsega B i od odnosa signal/šum (S/N) prema formuli: C = B log&sub2;(1 + S/N). Na kapacitet se može uticati:

• Povećanjem širine propusnog opsega B.
• Povećanjem odnosa signal/šum (S/N) kroz povećanje snage korisnog signala ili smanjenje nivoa šuma.
• Primenom kvalitetnijih uređaja i tehnika za smanjenje smetnji.

Hemingov kod

Primenom Hemingovog koda mogu da se otkriju dve greške, ali može da se ispravi samo jedna greška. Formula za proveru je 2^k ≥ m + k + 1, gde je m broj informacionih, a k broj kontrolnih bitova.

Napomena: Primenom Hemingovog koda se ne povećava brzina prenosa, već se povećava pouzdanost. Efektivna brzina se zapravo smanjuje jer se dodaju kontrolni bitovi.

Kriptologija: Kriptografija i kriptoanaliza

Zajedno čine oblast koja se zove kriptologija.

• Kriptografija: Nauka o zaštiti informacija koja se bavi konstrukcijom šifara i razvojem metoda za šifrovanje i dešifrovanje. Cilj je poverljivost i bezbednost poruke.
• Kriptoanaliza: Nauka o razbijanju ili analiziranju šifara. Bavi se pronalaženjem načina da se otkrije originalna poruka ili ključ bez poznavanja tajnog koda.

Entropijska funkcija i tipovi kodova

Fizički smisao entropije

Entropija diskretnog izvora bez memorije ukazuje na to koliko se informacionih bita nalazi po jednom fizičkom bitu (simbolu). Ona je maksimalna kada su svi simboli podjednako verovatni (najveća neizvesnost), a jednaka je nuli kada je ishod siguran.

• p = 0: H(0) = 0 (nema neizvesnosti)
• p = 1: H(1) = 0
• p = 1/2: H(1/2) = 1 (maksimalna neizvesnost)

Sistematski naspram nesistematskih kodova

• Sistematski kodovi: Informacioni bitovi ostaju nepromenjeni i nalaze se direktno u kodnoj reči, a na njih se dodaju kontrolni bitovi.
• Nesistematski kodovi: Informacioni bitovi nisu direktno vidljivi jer se kombinuju sa kontrolnim bitovima, pa se originalna informacija ne može odmah prepoznati.

Razlika između zaštitnih i kripto kodova

• Zaštitni kod: Služi za otkrivanje i/ili ispravljanje slučajnih grešaka nastalih pri prenosu ili skladištenju.
• Kripto kod: Služi za zaštitu poverljivih podataka i sprečavanje neovlašćenog pristupa šifrovanjem.