TEORIJA INFORMACIJ




IN IZVORNO KODIRANJE





TEORIJA INFORMACIJ




IN IZVORNO KODIRANJE



Razloˇzeni primeri in naloge



Matevˇz Kunaver





Zaloˇzba FE, 2025



©2025 Zaloˇzba FE, CC BY-NC-ND 4.0

To delo je objavljeno pod licenco Creative Commons

Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.

http://creativecommons.org/licenses/by-nc-nd/4.0.



Kataloˇzni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjiˇznici v Ljubljani

COBISS.SI-ID 247040771

ISBN 978-961-243-480-9 (PDF)

URL: https://fides.fe.uni-lj.si/˜matevzk/Ucbeniki/TIIK/TIIK_Kunaver.pdf

Copyright © 2025 Zaloˇzba FE. All rights reserved. Razmnoˇzevanje (tudi fotokopiranje)

dela v celoti ali po delih brez predhodnega dovoljenja Zaloˇzbe FE prepovedano.

Naslov: Teorija informacij in izvorno kodiranje : razloˇzeni primeri in naloge

Recenzenta: pro. dr. ´ Arp´ad B˝urmen, prof. dr. Marko Meˇza

Zaloˇznik: Zaloˇzba FE, Ljubljana

Izdajatelj: Fakulteta za elektrotehniko, Ljubljana

Urednik: prof. dr. Saˇso Tomaˇziˇc

Kraj in leto izida: Ljubljana, 2025

1. elektronska izdaja





VSEBINA




Zahvala vii

Namesto uvoda ix



1 Osnove verjetnosti 1

1.1 Naloge 1



2 Naklju ˇcne spremenljivke 11

2.1 Naloge 12



3 Ve ˇckratne naklju ˇcne spremenljivke 21

3.1 Naloge 22



4 Avtokorelacija 33



5 Informacija in entropija 51

5.1 Naloge 52



6 VLC kodiranje 57

6.1 Naloge 58



7 Vzajemna informacija 77





v


vi VSEBINA



7.1 Naloge 78



8 Kapaciteta kanala 87

8.1 Naloge 88



9 Kapaciteta kanala za razli ˇcne porazdelitve 99

9.1 Naloge 99



10 Vzor ˇcenje 109

10.1 Naloge 110



A Analiza ˇ Casovnih vrst 117



B Aritmeti ˇ Cno kodiranje 121



C LZW (de)kodiranje 123



D Huffmanovo kodiranje 127



Viri 131





ZAHVALA




Vsak zaˇcetek je teˇzak in pisanje prvega uˇcbenika ni izjema. Za zaˇcetek se zahvaljujem Iztoku, ki mi je pokazal, da je to moˇzno in mi hkrati prihranil veliko veliko dela, ker se je on prvi spopadel z latex predlogo za uˇcbenik. Prav tako gre zahvala vsem sodelavcem, ki so mirno prenesli, da sem med pisanjem izginil z radarja in se ukvarjal samo z uˇcbenikom. Nikakor pa ne bi pred seboj imeli tega uˇcbenika, ˇce ne bi bilo mojih domaˇcih, ki so mi vztrajno dvigali moralo in poskrbeli za to, da sem naˇsel nov zagon, ko sem bil ˇze skoraj obupan. Hvala vam!





vii


NAMESTO UVODA




V tem uˇcbeniku se bomo seznanili z osnovnimi pojmi teorije informacij in izvornega kodi-ranja, ki so kljuˇcni za razumevanje prenosa informacij, obdelave signalov in delovanja komunikacijskih sistemov. Postopoma bomo spoznali matematiˇcno in inˇzenirsko osnovo, ki jo potrebujemo za kvantitativno obravnavo informacijskih procesov.

Najprej bomo ponovili in razˇsirili znanje iz verjetnostnega raˇcuna, nakljuˇcnih spre-

menljivk in njihovih porazdelitev, ter spoznali veˇckratne spremenljivke in odvisnosti med njimi. Na teh temeljih bomo obravnavali statistiˇcne lastnosti signalov, vkljuˇcno z avtoko-relacijo in drugimi pomembnimi koncepti, ki opisujejo ˇcasovne in frekvenˇcne znaˇcilnosti procesov.

Nato bomo preˇsli na jedro teorije informacij, kjer bomo spoznali pojme informacije,

entropije, kodiranja in vzajemne informacije. Videli bomo, kako informacijo merimo, kako jo uˇcinkovito predstavimo ter kako jo lahko prenaˇsamo z najmanjˇso moˇzno izgubo in redundanco. Poseben poudarek bomo namenili Shannonovim temeljnim rezultatom, ki povezujejo kapaciteto komunikacijskega kanala z razmerjem signal–ˇsum in ˇsirino pasu.

V zadnjih poglavjih bomo obravnavali kapaciteto sploˇsnega in Gaussovega kanala ter

postopek vzorˇcenja signalov. Na teh primerih bomo spoznali, kako teoretiˇcna znanja uporabimo pri zasnovi in analizi realnih telekomunikacijskih sistemov, radijskih prenosov, digitalnih komunikacij in pri obdelavi ter shranjevanju podatkov.

Vsako poglavje vsebuje sklop vaj, ki nam bodo pomagale utrditi razlago in postopoma

pridobiti samostojno obvladovanje obravnavanih metod. Na voljo bodo tudi priporoˇceni dodatni viri, kjer bomo lahko pridobljeno znanje ˇse poglobili s pomoˇcjo klasiˇcne in sodobne literature s podroˇcja teorije informacij, statistiˇcne obdelave signalov in telekomunikacij.





ix


1. POGLAVJE



OSNOVE VERJETNOSTI



V sodobni informacijski teoriji in izvirnem kodiranju je verjetnostna teorija kljuˇcna osnova za razumevanje in modeliranje negotovosti, napak pri prenosu in uˇcinkovitosti kodiranja. Informacijski sistemi se redno sooˇcajo z nakljuˇcnimi procesi — od prenosa bitov prek ˇsumnega kanala, do stiskanja podatkov s spremenljivo dolˇzino kod. Razumevanje osnovnih pojmov, kot so verjetnostni prostor, dogodki, neodvisnost in pogojna verjetnost, je zato temeljno za nadaljnje ˇstudije entropije, kapacitete kanala in kodirnih strategij.

V tem poglavju bomo na primerih pokazali, kako uporabljamo osnovne koncepte klasiˇcne

verjetnosti pri analizi enostavnih nakljuˇcnih sistemov, kot so meti kocke, kvizi in teleko-munikacijski prenosi.

Pri reˇsevanju nalog v tem poglavju se bomo seznanil z modeliranjem enostavnih sis-

temov, analizo izidov ter praktiˇcnim raˇcunom verjetnosti, ki tvorijo osnovo za kasnejˇse poglavje o informacijskih ukrepih in kodiranju z izgubo ali brez nje.



Za dodatno branje priporoˇcamo naslednje vire:



A. Papoulis, S. U. Pillai: Probability, Random Variables, and Stochastic Processes

[1]



S. Haykin: Communication Systems, 5th ed. [7]



1.1 Naloge



M. Kunaver, Teorija informacij in izvorno kodiranje. 1

©2025 Zaloˇzba FE

2 OSNOVE VERJETNOSTI



Naloga 1.1: V vreˇci imamo 15 kroglic razliˇcnih barv: 10 modrih in 5 rdeˇcih. V vreˇco

seˇzemo z obema rokama in z vsako roko izvleˇcemo eno kroglico (skupaj izvleˇcemo

dve kroglici) ter si zapomnimo njuni barvi.



Definiraj nakljuˇcni dogodek v tem specifiˇcnem primeru.

Doloˇci vzorˇcni prostor.



Izrazi dogodek, da je leva izvleˇcena kroglica rdeˇce barve, kot podmnoˇzico vzorˇcnega prostora.



Reˇsitev: Naˇsa naloga je torej da najprej opredelimo sistem ki ga opazujemo in nato

definiramo posamezne dogodke, ki se lahko zgodijo v njem. Pri tem opozorimo na

dejstvo, da loˇcimo med levo in desno roko, saj je to pomembno za naˇso analizo.



Dogodek, ki nas zanima je barva obeh kroglic, ki ju izvleˇcemo. Pri tem smo pozorni, da sledimo tudi podatku v kateri roki je katera barva.



Vzorˇcni prostor je zaloga vseh moˇznih dogodkov, ki jih v naˇsem sistemu lahko opazimo. Definiramo najprej obe barvi (M za kroglico modre barve in R za rdeˇco). Dogodek, da smo v levi roki izvlekli rdeˇco in v desni modro kroglico zabeleˇzimo kot (R, M).

Vse moˇzne dogodke na koncu podamo kot {(M, M ), (M, R), (R, M ), (R, R)}



Podmnoˇzica vzorˇcnega prostora vsebuje samo tiste dogodke, ki nas zanimajo, torej {(R, M ), (R, R)}



Naloga 1.2: Na sliki so prikazane verjetnosti za dogodke A, B, C, D, E in F.





Kateri dogodek je gotov?



Kateri dogodek je najbolj neverjeten, a ne nemogoˇc?



Kateri dogodek je nemogoˇc?



Kateri dogodki so bolj verjetni kot C?



NALOGE 3



Reˇsitev: ˇ Ceprav so dogodki A, B, C, D, E in F prikazani skupaj, to ˇse ne pomeni,

da pripadajo istemu verjetnostnemu prostoru. To ugotovimo, ker je vsota njihovih

verjetnosti veˇcja od 1, kar krˇsi osnovno pravilo verjetnosti. Zato teh dogodkov ne

smemo primerjati ali zdruˇzevati med sabo na enak naˇcin, kot bi to storili z dogodki

iz istega eksperimenta. Za vsak dogodek lahko tako iz grafiˇcne predstavitve (v levo

smer se verjetnost manjˇsa, v desno pa veˇca) ugotovimo v kakˇsnem odnosu so med

seboj.

Glede na pozicijo na sliki je gotov dogodek F, saj ima 100% verjetnost, da se zgodi.



Najbolj neverjeten, a ne nemogoˇc je dogodek B, saj ˇse vedno obstaja majhna moˇznost, da se zgodi.



Nemogoˇc je dogodek A.



Dogodki, ki so bolj verjetni kot C se na sliki nahajajo desno od njega: D, E in F.



Naloga 1.3: Poˇsteno igralno kocko vrˇzemo 300 krat.

Koliko ˇsestic priˇcakujemo?



Ali smo lahko preseneˇceni, ˇce dobimo 55 ˇsestic?



Reˇsitev: Poˇstena igralna kocka pomeni, da vsaka cifra pade z enako verjetnostjo

P 1 ( X ) =. Vsak met je neodvisen, torej zgodovina metov ne vpliva na naslednjega.

6

Verjetnost za posamezno ˇsestico je 1 P (6) =, meti so med seboj neodvisni torej

6

lahko priˇcakujemo 1 300 · P (6) = 300 · = 50 ˇsestic.

6

Ne.



Naloga 1.4: M&M bonbonˇcki so razliˇcnih barv in te razliˇcne barve se pojavljajo v

razliˇcnih razmerjih. Spodnja tabela podaja verjetnosti, da je nakljuˇcno izbran M&M

doloˇcene barve, vendar verjetnost za pojavljanje modre barve manjka.



barva rjava rdeˇca rumena zelena oranˇzna modra

verjetnost 0,3 0,2 0,2 0,1 0,1 ?



a) Kolikˇsna je manjkajoˇca verjetnost?



b) Kolikˇsna je verjetnost da:



Dobimo rjavega ali rdeˇcega.



Ne dobimo rumenega.

Ne dobimo niti oranˇznega niti modrega.



Dobimo rjavega ali rdeˇcega ali rumenega ali zelenega ali oranˇznega ali modrega.

4 OSNOVE VERJETNOSTI



Reˇsitev:



a) Vemo, da mora biti vsota vseh verjetnosti enaka ena. Torej:



P X ( moder ) = 1 − P ( moder ) = 1 − P (ostali)

= 1 − (0,3 + 0,2 + 0,2 + 0,1 + 0,1) = 1 − 0,9 = 0,1



Verjetnost, da izvleˇcemo modri bonbon je torej 0,1.



b) Izraˇcunane verjetnosti:



P(rjav ∪ rdeˇc) = 0,3 + 0,2 = 0,5

P(rumen) = 1 − P(rumen) = 1 − 0,2 = 0,8

1 − P(oranˇzen ∪ moder) = 1 − (0,1 + 0,1) = 0,8

P (vse) = 1(ker smo pokrili vse moˇznosti).



Naloga 1.5: Meˇcemo poˇsteno igralno kocko.



Ce je prej padla 5, kakˇsna je sedaj verjetnost, da sedaj pade 6? ˇ

Trikrat zapored je padla 1. Kolikˇsna je verjetnost, da sedaj pade 6?



Kolikˇsna je verjetnost, da trikrat zapored pade 6?



Kolikˇsna je verjetnost, da v treh metih nikoli ne pade 3?



Kolikˇsna je verjetnost, da bo v treh metih vsaj enkrat padla 6?



Reˇsitev:



• Verjetnost, da pade petica ni vezana na prejˇsnje mete (dogodki so neodvisni) torej

je enaka

1

P (5) =

6



• Verjetnost je par tako neodvisna od prejˇsnjih metov, torej

1

P (6) =

6



• Verjetnost, da trikrat zapored pade 6 je enaka produktu verjetnosti:

1 1 1 1

P (6, 6, 6) = P(6)P(6)P (6) = =

6 6 6 216



NALOGE 5



• 5 Verjetnost, da enkrat ne pade 3 P (3) = 1 − P (3) =. Konˇcna verjetnost je tako

6

125

P (333) = P(3)P (3)P (3) =

216



• Zadnjo verjetnost lahko izraˇcunamo na dva naˇcina - da upoˇstevamo vse moˇznosti

ali s pomoˇcjo inverza.

1 5 5 1 1 5 1 1 1 91

vse moˇznosti : 3( ) + 3( ) + =

6 6 6 6 6 6 6 6 6 216

125 91

inverz : P (vsaj ena) = 1 − P (nobena) = 1 − =

216 216



Naloga 1.6: Dve osebi trdita, da sta telepata. Naredimo poskus, kjer postavimo

vsako osebo v svojo sobo. Osebi A pokaˇzemo niz kart, kjer je vsaka karta z enako

verjetnostjo rdeˇca, modra ali zelena.



Za vsako karto, ki jo pokaˇzemo osebi A, oseba B zabeleˇzi ”telepatsko” barvo.



Kolikˇsna je verjetnost, da oseba B pravilno ugotovi vsaj eno karto, ˇce jih osebi A

pokaˇzemo deset.



Reˇsitev: Nalogo laˇzje reˇsimo, ˇce uporabimo inverzni pristop, torej da najprej izraˇcu-

namo verjetnost, da oseba B zgreˇsi vse karte. Ko imamo ta podatek znan pa lahko z

inverzom dobimo verjetnost za vse ostale moˇznosti (torej, da ugane eno, dve, tri ali

veˇc kart).

1

P (prav) =

3

2

P(narobe) =

3

10 2

P 10 ( vse narobe ) = P (narobe

) = = 0,0173

3

P(vsaj ena) = 1 − P (vse narobe) = 1 − 0,0173 = 0,9827



Naloga 1.7: Izpit je sestavljen iz vpraˇsanj za obkroˇzevanja s po petimi odgovori.

ˇStudent na izpitu ve:

ker se je za izpit uˇcil, obstaja 75% verjetnost, da pozna pravilen odgovor



v primeru, da odgovora ne pozna bo ugibal, ker na izpitu ni negativnih toˇck za napaˇcen odgovor



Kolikˇsna je torej verjetnost, da bo ˇstudent na vpraˇsanje odgovoril pravilno?

6 OSNOVE VERJETNOSTI



Reˇsitev: Reˇsitev je kombinacija dveh dogodkov - poznavanje odgovora (A) in

ugibanje (B). Pravilni odgovor dobimo v primeru, ko ˇstudent pozna odgovor, ker se

je uˇcil ali pa vpraˇsanja ne pozna in mu uspe uganiti pravilno izbiro.



P (A) = 0.75

1

P (B) =

5

P (pravilno) = P(A) + P (B) · P(A)

1

P (pravilno) = 0,75 + · (1 − 0,75) = 0,75 + 0,05 = 0,8

5

Verjetnost, da bo ˇstudent na vpraˇsanje odgovoril pravilno je torej 0,8.



Naloga 1.8: Imamo 10 kovancev. Devet jih je ”navadnih” (cifra-grb), eden pa je

goljufiv (grb-grb).

Iz ˇzepa vzamemo kovanec. Kolikˇsna je verjetnost, da je goljufiv?



Vzamemo kovanec ne da bi ga pogledali ter ga vrˇzemo. Pade grb. Kakˇsna je verjetnost, da je goljufiv?



Ko vrˇzemo kovanec pade cifra. Kolikˇsna je verjetnost, da gre za navadni ko-vanec?



Reˇsitev:



• 1 Verjetnost, da vzamemo goljufiv kovanec je P ( G ) = .

10

• Do verjetnosti, da je kovanec goljufiv pridemo s pomoˇcjo Bayesovega izreka:



P(grb|G)P (G)

P (G|grb) =

P (grb |G)P (G) + P(grb|N)P (N)

P (grb |G) = 1 pri goljufivem kovancu vedno pade grb

1

P (G) =

10

1

P (grb |N) = pri navadnem kovancu pade grb s 50% verjetnostjo

2

9

P (N) =

10

1 1 9 2

P (G|grb) = 1 · + · =

10 2 10 11

Verjetnost, da je kovanec goljufiv je torej 0,1818.



• ˇ Ce pade cifra ni moˇzno, da gre za goljufiv kovanec, torej je 100% navadni kovanec.



NALOGE 7



Naloga 1.9: Meˇcemo poˇsteno igralno kocko.



Kolikˇsna je verjetnost, da pade liha ˇstevilka?



Kolikˇsna je verjetnost, da pade ˇstevilka, manjˇsa od 5?

Ali sta ta dogodka odvisna?



Ali sta dogodka da pade sodo ˇstevilo in da pade ˇstevilo veˇcje od 3 odvisna?



Kaj pa dogodka da pade ˇstevilo manjˇse od 4 in pade ˇstevilo veˇcje od 3?



Reˇsitev:



• Verjetnost, da pade liha ˇstevilka je:

3 1

P (L) = =

6 2



• Verjetnost, da pade ˇstevilka manjˇsa od 5 je:

4 2

P (M ) = =

6 3



• Dogodka sta neodvisna, saj je:



P(Liho∩ < 5) = P (Liho)P (< 5)



• Dogodka da pade sodo ˇstevilo in da pade ˇstevilo veˇcje od 3 sta neodvisna, saj je:



P(Sodo∩ > 3) = P (Sodo)P (> 3)



• Dogodka da pade ˇstevilo manjˇse od 4 in pade ˇstevilo veˇcje od 3 sta odvisna, saj je:



P(< 4∩ > 3) ̸= P (< 4)P (> 3)



Naloga 1.10: Kupujemo svetilko. Na izbiro imamo tri razliˇcne modele. Za vsakega

vemo kakˇsna je verjetnost, da bo svetilka po petih letih ˇse delovala ter kakˇsna je

verjetnost, da bomo ta model dobili.



Model I II III

Verjetnost delovanja po 5 letih 90% 75% 80%

Verjetnost nakupa 20% 30% 50%



Kolikˇsna je torej verjetnost, da bo kupljena svetilka po petih letih ˇse delovala.



8 OSNOVE VERJETNOSTI



Reˇsitev: Verjetnost, da bo svetilka po petih letih ˇse delovala dobimo tako, da izraˇcunamo

verjetnost za vsak model posebej in jih seˇstejemo. Tako dobimo skupno priˇcakovano

verjetnost (tehtano povpreˇcje) delovanja svetilke.



P (deluje) = P(I)P(deluje|I) + P(II )P(deluje|II) + P (III)P(deluje|III)

= 0,2 · 0,9 + 0,3 · 0,75 + 0,5 · 0,8 = 0,18 + 0,225 + 0,4 = 0,805



Verjetnost, da bo kupljena svetilka po petih letih ˇse delovala je torej 0,805.



Naloga 1.11: 2 V binarnem kanalu je visoki nivo H oddajan ˇcasa in nizki L preostalo

3

1 . verjetnost za pravilni sprejem H je 0,95, za pravilno sprejet L pa 0,85. 3



2 0,95

P (TH) = TH RH

3

0,15



0,05

1

P (TL) = TL RL

3 0,85



Binarni kanal



Kakˇsni sta zanesljivosti simbolov?



Reˇsitev: Zanesljivost simbolov izraˇcunamo tako, da izraˇcunamo verjetnost, da je

simbol sprejet pravilno. Torej da je bil sprejet visoki nivo (RH) ˇce je bil oddan

visoki nivo (TH) in obratno. Zanesljivosti zato definiramo kot pogojni verjetnosti

P (T H |RH) in P (T L|RL).



2 1

P(RH) = · 0,95 + · 0,15 = 0,686

3 3

1 2

P (RL) = · 0,85 + · 0,05 = 0,316

3 3

P 2 ( RH | T H ) P ( T H ) 0 , 95 ·

P 3 ( T H | RH ) = = = 0,927

P (RH) 0,6833

P 1 ( RL | T L ) P ( T L ) 0 , 85 ·

P 3 ( T L | RL ) = = = 0,893

P (RL) 0,3167



Zanesljivost simbolov je torej P(T H |RH) = 0,927 in P(T L|RL) = 0,893.



NALOGE 9



Naloga 1.12: Na vhodu imamo niz simbolov:



X [n]ϵ{x 1, x2} = {0, 1}; P (x1) = 0,4 P (x2) = 0,6

Verjetnost napake pri prenosu po kanalu je Pn = 0,1.

Kolikˇsna je verjetnostna funkcija izhodnega niz y[n]



Kako vpliva kanal na verjetnost izhodnih simbolov?



Kaj pa ˇce bi bili verjetnosti simbolov enaki?



Reˇsitev:



• Verjetnostna funkcija izhodnega niza y[n] je odvisna od verjetnosti napake pri prenosu

po kanalu.



P (y 1) = P (y1 |x1)P (x1) + P(y1|x2)P (x2)

= 0,9 · 0,4 + 0,1 · 0,6 = 0,42

P (y 2) = P (y2 |x2)P (x2) + P(y2|x1)P (x1)

= 0,9 · 0,6 + 0,1 · 0,4 = 0,58



• Kanal vpliva na verjetnost izhodnih simbolov, saj se verjetnosti spreminjajo glede

na to ali je priˇslo do napake ali ne.



• ˇ Ce bi bile verjetnosti simbolov enake kanal ne bi imel vpliva na verjetnost izhodnih

simbolov.



Povzetek klju ˇcnih ena ˇcb



P ugodniizidi ( A ) = Klasiˇcna definicija verjetnosti: razmerje

vsiizidi

med ugodnimi in vsemi moˇznimi izidi

P (A ∪ B) = P (A) + P (B) − P(A ∩ B) Verjetnost unije dveh dogodkov

P (A ∩ B) = P (A|B) · P(B) Verjetnost preseka dveh dogodkov preko

pogojne verjetnosti

P P [ X ] = x · P (x ) Priˇcakovana vrednost diskretne sluˇcajne

i i i

spremenljivke

P R ∞ [ X ] = x · p(x) dx Priˇcakovana vrednost zvezne sluˇcajne

−∞

spremenljivke

P ˇ ( A ∩ B ) = P ( A ) · P ( B ) Ce sta A in B neodvisna dogodka

P ( ¯ A) = 1 − P (A) Verjetnost komplementarnega dogodka

P (A ∩ B)

P (A |B) = Pogojna verjetnost

P (B)

2. POGLAVJE



NAKLJU ˇ CNE SPREMENLJIVKE



V tem poglavju bomo na konkretnih nalogah prikazali uporabo nakljuˇcnih spremenljivk za modeliranje in analizo meritev, napak in izidov v informacijskih sistemih. Nakljuˇcna spremenljivka nam omogoˇca, da kvantitativno opiˇsemo izide nakljuˇcnih poskusov — naj bodo to meritve napetosti v komunikacijskem kanalu, ˇstevilo napak pri prenosu ali rezultat kviza.

Razumeli bomo razlike med diskretnimi in zveznimi nakljuˇcnimi spremenljivkami ter

naˇcine, kako opisujemo njihove verjetnostne porazdelitve: s funkcijo verjetnosti P(x) za diskretne in z gostoto verjetnosti p(x) za zvezne.

Nadalje bomo definirali priˇcakovano vrednost nakljuˇcne spremenljivke X z oznako

P (X) in preko nje razvili kljuˇcne koncepte, kot so varianca, standardni odklon in funkcija porazdelitve. Posebej nas bodo zanimale lastnosti linearnih transformacij nakljuˇcnih spre-menljivk, simetrije, enakomernih in normalnih porazdelitev ter uporaba teh znanj pri anal-izi in detekciji signalov.

Nauˇcili se bomo tudi, kako z uporabo tabel (ali izraˇcunov) ocenimo verjetnosti za

standardno normalno porazdeljene spremenljivke, kar je pogosto v aplikacijah, kjer pred-postavljamo prisotnost ˇsuma (npr. digitalni komunikacijski sistemi).



Poglavje bo kljuˇcno za nadaljnje razumevanje entropije, kanalov, ter kodiranja z napako ali brez nje. Osvojena znanja bomo uporabljali pri ocenjevanju zanesljivosti prenosa, di-menzioniranju kanalov in pri analizi porazdelitev, ki vplivajo na uˇcinkovitost kodirnih al-goritmov.



M. Kunaver, Teorija informacij in izvorno kodiranje. 11

©2025 Zaloˇzba FE

12 NAKLJU ˇ CNE SPREMENLJIVKE



Za dodatno branje priporoˇcamo naslednje vire:



A. Papoulis, S. U. Pillai: Probability, Random Variables, and Stochastic Processes

[1]



S. Tomaˇziˇc: Osnove telekomunikacij I [5]



2.1 Naloge



Naloga 2.1: Zgodovina orkanov v ZDA je podana v tabeli.



xi 0 1 2 3 4 5 6 7

Px[i] 0,05 0,15 0,22 0,26 0,14 0,08 0,07 0,03



Kolikˇsno je priˇcakovano ˇstevilo orkanov?



Kakˇsna je standardna deviacija?



Reˇsitev: Uporabimo diskretno porazdelitev za oceno priˇcakovanega ˇstevila orkanov

ter standardne deviacije. Zaˇcnemo z izraˇcunom priˇcakovane vrednosti:

7

X X = i · P [i] = 0 · 0,05 + 1 · 0,15 + 2 · 0,22 + 3 · 0,26 + 4 · 0,14





x


i=0

+ 5 · 0,08 + 6 · 0,07 + 7 · 0,03 = 2,96



Priˇcakovano ˇstevilo orkanov je 2,96.

Standardna deviacija je kvadratni koren variance. Ti izraˇcuni so uporabni, kadar

ˇzelimo razumeti variabilnost pojavov v okolju — tukaj naravnih nesreˇc.

7

σ2 X 2 2 2 = D ( X ) = P X [ i ] · ( x i − X ) = X − X X

i=0

7

X 2 X 2 = P X [ i ] · ( x i )

i=0

X 2 2 2 2 2 2 = 0 , 05 · 0 + 0 , 15 · 1 + 0 , 22 · 2 + 0 , 26 · 3 + 0 , 14 · 4

+ 0 2 2 2 , 08 · 5 + 0 , 07 · 6 + 0 , 03 · 7

X 2 = 11,6

σ2 2 = 11 , 6 2 96 = 2,8384 − ,





X


σX = 1,685



NALOGE 13



ali

7

σ2 X 2 = D ( X ) = P [ i ] · ( x − X )

X X i

i=0

σ2 2 2 2 = 0 , 05 · (0 − 2 , 96) + 0 , 15 · (1 − 2 , 96) + 0 , 22 · (2 − 2 , 96)





X


+ 0 2 2 2 , 26 · (3 − 2 , 96) + 0 , 14 · (4 − 2 , 96) + 0 , 08 · (5 − 2 , 96)

+ 0 2 2 , 07 · (6 − 2 , 96) + 0 , 03 · (7 − 2 , 96)

σ2 = 2,8384





X


σX = 1,685



Standardna deviacija je 1,685.



Naloga 2.2: Predpostavimo, da je X zvezna nakljuˇcna spremenljivka z gostoto ver-

jetnosti

( (3 −x) ce, za 3 ≤ x ≤ 6

p(x) =

0, drugje

Doloˇci



Vrednost konstante c

P (x ≤ 5)



P (x ≤ 3)



P (4 ≤ x ≤ 5.5)



P (4 ≤ x ≤ 7)



P (x ≤ 5 | x ≥ 4)



Reˇsitev: Veljati mora:

Z ∞

p X (x) dx = 1

−∞

Torej integral razbijemo na tri dele:

Z 3 Z 6 Z ∞ 6

0 (3−x) (3−x) dx + ce dx + 0 dx = − ce



−∞ 3 63

= 3−6 3−3 −3 − c e − e = c 1 − e

= c · 0,95



Iz tega sledi, da mora biti konstanta c enaka:

1

c = = 1,0524

0,95

14 NAKLJU ˇ CNE SPREMENLJIVKE



Sedaj lahko izraˇcunamo ostale verjetnosti, v vsakem primeru s pomoˇcjo integrala:



Verjetnost P(x ≤ 5) je 0,91.

Z 5 Z 5 5

P (3−x) (3−x) ( X ≤ 5) = p ( x ) dx = 1 , 05 · e dx = − 1 , 05 · e





X


−∞ 3 3

= 1 −2 , 05 1 − e = 0,91



Verjetnost P(x ≤ 3) je 0.

Z 3 Z 3

P (3−x) ( X ≤ 3) = p ( x ) dx = 1 , 05 · e dx = 0





X


−∞ 3



Verjetnost P(4 ≤ x ≤ 5.5) je 0,30.



P (4 ≤ X ≤ 5.5) = P (X ≤ 5.5) − P (X < 4)

= 1 3−5.5 3−4 , 05 1 − e − 1 , 05 1 − e

= 0,30



Verjetnost P(4 ≤ x ≤ 7) je 0,335.



P (4 ≤ X ≤ 7) = P(X ≤ 7) − P (X < 4)

= 1 3−6 3−4 , 05 1 − e − 1 , 05 1 − e

= 0,335



Verjetnost P(x ≤ 5 | x ≥ 4) je 0,73.



P (4 ≤ X ≤ 5) P (X ≤ 5) − P (X < 4)

P (X ≤ 5 | X ≥ 4) = =

P (X ≥ 4) 1 − P(X < 4)

1 3−5 3−4 , 05 1 − e − 1 , 05 1 − e

P (X ≤ 5 | X ≥ 4) = 3− 1 −4 1 , 05 (1 − e)

= 0,73



NALOGE 15



Naloga 2.3: X je zvezna nakljuˇcna spremenljivka s porazdelitvijo verjetnosti:



( 2 3 x, 0 ≤ x ≤ 1

p(x) =

0, drugje



Ali je p(x) lahko verjetnostna porazdelitev?



Doloˇci kumulativno verjetnostno porazdelitev.



Izraˇcunaj povpreˇcno vrednost spremenljivke.



Izraˇcunaj varianco nakljuˇcne spremenljivke.



Reˇsitev: ˇ Ce je p(x) verjetnostna porazdelitev, mora veljati:

Z ∞

pX(x) dx = 1

−∞

Z 1 1 3 x

3 2 x dx = 3 · = 1

3

0 0



Torej je p(x) verjetnostna porazdelitev.

Kumulativna verjetnostna porazdelitev je definirana kot:

Z x

FX(x) = pX(t) dt

−∞

x < 0 : F X (x) = 0

Z x 3 x t

0 2 3 3 3 ≤ x ≤ 1 : F ( x ) = 3 t dt = 3 · = x − 0 = x

X 0 0 3

x > 1 : F X (x) = 1



Za povpreˇcno vrednost spremenljivke reˇsimo integral:

Z ∞ Z 1 Z 1

X 2 3 = x · p ( x ) dx = x · 3 x dx = 3 x dx





X


−∞ 0 0

x 4 1 3

= 3 · = = 0,75

4 4

0



Povpreˇcna vrednost spremenljivke je torej X = 0,75.



16 NAKLJU ˇ CNE SPREMENLJIVKE



Za varianco spremenljivke uporabimo formulo:

Z Z 1 ∞

D 2 2 2 ( X ) = ( x − X ) · p ( x ) dx = ( x − 0 , 75) · 3 x dx





X


−∞ 0

Z 1

= 2 2 x − 1 , 5 x + 0 , 5625 · 3 x dx

0

Z 1 Z 1 Z 1

D 4 3 2 ( X ) = 3 x dx − 1 , 5 3 x dx + 0 , 5625 3 x dx

0 0 0

x 5 1 4 1 3 1 x x

= 3 · − 4 , 5 · + 0 , 5625 · 3 ·

5 4 3

0 00

3 4,5

D(X) = − + 0,5625 = 0,0375

5 4

Varianca nakljuˇcne spremenljivke X je torej D(X ) = 0,0375.



Naloga 2.4: Nakljuˇcna spremenljivka X s srednjo vrednostjo 2 ima standardno de-

viacijo 1. Doloˇci srednjo kvadratno vrednost 2 X.



Reˇsitev: 2 Srednja kvadratna vrednost spremenljivke je X = 5, kar dobimo neposredno

iz srednje vrednosti in standardne deviacije po sledeˇci formuli:



X 2 2 2 2 2 = X + σ = 2 + 1 = 5





X




Naloga 2.5: Debelina fotorezista, ki ga nanesemo na silicijeve rezine pri proizvodnji

polprevodnikov je enakomerno porazdeljena med 0,202 in 0,215 mikrometri.



Doloˇci kumulativno porazdelitev Fx.

Doloˇci deleˇz rezin, katerih debelina presega 0,2125 mikrometra.



Katero debelino fotorezistorja presega zgolj 10% vseh rezin?



Doloˇcite povpreˇcno debelino in varianco debeline.



Reˇsitev: Enakomerna porazdelitev pomeni, da je verjetnost na celem intervalu kon-

stantna. Ker mora biti integral ˇcez celoten interval enak ena, izraˇcunamo konstantno

verjetnost kot:

1 1

p = = = 100

∆x 0,01



NALOGE 17



Kumulativna verjetnost je integral gostote verjetnosti od −∞ do izbrane vrednosti

nakljuˇcne sprememnljivke:



x < 0,205 : F X (x) = 0

Z x Z x x

0 , 205 ≤ x ≤ 0 , 215 : F ( x ) = p ( t ) dt = p · dt = 100 · t

X X

0 , 205 0 , 2050,205

= 100(x − 0,205) = 100x − 20,5

x > 0,215 : F X (x) = 1



Da doloˇcimo deleˇz rezin, katerih debelina presega 0,2125 mikrometra, uporabimo

kumulativno porazdelitev in inverzno logiko:



PX(x > 0,2125) = 1 − FX(0,2125) = 1 − (100 · 0,2125 − 20,5)

= 1 − 0,75 = 0,25



Na podoben naˇcin doloˇcimo debelino, ki presega zgolj 10% vseh rezin:



PX(X > x10) = 0,1 = 1 − FX(x10) ⇒ FX(x10) = 0,9

100 · x10 − 20,5 = 0,9

0,9 + 20,5

x10 = = 0,214

100

Povpreˇcno debelino in varianco izraˇcunamo z uporabo definicij:



Z Z 0 ∞,215 , Z 0215 1

X = x · pX(x) dx = x · dx = 100 · x dx

−∞ 0,01 0 , 205 0,205

x 2 0,215

= 100 · = 50 · (0,046225 − 0,042025) = 0,210 2 0 , 205

Z Z 0 ∞,215

D 2 2 ( X ) = ( x − X ) p ( x ) dx = ( x − 0 , 21) · 100 dx





X


−∞ 0,205

Z 0,215

= 100 2 · ( x − 0,42x + 0,0441) dx

0,205

3 x 0 , 215 2 x 0 , 215 0 , 215

D(X) = 100 · − 0,42 · + 4,41 · x

3 0 , 205 2 0 , 2050,205

= 0 −6 , 04410833 − 0 , 0882 + 0 , 0441 = 8 , 33 · 10



18 NAKLJU ˇ CNE SPREMENLJIVKE



Naloga 2.6: Naj bo X normalno porazdeljenba zvezna nakljuˇcna spremenljivka s

srednjo vrednostjo 0 in standardno deviacijo 1. Doloˇci:



P (x ≤ 1,4)

P (x ≥ −1,3)



Reˇsitev: Za normalno porazdelitev pogosto ne raˇcunamo verjetnosti analitiˇcno,

temveˇc s pomoˇcjo tabele. Standardna normalna porazdelitev N (0, 1) omogoˇca iskanje:



P (X ≤ x) = Φ(x)



kjer je Φ(x) vrednost iz tabele. Dodatno si pomagamo s sledeˇcimi pomoˇznimi

enaˇcbami:

P(X ≥ x) = 1 − P(X ≤ x)

P (X ≤ −x) = P (X ≥ x)

P (X ≥ −x) = P (X ≤ x)



Za naˇs primer torej dobimo:



P(X ≤ 1, 4) = Φ(1, 4) = 0, 91924

P (X ≥ −1, 3) = Φ(1, 3) = 0, 90320



Naloga 2.7: Na digitalni liniji je prisoten ˇsum z normalno porazdelitvijo amplitude,

srednjo vrednostjo 0 in standardno deviacijo 0,45V.

Sistem zazna 1, ˇce napetost presega 0,9V. Kolikˇsna je verjetnost, da sistem zazna

1, ˇce na liniji ni signala?



Reˇsitev: Pozorni moramo biti na to, da je standardna deviacija razliˇcna od 1, kar

pomeni, da moramo prilagoditi izraˇcun normalne porazdelitve. Vse tabele v matema-

tiˇcnem priroˇcniku so namreˇc narejene za standardno normalno porazdelitev, kjer je

standardna deviacija 1. Potrebno je torej normalizirati vrednost, da jo lahko potem

preberemo iz tabele.

Vrednosti v tabeli nam namreˇc povejo ”kolikokrat moram ˇsum preseˇci vrednost stan-

dardne deviacije”. Torej Φ(0, 4) pomeni, da je ˇsum presegel 0,4 standardne deviacije.

Povedano drugaˇce - v primerih ko je standardna deviacija razliˇcna od 1 uporabimo

sledeˇco enaˇcbo:

nivo ki me zanima

Φ

standardna deviacija



NALOGE 19



V naˇsem primeru mora torej ˇsum preseˇci 0,9V, kar je dvakratna vrednost standardne

deviacije:



0, 9V 0, 9V

xσ = 0, 9V ⇒ x = = = 2

σ 0, 45V

X 0 , 9 0 , 9

PX(X > 0, 9) = 1 − PX(X ≤ 0, 9) = 1 − PX ≤ = 1 − Φ

σ σ 0, 45

= 1 − Φ(2) = 1 − 0, 97725

PX(X > 0, 9) = 0, 02275



Verjetnost, da sistem zazna 1, ˇce na liniji ni signala, je torej pribliˇzno 0,02275 ali

2,275%.



Povzetek klju ˇcnih ena ˇcb



X ¯ P = x i · P (xi) Priˇcakovana vrednost diskretne spremenljivke

X ¯ R ∞ = x · p(x) dx Priˇcakovana vrednost zvezne spremenljivke −∞

σ2 P ¯ 2 = P ( x ) · ( x X i i − X ) Varianca – kvadratni odmik od povpreˇcja

σ p 2 X X Standardna deviacija – raztros v istih enotah kot = σ X

P R A ( x ≤ A ) = p(x) dx Verjetnost, da je X manjˇsa ali enaka A (zvezne spre-

−∞

menljivke)

F (x) = P(X ≤ x) Kumulativna funkcija porazdelitve



3. POGLAVJE



VE ˇ CKRATNE NAKLJU ˇ CNE



SPREMENLJIVKE



V tem poglavju bomo obravnavali naloge, kjer nastopata dve ali veˇc medsebojno odvisnih nakljuˇcnih spremenljivk — na primer v prisotnosti ˇsuma ali soˇcasnem prenosu informacij. Tak pristop je nujen pri analizi sistemov, kjer spremenljivke niso neodvisne, ampak so med seboj statistiˇcno povezane — na primer meritev signala v prisotnosti ˇsuma, temperaturni in napetostni profil v sistemu, ali soˇcasno kodiranje veˇcih informacijskih tokov.

Bistvena pojma, ki ju bomo obravnavali, sta skupna porazdelitev in pogojna porazdelitev.

Skupna porazdelitev P XY (x, y) nam pove, s kakˇsno verjetnostjo se hkrati pojavita vred-nosti x in y spremenljivk X in Y . Pogojna porazdelitev P(Y |X ) pa modelira verjetnost za vrednosti Y , ˇce je X ˇze znan.

Spoznali bomo tudi koncept neodvisnosti, ki v veˇcrazseˇznem prostoru pomeni, da skupna

porazdelitev razpade na produkt marginalnih:



P XY (x, y) = PX(x) · PY (y)



Pri zveznih spremenljivkah bomo delali z gostoto verjetnosti p(x, y), kjer mora integral po celotnem obmoˇcju enak 1. Pogojne gostote bomo izraˇcunali s pomoˇcjo:



p(x, y)

p(y | x) =

pX(x)

Dodatno bomo analizirali kovarianco in korelacijo, ki podata informacijo o tem, ali se

vrednosti spremenljivk gibajo skupaj (in ˇce, kako moˇcno). Kadar je korelacijski koeficient enak 1 ali -1, imamo popolnoma linearno povezanost med spremenljivkama.



M. Kunaver, Teorija informacij in izvorno kodiranje. 21

©2025 Zaloˇzba FE

22 VE ˇ CKRATNE NAKLJU ˇ CNE SPREMENLJIVKE



Ti koncepti so temeljni v teoriji informacij, ˇse posebej pri kodiranju povezanih signalov

in ocenjevanju napak pri prenosu informacij.

Za dodatno branje priporoˇcamo naslednje vire:



A. Papoulis, S. U. Pillai: Probability, Random Variables, and Stochastic Processes

[1]



N. Paveˇsiˇc: Informacija in kodi [6]



3.1 Naloge



Naloga 3.1: Za dve spremenljivki X in Y doloˇci marginalni verjetnostni funkciji

Px(xi), Py(yj), korelacijo Rxy, kovarianco Cxy in korelacijski koeficient.

Y



0,05

4



0,05 0,15

3



0,05 0,25 0,05

2



0,1 0,05 0,1

1

0,15

0

0 1 2 3 4 X



Reˇsitev: Ker imamo skupno porazdelitev PXY (xi, yj), lahko marginalne porazdelitve

dobimo s seˇstevanjem po drugi spremenljivki:

X X

PX(xi) = PXY (xi, yj), PY (yj) = PXY (xi, yj)

j i



Korelacija je definirana kot:

X X

RXY = xiyj PXY (xi, yj )

i j



Kovarianca:



CXY = RXY − X · Y



NALOGE 23



Korelacijski koeficient:



CXY

ρ ˆXY =

σX · σY



Ta zadnji pove, kako linearno sta spremenljivki povezani. ˇ Ce je ρ ˆXY = 0, sta lin-

earno neodvisni.

Marginalni porazdelitvi sta torej:

X X

PX(xi) = PXY (xi, yj) PY (yj) = PXY (xi, yj)

j i

P PY (0) = 0, 15 X (0) = 0 , 15

PX(1) = 0, 1 + 0, 05 = 0, 15 PY (1) = 0, 1 + 0, 05 + 0, 1 = 0, 25

P PY (2) = 0, 05 + 0, 25 + 0, 05 = 0, 35 X (2) = 0 , 05 + 0 , 25 = 0 , 3

PX(3) = 0, 1 + 0, 05 = 0, 15 PY (3) = 0, 05 + 0, 15 = 0, 2

PX(4) = 0, 05 + 0, 15 + 0, 05 = 0, 25 PY (4) = 0, 05



Korelacija je tako:



R X X = x y P (x , y )

XY i j XY i j

i j

RXY = 0 · 0 · 0, 15

+ 1 · (1 · 0, 1 + 2 · 0, 05)

+ 2 · (1 · 0, 05 + 2 · 0, 25)

+ 3 · (1 · 0, 1 + 3 · 0, 05)

+ 4 · (2 · 0, 05 + 3 · 0, 15 + 4 · 0, 05)

RXY = 5, 05



Ko poznamo korelacijo lahko izraˇcunamo kovarianco:



CXY = RXY − X · Y

X X

X = x iPX(xi), Y = yjPY (yj)

i j

X = 0 · 0, 15 + 1 · 0, 15 + 2 · 0, 3 + 3 · 0, 15 + 4 · 0, 25 = 2, 2

Y = 0 · 0, 15 + 1 · 0, 25 + 2 · 0, 35 + 3 · 0, 2 + 4 · 0, 05 = 1, 75

CXY = 5, 05 − 2, 2 · 1, 75 = 1, 2



24 VE ˇ CKRATNE NAKLJU ˇ CNE SPREMENLJIVKE



In na koncu ˇse korelacijski koeficient:



CXY

ρXY =

σX · σY

q s

σ 2 2 X 2 2 X = X − X = x P x i X ( i ) − X,





i


q s

σ 2 2 Y j = Y Y = yP y ( ) − Y

− 2 X 2

Y j

j

σ p 2 2 2 2 = 1 · 0 , 15 + 2 · 0 , 3 + 3 · 0 , 15 + 4 · 0, 25 − 2, 2 = 1, 3638





X


2



σ p 2 2 2 2 2 = 1 · 0 , 25 + 2 · 0 , 35 + 3 · 0 , 2 + 4 · 0 , 05 − 1 , 75 = 1, 0897

Y

1, 2

ρXY = = 0, 807

1, 3638 · 1, 0897



Naloga 3.2: Podan imamo grafiˇcni prikaz gostote verjetnosti spremenljivk x in y.

Y



1



0,5



0

0 0,5 1 X



Doloˇci marginalno porazdelitev komponent.



Ali sta spremenljivki korelirani?



Izraˇcunaj gostoto verjetnosti p y(y |x).



Reˇsitev: Ker imamo sedaj opravka z zveznimi spremenljivkami, se naˇse vsote spre-

menijo v integrale. Najprej moramo doloˇciti gostoto verjetnosti na podroˇcju, kjer je

razliˇcna od 0. Integral po celotnem definicijskem obmoˇcju (povrˇsini x-y) mora biti

enak 1. Ker je gostota verjetnosti konstantna, lahko to napravimo grafiˇcno (iz slike

NALOGE 25



vidimo, da je povrˇsina enaka 1/2):

1

K · = 1 ⇒ K = 2

2

ali pa matematiˇcno:

Z Z ∞ ∞

p XY (x, y) dx dy = 1

−∞ −∞

Z Z Z 1 ∞ ∞ Z x Z 1 Z 1

p x ( x, y ) dy dx = K dy dx = ( Ky)dx = Kx dx

XY 0

−∞ −∞ 0 0 0 0

x2 1 1

= K = K

2 2

0

ali:



Z Z Z 1 ∞ ∞ Z 1 Z 1 1 p XY ( x, y ) dx dy = K dx dy = Kx dy y

−∞ −∞ 0 y 0

Z 1 2 1! 1 y 1

= K (1 − y ) dy = K y − = K

0 2 0

0 2

1

K · = 1 ⇒ K = 2

2

Marginalni porazdelitvi sta:

Z Z ∞ ∞

p X(x) = pXY (x, y) dy, pY (y) = pXY (x, y) dx

−∞ −∞

x ≤ 0 : p X(x) = 0

Z x

0 x < x ≤ 1 : p ( x ) = K dy = Ky = Kx = 2x

X 0

0

x > 1 : p X(x) = 0

y < 0 : p Y (y) = 0

Z 1

0 1 ≤ y ≤ 1 : p Y y (

y) = K dx = Kx = K(1 − y) = 2(1 − y)

y

y > 1 : p Y (y) = 0



Nakljuˇcni spremenljivki sta korelirani, ˇce je kovarianca CXY razliˇcna od niˇc, oziroma,



26 VE ˇ CKRATNE NAKLJU ˇ CNE SPREMENLJIVKE



ˇce je korelacija razliˇcna od produkta povpreˇcnih vrednosti spremenljivk X in Y .



RXY = CXY + X · Y

C XY ̸= 0 ⇒ RXY ̸= X · Y

Z ∞ Z ∞

RXY = xypXY (x, y) dx dy

−∞ −∞

Z 1 Z x Z 1 Z x

RXY = xyK dy dx = xK y dy dx

0 0 0 0



= Z 1 2 Z 1 2 1 y x Z x K 3 xK dx = xK dx = x dx 0 0 2 0 2 2 0



RXY = = · = 2 K 4 x 1 K 1 1

4 0 2 4 4



X Z ∞ Z 1 Z 1 3 x 1 2 2 = xp X ( x ) dx = x 2 x dx = 2 x dx = 2 = 3 0 3 −∞ 0 0

Z ∞ Z 1

Y = ypY (y) dy = y2(1 − y) dy

−∞ 0

Z 1 2 3 y y 1 1 1 1

= 2 − = 2 − =

0 2 3 0 2 3 3

2 1 2

X · Y = · = ̸= RXY ⇒ Nakljuˇcni spremenljivki sta korelirani.

3 3 9



Korelacijski koeficient C XY ρ XY = σ X σ Y



X 2 Z Z 1 ∞ 4 x1 K 1 2 2 = x p X ( x ) dx = x Kx dx = K = = 4 0 4 2 −∞ 0

Z ∞ Z 1

Y 2 2 2 = y p Y ( y ) dy = yK(1 − y) dy

−∞ 0



= K − = K − = K = 3 3 4 y 1 y 1 1 1 1 1

0 40 3 4 12 6

s √

q 2 r 2 1 2 1 4 1 2

σ 2 = X − X = − = − = √ =

X 2 3 2 9 18 6

q r 2 s √

2 2 1 1 1 1 1 2

σ Y = Y − Y = − = − = √ =

6 3 6 9 18 6

1 2 1 9 − 8 1

CXY = RXY − X · Y = − · = =

4 3 3 36 36



ρXY = = √ = = 2 σ 2 X σ 2 Y 2 · 36 6 C 1 1 XY 36 36 √ 1

6



NALOGE 27



Pogojna gostota verjetnosti p y (y |x)



p XY (x, y)

p Y (y |x) =

p X (x)

0

x ≤ 0 ∪ x > 1 : p XY (x, y) = 0, pX(x) = 0 ⇒ pY (y|x) =

0

0 < x ≤ 1 :

(K, 0 ≤ y ≤ x

pXY (x, y) = , pX (x) = 2x

0, sicer

 K

p XY (x, y)  , 0 ≤ y ≤ x

pY (y |x) = = 2x

p X (x) 0, sicer

 1

p XY (x, y)  , 0 ≤ y ≤ x

pY (y |x) = = x

p X (x) 0, sicer



Naloga 3.3: Podan imamo grafiˇcni prikaz gostote verjetnosti spremenljivk x in y.



Doloˇci marginalno porazdelitev komponent.



Izraˇcunaj korelacijo Rxy.

Izraˇcunaj korelacijski koeficient.



Izraˇcunaj gostoto verjetnosti p y(y |x).



Reˇsitev: Najprej moramo doloˇciti gostoto verjetnosti na podroˇcju, kjer je razliˇcna od

0. Integral po celotnem definicijskem obmoˇcju (povrˇsini x-y) mora biti enak 1. Ker 28 VE ˇ CKRATNE NAKLJU ˇ CNE SPREMENLJIVKE



je gostota verjetnosti konstantna, lahko to napravimo grafiˇcno (iz slike vidimo, da je

povrˇsina enaka 2):

1

K · 2 = 1 ⇒ K =

2

ali pa z integracijo:

Z Z ∞ ∞

pXY (x, y) dx dy = 1

−∞ −∞

Z Z Z 0 ∞ ∞ Z x+1 Z 1 Z 1

pXY (x, y) dy dx = K dy dx + K dy dx

−∞ −∞ −1 x 0 0

Z 0 Z 1 x +1 1

= Ky dx + Ky dx x 0

−1 0

Z 0 Z 1

= (K(x + 1 − x)) dx + (K)dx

−1 0

Z 0 Z 1

= 0 1 K dx + K dx = K ( x + x) = 2K

− 10

−1 0

Marginalni porazdelitvi:

Z Z ∞ ∞

pX(x) = pXY (x, y) dy, pY (y) = pXY (x, y) dx

−∞ −∞

x ≤ −1 : pX(x) = 0

Z x+1 1

−1 < x ≤ 0 : pX(x) = K dy = K(x + 1 − x) = K =

x 2

Z 1 1

0 1 < x ≤ 1 : p X 0 (

x) = K dy = Ky = K =

0 2

x > 1 : pX(x) = 0

y < −1 : pY (y) = 0

Z y 1

− y 1 ≤ y < 0 : p ( y ) = K dx = Kx = K(y + 1) = (y + 1)

Y −1 2

−1



0 ≤ y ≤ 1 : pY (y) = K dx = Kx = K(1 − (y − 1)) = (2 − y) y Z 1 1 1

−1 2

y−1

y > 1 : pY (y) = 0



NALOGE 29



Nakljuˇcni spremenljivki sta korelirani, ˇce je kovarianca C XY razliˇcna od niˇc, oziroma, ˇce je korelacija razliˇcna od produkta povpreˇcnih vrednosti spremenljivk X in Y .



RXY = CXY + X · Y

C XY ̸= 0 ⇒ RXY ̸= X · Y

Z ∞ Z ∞

RXY = xypXY (x, y) dx dy

−∞ −∞

Z 0 Z y+1 Z 1 Z 1

RXY = xK dx dy + xK dx dy

−1 y 0 y−1



= Z 0 y ! ! +1 2 Z 1 2 1 x x K y dy + K y dy 2 2 − 1 y 0 y − 1

K Z 0 Z 1 K

= 2 2 2 y ( y + 1) − y dy + y 1 − ( y − 1) dy

2 2 − 1 0



= K Z 0 K Z 1 2 y (2 y + 1) dy + y (2 y − y)dy 2 2 − 1 0



= K 2 0 ! ! 3 4 1 y y K 2 y y + + − 2 2 4 2 3 4 − 1 0

K 2 K 1

= = =

2 3 3 6

Z ∞1 1 K

X 2 = xp ( x ) dx = Kx = (1 − 1) = 0

X 2 2

−∞ −1

Z ∞ Z 0 Z 1

Y = ypY (y) dy = yK(y + 1)dy + yK(2 − y)dy

−∞ −1 0

1 1 1 1 1

= K − + K − =

3 2 3 3 4

1 1 1

C XY = RXY − X · Y = − 0 · =

6 4 6

C XY ̸= 0 ⇒ Nakljuˇcni spremenljivki sta korelirani.



30 VE ˇ CKRATNE NAKLJU ˇ CNE SPREMENLJIVKE



Korelacijski koeficient C XY ρ XY = σ X σ Y



Z ∞ Z 1 3 1 x K 2 1

X 2 2 2 = x p X ( x ) dx = x K dx = K = (1 + 1) = =

−∞ 3 3 3 3 − 1 − 1

Z Z 0 ∞ Z 1

Y 2 2 2 2 = y p Y ( y ) dy = y K ( y + 1) dy + yK(2 − y) dy

−∞ −1 0

y 4 0 ! ! 3 0 3 1 4 1 y y y

= K + + K 2 −

4 3 3 4 − 1 − 1 00

1 1 2 1 1 1

= K − + + K − = K =

4 3 3 4 2 4

q 2 1 1 3

r √

σ 2 = X − X = − 0 = √ =

X 3 3 3

s √

q 2 r 2 1 1 3 3

σ 2 = Y − Y = − = =

Y 4 4 16 4



C 1 1 XY 6 6 √ 4

ρXY = = √ = = = 3 σ 2

X 3 σ 3 Y 6 3 · 12 3 4



Pogojna gostota verjetnosti p y (y |x)



pXY (x, y)

p Y (y | x) =

pX(x)

0

x ≤ −1 ∪ x > 1 : pXY (x, y) = 0, pX(x) = 0 ⇒ pY (y | x) =

0

− 1 < x ≤ 0 :

(

K ; x ≤ y ≤ x + 1

p XY (x, y) = , pX (x) = K

0 ; sicer



p ( K XY K ( x, y) ; x ≤ y ≤

p Y (y | x) = = 0 x + 1

pX(x) ; sicer K

(

1 ; x ≤ y ≤ x + 1

p Y (y | x) =

0 ; sicer

0 < x ≤ 1 :

(

K ; 0 ≤ y ≤ 1

p XY (x, y) = , pX (x) = K

0 ; sicer

p ( K ( x, y ) ; 0 ≤ y ≤ 1

p XY K ( y | x ) = =

Y 0 p X ; ( x ) sicer

K

(

1 ; 0 ≤ y ≤ 1

p Y (y | x) =

0 ; sicer



NALOGE 31



PXY (x, y) Skupna porazdelitev dveh spremenljivk

P P X XY y ( x ) = P (x, y) Marginalna porazdelitev X iz skupne (diskretni

primer)

R P P xy i j i j XY i j Korelacija (diskretno) = x y P ( x , y )

C ¯ ¯ xy = R xy − X Y Kovarianca (diskretna)

ρ Cov(X,Y ) XY σX =

σ Korelacijski koeficient

Y

p p(x,y) ( y | x ) = Pogojna gostota — za zvezne spremenljivke

p x(x)

p 1 ( x, y ) = Enakomerna gostota v zveznem primeru

ploˇsˇcina



4. POGLAVJE



AVTOKORELACIJA



V tretjem poglavju smo spoznali korelacijo kot orodje za merjenje odnosa med dvema spremenljivkama. Z njeno pomoˇcjo smo ugotavljali, ali sta spremenljivki povezani, in ali morda obstaja takˇsna povezava, da lahko eno izmed njiju izrazimo z drugo. Takˇsna reduk-cija dimenzij ni zgolj matematiˇcna eleganca, ampak tudi praktiˇcna prednost — omogoˇca uˇcinkovitejˇso predstavitev podatkov in bolj kompaktno kodiranje.

V tem poglavju bomo naredili pomemben korak naprej: spoznali bomo avtokorelacijo.

Gre za koncept, ki je v osnovi podoben korelaciji, vendar se ne osredotoˇca na povezavo med dvema razliˇcnima spremenljivkama, temveˇc raziskuje odnos znotraj ene same spre-menljivke skozi ˇcas.

Zanimalo nas bo:

ali obstajajo ponavljajoˇci se vzorci,

ali se vrednosti v preteklosti ujemajo z vrednostmi v prihodnosti,

ali obstaja periodiˇcnost, sezonskost ali trendi,

in ali lahko iz preteklosti napovemo prihodnost.

Avtokorelacija ima kljuˇcno vlogo pri analizi ˇcasovnih vrst, kjer zaporedje podatkov

ni nakljuˇcno, temveˇc nosi strukturo — red, ki ga lahko odkrijemo in izkoristimo. Zato bomo v tem poglavju naredili odmik od abstraktnih primerov in pokazali praktiˇcno uporabo avtokorelacije na realnih ˇcasovnih nizih.

To poglavje bo tako predstavljalo pomemben prehod iz teoretiˇcnih temeljev v svet

praktiˇcne analize podatkov — tam, kjer informacije postanejo uporabne.

M. Kunaver, Teorija informacij in izvorno kodiranje. 33

©2025 Zaloˇzba FE

34 AVTOKORELACIJA



Casovne vrste in model ARIMA ˇ

Casovna vrsta ˇ je zaporedje opazovanj, ki so zbrana skozi ˇcas v enakomernih ˇcasovnih intervalih (npr. dnevno, meseˇcno, letno). V kontekstu elektrotehnike in informatike se ˇcasovne vrste pogosto pojavljajo v obliki signalov, meritev, prometnih tokov, obremenitev, ˇstevila dogodkov ali ekonomskih indikatorjev.



Sestavni deli ˇcasovne vrste Veˇcina realnih ˇcasovnih vrst vkljuˇcuje veˇc naslednjih kom-

ponent:

Trend – dolgoroˇcna usmerjenost serije (naraˇsˇcanje ali upadanje),

Sezonskost – periodiˇcno ponavljanje vzorcev (npr. vsakih 12 mesecev),



Nakljuˇcna komponenta (preostanek) – nestrukturirani ostanki, ki jih ni mogoˇce pojasniti z modelom,

Cikliˇcnost – dolgoroˇcni neperiodiˇcni valovi (npr. gospodarski cikli).



Modeli ˇcasovnih vrst Glavni cilj analize ˇcasovne vrste je napovedovanje prihodnjih

vrednosti na podlagi zgodovinskih podatkov. Eden najpogosteje uporabljenih modelov za to je ARIMA.



Kako deluje model ARIMA



Model ARIMA (Autoregressive Integrated Moving Average) omogoˇca modeliranje in napove-dovanje ˇcasovnih vrst s kombinacijo treh komponent: avtoregresije (AR), integracije (I) in drseˇcega povpreˇcja (MA). Vsaka komponenta ima svojo vlogo pri razlagi strukture serije:



AR (autoregressive) – model predpostavi, da je trenutna vrednost odvisna od pretek-lih vrednosti ˇcasovne vrste.



I (integrated) – predstavlja ˇstevilo razlikovanj (diferenc), potrebnih za dosego sta-cionarnosti.

MA (moving average) – modelira odvisnost trenutne vrednosti od preteklih napak napovedi.



Model ARIMA je oznaˇcen s trojico parametrov (p, d, q), kjer:

p doloˇca ˇstevilo avtoregresivnih zaostalih vrednosti (lagov),



d doloˇca ˇstevilo razlikovanj serije,

q doloˇca ˇstevilo zaostalih napak v modelu.



Avtoregresivni (AR) del Vrednost ˇcasovne vrste Xt modeliramo kot linearno kombi-nacijo preteklih vrednosti:



Xt = ϕ1Xt−1 + ϕ2Xt−2 + . . . + ϕpXt−p + εt

Torej, parameter p doloˇca, koliko zadnjih vrednosti serije model upoˇsteva za napoved

trenutne vrednosti. Te vrednosti se imenujejo lag-i, uteˇzi ϕi pa model izraˇcuna med uˇcenjem.

35



Integrirani (I) del ˇ Ce serija ni stacionarna, uporabimo razlikovanje:



Y t = Xt − Xt −1

Za veˇcjo stopnjo trenda ali sezonskosti uporabimo viˇsji nivo odvoda d:



Z d = ∇X

t t



kjer je ∇ uporabljena kot:

∇Xt = Xt − Xt −1.

S tem pretvorimo nestacionarno serijo v stacionarno, ki je primerna za AR in MA mod-

eliranje.



Drse ˇce povpre ˇcje (MA) del Model predpostavi, da je trenutna vrednost odvisna tudi od

preteklih napak (reziduumov):



Xt = θ1εt−1 + θ2εt−2 + . . . + θq εt−q + εt

Torej q doloˇca, koliko preteklih napak napovedi model uporablja. Uporaba napak

omogoˇca kompenzacijo nepojasnjenih nihanj in boljˇso prileganje.



Kako model napove novo vrednost Za vsak ˇcasovni trenutek t, model izraˇcuna napovedano vrednost ˆ X t s kombinacijo:



1. zadnjih p vrednosti serije (X t−1, . . . , Xt−p),

2. zadnjih q napak (εt−1, . . . , εt−q),

3. po potrebi razlikovane serije, ˇce d > 0.



Npr. ARIMA(2,1,1) modelira:



∆X t = ϕ1∆Xt−1 + ϕ2∆Xt−2 + θ1εt−1 + εt

Kar pomeni:



Predhodno se izraˇcuna razlika ∆Xt = Xt − Xt −1,

Nato se uporabi 2 pretekli razliki ( ∆Xt−1, ∆Xt−2) in 1 prejˇsnja napaka za izraˇcun nove vrednosti,

Napoved se rekonstruira z obratnim razlikovanjem.



Zna ˇcilnosti modela ARIMA

Uˇcinkovit za modeliranje nelinearnih trendov in sezonskih pojavov (v kombinaciji z razˇsiritvami, npr. SARIMA),

Temelji na predpostavki stacionarnosti — podatke pogosto predhodno transformi-ramo,

Primeren za enodimenzionalne serije, kjer so vzorci izraˇzeni skozi ˇcas.

ARIMA je robusten model za mnoge vrste podatkov, ˇse posebej ko ni izrazite sezonskosti. Pri sezonskih podatkih se pogosto uporablja njegova razˇsiritev SARIMA.

36 AVTOKORELACIJA



Primer - analiza ˇstevila potnikov v letalskem prometu



Analiza ˇcasovnih vrst je eno najmoˇcnejˇsih statistiˇcnih orodij, saj nam omogoˇca, da na podlagi preteklih meritev napovemo prihodnje vrednosti. Uporablja se na razliˇcnih po-droˇcjih — od napovedovanja vremenskih pojavov in finanˇcnih trendov do analize prometa in proizvodnih procesov.

V tej vaji si bomo ogledali primer ˇstevila letalskih potnikov na meseˇcni ravni. Na

tem primeru bomo prikazali kljuˇcne korake priprave, ˇciˇsˇcenja in modeliranja podatkov za napovedovanje prihodnjih vrednosti.

Preden se lotimo celotne procedure razloˇzimo kaj je naˇs cilj. S pomoˇcjo statistiˇcne

analize in manipulacije podatkov ˇzelimo izdelati model s pomoˇcjo katerega bomo sposobni napovedati naslednje ˇstevilo potnikov. Naˇso uspeˇsnost bomo vrednotili tako, da bomo dejanske podatke primerjali z naˇsimi napovedmi in pri tem uporabili merilo koren srednje kvadratne napake.



Korak 1: Uvoz in vizualizacija podatkov



Zaˇcnemo z uvozom podatkov, ki so podani v obliki CSV datoteke. Te podatke shranimo v razpredelnico s ˇcasovno osjo kot indeksom, nato pa jih tudi grafiˇcno prikaˇzemo. ˇ Ze ob prvem pogledu lahko opazimo rast ˇstevila potnikov ter ponavljajoˇco se sezonskost.



Opis podatkov

Casovno obdobje: ˇ januar 1949 – december 1960



ˇStevilo opazovanj: 144 (meseˇcnih)

Frekvenca: meseˇcna (12 opazovanj na leto)



Spremenljivka: ˇstevilo potnikov, predstavljeno kot celo, pozitivno ˇstevilo



37



Teko e povpre je in standardni odklon



600 Original Rolling Mean Rolling Std

500



ov 400



300



tevilo potnik

200



100



0

1950 1952 1954 1956 1958 1960

Leto



Opazka: Serija oˇcitno ni stacionarna — ima trend in sezonske vzorce, kar pomeni, da

je ni mogoˇce neposredno uporabiti za veˇcino statistiˇcnih metod ˇcasovne analize. VIdimo predvsem, da povpreˇcje (rdeˇca) strmo naraˇsˇca, prav tako pa tekoˇca standardna deviacija (ˇcrna, predstavlja standardno deviacijo zadnjih 12 mesecev) prav tako ni stabilna (ravna).



Korak 2: Preverjanje stacionarnosti



Stacionarnost pomeni, da se povpreˇcje in varianca serije ne spreminjata skozi ˇcas. ˇ Ce tega pogoja ni, bo napovedovanje manj zanesljivo. Za preverjanje uporabimo Dickey–Fullerjev test.

Test vrne naslednje kljuˇcne vrednosti:

Testno statistiko, ki jo uporabimo za primerjavo s kritiˇcnimi vrednostmi,



p-vrednost, ki nam pove, ali lahko zavrnemo hipotezo o nestiacionarnosti (obiˇcajno pri p ¡ 0.05),



Kritiˇcne vrednosti za 1%, 5% in 10% - ˇce je statistika manjˇsa od kritiˇcne vrednosti, lahko zavrnemo hipotezo o nestiacionarnosti. (drugaˇce povedano - ˇce je statistika manjˇsa od kritiˇcne vrednosti na 5% nivoju, lahko z 95% gotovostjo trdimo, da je serija stacionarna).

V naˇsem primeru dobimo sledeˇce rezultate:



Results of Dickey-Fuller Test:

38 AVTOKORELACIJA



Test Statistic 0.815369

p-value 0.991880

#Lags Used 13.000000

Number of Observations Used 130.000000

Critical Value (1%) -3.481682

Critical Value (5%) -2.884042

Critical Value (10%) -2.578770

dtype: float64



Kot vidimo ni testna statistika manjˇse od nobene kritiˇcne vrednosti, kar pomeni da po-

datki niso stacionarni in jih poslediˇcno ne moremo direktno uporabiti v ˇcasovni vrsti. Naˇsa naloga je sedaj, da s pomoˇcjo orodij kot so odvajanje, logaritmiranje in drseˇce povpreˇcje, serijo transformiramo v stacionarno obliko.

Opazka: Uporabiti smemo samo reverzibilne transformacije, da bomo kasneje sposobni

naˇse napovedi vrniti v prvotno obmoˇcje.



Korak 3: Transformacije za dosego stacionarnosti

Ker serija vsebuje trend in sezonskost, jo moramo transformirati. Moˇzne strategije vkljuˇcujejo:



Table 4.1: Pogoste transformacije ˇcasovnih vrst za dosego stacionarnosti



Transformacija Matematiˇcna oblika Namen / uˇcinek



Logaritemska yt = log(xt) Zmanjˇsanje variabilnosti, ob-

pretvorba vladovanje eksponentne rasti



Drseˇce povpreˇcje 1 Pk−1 y t k i=0 t− = x i

Glajenje kratkoroˇcnih nihanj,

odstranjevanje ˇsuma



Eksponentno uteˇzeno yt = αxt + (1 − Glajenje podatkov z veˇcjim

povpreˇcje (EMA) α)yt−1 poudarkom na novejˇsih vrednostih



Diferenciranje yt = xt − xt −1 Odstranjevanje trenda, doseganje

stacionarnosti



Razstavljanje v kom- x t = Tt + St + Rt Analiza posameznih komponent: ponente trend, sezona, ostanek



Po vsaki transformaciji (ali kombinaciji veˇcih transformacij) izvedemo Dickey–Fullerjev

test, da preverimo, ali je serija postala dovolj stacionarna za izdelavo modela ˇcasovne vrste.

Za prvi poskus podatke samo logaritmiramo



39



6.50 Logaritmirani vhodni podatki Teko e povpre je in standardni odklon

Logaritmirani podatki Original

Drse e povpre je 6 Rolling Mean

6.25 Rolling Std

6.00 5

ov 5.75 ov 4

5.50 3

tevilo potnik tevilo potnik 5.25 2

5.00

1

4.75

0

1950 1952 1954 1956 1958 1960 1950 1952 1954 1956 1958 1960 Leto Leto



Logaritmirani podatki



Po statistiˇcnem testu dobimo sledeˇce rezultate:

Results of Dickey-Fuller Test:

Test Statistic -1.717017

p-value 0.422367

#Lags Used 13.000000

Number of Observations Used 130.000000

Critical Value (1%) -3.481682

Critical Value (5%) -2.884042

Critical Value (10%) -2.578770

dtype: float64

In ugotovimo, da ˇse vedno ni stacionarna. Smo pa bliˇzje kot prej, saj se je sedaj testna statistika vsaj pribliˇzala kritiˇcni vrednosti na 10% nivoju.

Nadaljujemo s kombinacijo logaritmiranja in uporabo (odstranitvijo) 12-meseˇcnega drseˇcega

povpreˇcja.



6.50 Logaritmirani vhodni podatki Teko e povpre je in standardni odklon

Logaritmirani podatki

6.25 Drse e povpre je 0.3

6.00 0.2

ov 5.75 ov

0.1

5.50

tevilo potnik tevilo potnik 0.0 5.25

5.00 0.1

4.75 Rolling Mean 0.2 Original

Rolling Std

1950 1952 1954 1956 1958 1960 1950 1952 1954 1956 1958 1960

Leto Leto



Odstranjeno drseˇce povpreˇcje



Opazka: Leva slika je ista, saj gre ˇse vedno za logartimirane podatke. Spremeni pa

se desna slika, kjer smo sedaj odˇsteli 12-meseˇcno drseˇce povpreˇcje. Po statistiˇcnem testu dobimo sledeˇce rezultate:

40 AVTOKORELACIJA



Results of Dickey-Fuller Test:

Test Statistic -3.162908

p-value 0.022235

#Lags Used 13.000000

Number of Observations Used 119.000000

Critical Value (1%) -3.486535

Critical Value (5%) -2.886151

Critical Value (10%) -2.579896

dtype: float64



To je velik bolje, saj lahko sedaj z 95% gotovostjo trdimo, da je serija stacionarna. Ven-

dar pa ˇse vedno lahko rezultat ˇse izboljˇsamo, ˇce uporabimo eksponentno uteˇzeno povpreˇcje (EWMA), ki pripisuje veˇcjo teˇzo zadnjim vrednostim.



6.50 Odstranjeno eksponentno povpre je Teko e povpre je in standardni odklon

0.4 Original

6.25 Rolling Std Rolling Mean

0.3

6.00

0.2

ov 5.75 ov

5.50 0.1

tevilo potnik tevilo potnik 0.0 5.25

5.00 0.1

4.75

0.2

1950 1952 1954 1956 1958 1960 1950 1952 1954 1956 1958 1960

Leto Leto



Odstranjeno eksponentno uteˇzeno povpreˇcje



Po statistiˇcnem testu dobimo sledeˇce rezultate:



Results of Dickey-Fuller Test:

Test Statistic -3.566092

p-value 0.006443

#Lags Used 13.000000

Number of Observations Used 130.000000

Critical Value (1%) -3.481682

Critical Value (5%) -2.884042

Critical Value (10%) -2.578770

dtype: float64



Kar pomeni da je naˇsa serija sedaj stacionarna z 99% gotovostjo. S samimi transformaciji bi sedaj teˇzko ˇse kaj izboljˇsali doseˇzeni rezultat, zato preidemo na odstranjanje sezonskosti.



Korak 4: Odprava sezonskosti

Naslednji korak je odprava sezonskih vzorcev z diferenciranjem:



X ′(t) = X(t) − X(t − 1)

41



Z odˇstevanjem zamaknjene vrednosti tako skuˇsamo odstraniti sezonske vplive (v resnici

je to podobno, kot ˇce bi odvajali naˇse podatke). Po tem koraku ponovno izvedemo Dickey–Fullerjev test, da preverimo, ali je serija ˇse vedno stacionarna.



Odstranjena razlika med zaporednimi vrednostmi Teko e povpre je in standardni odklon

0.2 0.2



0.1 0.1

ov ov

0.0 0.0

tevilo potnik tevilo potnik

0.1 0.1



0.2 Rolling Mean 0.2 Rolling Std Original

1950 1952 1954 1956 1958 1960 1950 1952 1954 1956 1958 1960

Leto Leto



Odstranjeno eksponentno uteˇzeno povpreˇcje



Po statistiˇcnem testu dobimo sledeˇce rezultate:



Results of Dickey-Fuller Test:

Test Statistic -2.649973

p-value 0.083102

#Lags Used 14.000000

Number of Observations Used 128.000000

Critical Value (1%) -3.482501

Critical Value (5%) -2.884398

Critical Value (10%) -2.578960

dtype: float64



Vidimo, da smo naˇs rezultat sedaj dejansko poslabˇsali saj je testna statistika slabˇsa kot prej. To lahko nakazuje na to, da naˇsi podatki nimajo sezonskih vzorcev ALI pa vsebujejo kompleksnejˇse primere, ki jih z enostavnim diferenciranjem ne moremo odstraniti. Glede na to, da za naˇse podatke vemo, da predstavljajo letno ˇstevilo potnikov, lahko sklepamo da se naˇsi vzorci pojavljajo na letni ravni (torej npr. sklepamo de veliko veˇc ljudi leti v ˇcasu poˇcitnic).

V ta namem uporabimo namensko orodje, ki nam je na voljo v okolju Python -sea-

sonal decompose, ki iz podatkov izluˇsˇci:



trendno komponento,



sezonsko komponento,



ostanek (rezidual).

Ko imamo enkrat na voljo ostanek (torej edini kos naˇse serije, ki ga je ˇse potrebno mod-

elirati), ponovno izvedemo Dickey–Fullerjev test, da preverimo, ali je ostanek stacionaren.



42 AVTOKORELACIJA



Teko e povpre je in standardni odklon

6 Original

0.075

5

1950 0.050 1952 1954 1956 1958 1960



0.1 0.025 Trend ov 0.000

0.2 1950 0.0

1952 1954 1956 1958 1960 Sezonskost 0.025 tevilo potnik

0.0



0.0 1950 1952 1954 1956 1958 1960 0.075 Original Rolling Mean 0.100 0.2 0.050

Rolling Std

0.1 1950 1952 1954 1956 1958 1960 1950 1952 1954 1956 1958 1960 Leto



Odstranjena sezonskost



Dobimo sledeˇce rezultate:

Results of Dickey-Fuller Test:

Test Statistic -6.610539e+00

p-value 6.393663e-09

#Lags Used 9.000000e+00

Number of Observations Used 1.220000e+02

Critical Value (1%) -3.485122e+00

Critical Value (5%) -2.885538e+00

Critical Value (10%) -2.579569e+00

dtype: float64



Sedaj lahko z gotovostjo trdimo, da je ostanek stacionaren. To pomeni, da smo uspeˇsno odstranili sezonske vzorce in trendne komponente, kar nam omogoˇca nadaljnje modeli-ranje.



Korak 5: Gradnja modela ˇcasovne vrste

Zdaj, ko imamo stacionarno serijo, lahko preidemo na modeliranje. Uporabili bomo ARIMA-model, ki je doloˇcen s trojico parametrov (p, d, q):



p: ˇstevilo avtoregresivnih zamikov (ACF),



d: stopnja diferenˇcne transformacije,



q: ˇstevilo zamikov napak (PACF).



Parameter d ˇze poznamo iz prejˇsnjega koraka (npr. ena diferenˇcna stopnja pomeni d =

1). Za doloˇcitev p in q uporabimo avtokorelacijo in delno avtokorelacijo. Poiˇsˇcemo toˇcko, kjer funkcija prviˇc pade pod interval zaupanja (ˇcrtkasta ˇcrta na sliki). V naˇsem primeru dobimo p = 2, q = 2.



43



Avtokorelacijska funkcija Delna avtokorelacijska funkcija

1.0 1.0



0.8 0.8



0.6

0.6

0.4

0.4

0.2

0.2

0.0



0.0 0.2



0.2 0.4



0.4 0.6 0 5 10 15 20 0 5 10 15 20



Tako lahko sedaj ovrednotimo tri razliˇcne modele:

AR-model (samo avtoregresija): (2, 0, 0),



MA-model (samo napake): (0, 0, 2),

ARIMA-model (kombinirano): (2, 0, 2).



Vsak model bomo vrednotili z vsoto kvadratnih napak (RSS):



Mera napake: vsota kvadratov rezidualov (RSS)



Mera RSS (Residual Sum of Squares) je ena izmed osnovnih metrik za ocenjevanje kakovosti napovedi v modeliranju ˇcasovnih vrst. Predstavlja vsoto kvadratov razlik med dejanskimi vrednostmi in napovedmi.

Enaˇcba:

n

RSS = X 2 ( x − x ˆ )

t t

t=1

kjer je:



x t — dejanska (opazovana) vrednost v trenutku t,



x ˆ t — napovedana vrednost modela v trenutku t,

n — skupno ˇstevilo opazovanj.

Lastnosti:



Ni negativna: RSS ≥ 0,

Manjˇsa vrednost RSS pomeni boljˇse prileganje modela,

44 AVTOKORELACIJA



Zelo obˇcutljiva na velike napake (zaradi kvadriranja),



Pogosto se uporablja v kombinaciji z RMSE ali AIC.



Korak 6: Napoved in ovrednotenje modela



Pri vrednotenju modela se osredotoˇcimo na naˇs ”ostanek” (rezidual), ki je rezultat odstran-itve trenda in sezonskosti. ˇ Ce namreˇc ˇzelimo, da bo naˇs model pravilen, mora biti sposoben pravilno napovedati ostanek, saj bomo ostale podatke vrnili z uporabo obratnih procesov (priˇsteli bomo nazaj trend, sezonskost in po potrebo podatke potencirali).



RSS: 1.5138



0.2



0.1



0.0

Odstopanja



0.1



0.2 data fitteed values

1950 1952 1954 1956 1958 1960

Leto



AR model (2,0,0)



45



RSS: 1.4721



0.2



0.1



0.0

Odstopanja



0.1



0.2 data fitted data

1950 1952 1954 1956 1958 1960

Leto



MA model (0,0,2)



RSS: 1.3779



0.2



0.1



0.0

Odstopanja



0.1



0.2 data fitted data



1950 1952 1954 1956 1958 1960

Leto



ARIMA model (2,0,2)

Priˇcakovano ugotovimo, da je ARIMA model najboljˇsi od treh saj uporabi vse prednosti

modela. Ko imamo tako izbran model se lahko lotimo ˇse celotnega procesa rekonstrukcije 46 AVTOKORELACIJA



podatkov ter konˇcnega vrednotenja modela z uporabo korena srednje kvadratne napake (RMSE).



Korak 7: Rekonstrukcija in vrednotenje

Za ovrednotenje natanˇcnosti modela uporabimo RMSE — koren srednje kvadratne na-pake:





v


u n 1

RMSE u X 2 = ( y − y ˆ )

t t t n

t=1

kjer je:



yt — dejanska (opazovana) vrednost v trenutku t,

y ˆ t — napovedana vrednost modela v trenutku t,

n — skupno ˇstevilo opazovanj.

Ob tem se moramo zavedati, da moramo za vsako vrednotenje podatke, dobljene z

ARIMA modelom najprej vrniti v prvotno obmoˇcje.

Za prikaz, kako izbira modela in transformacije vpliva na konˇcno natanˇcnost ne bomo

ovrednotili samo najboljˇsega (torej modela z odstranjeno sezonskostjo), temveˇc tudi ostale modele, ki smo jih ustvarili v prejˇsnjih korakih.

Prvi model bo tako ARIMA(2,0,2), kjer smo za vhodne podatke uporabili samo logarit-

mirane podatke brez odstranjene sezonskosti. Za vrednotenje moramo torej vsak napovedani podatek potencirati z osnovo e. Dobljeni rezultat sicer izgleda, kot da sledi izvornim po-datkom, vendar je RMSE precej visok (30.11).



RMSE: 30.1187



600 data ARIMA data



500



ov

400



tevilo potnik 300



200



100

1950 1952 1954 1956 1958 1960

Leto

47



Rekonstrukcija - logaritmiran vhod



Preden smo se lotili odstranjevanja sezonskosti, smo ugotovili, da smo najveˇcjo sta-

cionarnost dosegli, ˇce smo odˇsteli eksponentno drseˇce povpreˇcje. ˇ Ce uporabimo te po-datke kot vhod za naˇs model dobimo ˇze malo boljˇsi razultat (RMSE = 27.5), ki nekako predstavlja tudi najboljˇse, ker lahko doseˇzemo, ˇce zanemarjamo sezonskost.



RMSE: 27.5183



600 originalni podatki ARIMA + EWMA



500



ov

400



tevilo potnik 300



200



100

1950 1952 1954 1956 1958 1960

Leto



Rekonstrukcija - logaritmiran vhod z odˇstetim eksponentnim uteˇzenim povpreˇcjem



V prvem poskusu odstranjevanja sezonskosti smo uporabili samo diferenciranje (odˇstevanje

zamaknjene vrednosti) in pokazali, da smo s tem dejansko pokvarili stacionarnost naˇsih podatkov. Priˇcakovano se zato pokvari tudi rezultat modela, ki sedaj ne vrne uporabnih podatkov (RMSE = 179.2).



48 AVTOKORELACIJA



RMSE: 179.2465



600 originalni podatki ARIMA na prvi razliki



500



ov

400



tevilo potnik 300



200



100

1950 1952 1954 1956 1958 1960

Leto



Rekonstrukcija - diferenciranje



Za konec uporabimo ˇse naˇse najoljˇse vhodne podatke - logaritmirane podatke z odstran-

jeno sezonskostjo. ˇ Ze na sliki takoj vidimo, da model sledi izvornim podatkom, mera RMSE (11.89) pa pokaˇze da smo skoraj trikrat boljˇsi kot pri najboljˇsem modelu brez se-zonskosti.



49



RMSE: 11.8966



600 originalni podatki ARIMA + sezonskost



500



ov

400



tevilo potnik 300



200



100

1950 1952 1954 1956 1958 1960

Leto



Rekonstrukcija - odstranjena sezonskost



Sklep



V tem poglavju smo pokazali, kako nam poznavanje lastnosti podatkov omogoˇca, da jih uporabimo za napovedovanje prihodnjih vrednosti. Tu nam predvsem pomaga avtoko-roelacija, ki podatke primerja same s seboj in nam tako omogoˇca, da najdemo vzorce, ki jih lahko uporabimo za napovedovanje. S pomoˇcjo avtokorelacije in delne avtokorelacije smo prikazali celotni proces priprave vhodnih podatkov, izdelave ARIMA modela ter pravilne rekonstrukcije napovedanih vrednosti.

Predstavljena metoda (poleg same didaktiˇcne vrednosti za prikaz uporabnosti avtoko-

relacije) je pogosto uporabljana tako v financah (napoved vrednosti delnic), telekomunkaci-jah (napoved obremenitve omreˇzja), meteorologiji (napoved vremena) in mnogih drugih podroˇcjih, kjer so podatki ˇcasovno odvisni.

V tej vaji smo predstavili celoten proces analize ˇcasovne vrste — od vizualizacije do

napovedi. Uporabili smo realne podatke in pokazali, kako pomembna je stacionarnost za uspeˇsno modeliranje. Prav tako smo videli, kako kompleksne strukture (sezonskost, trendi) zahtevajo veˇc korakov ˇciˇsˇcenja in predobdelave.

Za tiste, ki se ˇzelijo v metodo bolje poglobiti je v dodatku na voljo tudi s pomoˇcjo

katere smo izvedli celotno poglavje. Za dodatno branje priporoˇcamo naslednje vire:



S. Haykin: Communication Systems, 5th ed. [7]



5. POGLAVJE



INFORMACIJA IN ENTROPIJA



V tem poglavju bomo z reˇsevanjem nalog prikazali, kako merimo koliˇcino informacije in izraˇcunamo entropijo v razliˇcnih verjetnostnih sistemih. V kontekstu teorije informacij in-formacija meri koliˇcino preseneˇcenja oziroma negotovosti, ki jo povzroˇci pojav doloˇcenega dogodka. Entropija pa predstavlja povpreˇcno informacijo oziroma negotovost, ki je pris-otna v danem verjetnostnem sistemu.

Za posamezen dogodek x z verjetnostjo P(x) definiramo informacijo kot:



I(x) = log2 P 1

(x)



To pomeni, da redkejˇsi dogodki nosijo veˇcjo informacijo.

Ce imamo diskretno nakljuˇcno spremenljivko ˇ X, definiramo njeno entropijo kot povpreˇcno

informacijo vseh moˇznih vrednosti:



H (X ) = P (xi) · X X I ( x i i 2 ) = − P (x ) log P (x i

)

i i



Entropija je najveˇcja, ko so vsi dogodki enako verjetni, in znaˇsa log n, kjer je n ˇstevilo 2

moˇznih vrednosti.

Ko imamo opravka z dvema spremenljivkama, nas zanima tudi skupna entropija:



H X ( X, Y ) = − P(x, y) log P (x, y)

2

x,y



M. Kunaver, Teorija informacij in izvorno kodiranje. 51

©2025 Zaloˇzba FE

52 INFORMACIJA IN ENTROPIJA



ter pogojna entropija:



H (Y |X) = H (X, Y ) − H(X )



Ta pove, koliko negotovosti ostane v Y , ˇce ˇze poznamo X.

Razumevanje teh konceptov je kljuˇcno za kodiranje z minimalno povpreˇcno dolˇzino,

konstrukcijo optimalnih kodov (npr. Huffman) in za ocenjevanje izgub pri prenosu infor-macij.

Za dodatno branje priporoˇcamo naslednje vire:



T. M. Cover, J. A. Thomas: Elements of Information Theory [2]



D. J. C. MacKay: Information Theory, Inference, and Learning Algorithms [3]

N. Paveˇsiˇc: Informacija in kodi [6]



5.1 Naloge



Naloga 5.1: Glavni dobitek pri lotu je sedmica - kombinacija 7 ˇstevil iz razpona

[1, 39]. Izraˇcunaj informacijo pravilne kombinacije. Izraˇcunaj tudi informacijo ostalih

kombinacij.



Reˇsitev: Najprej rabimo podatek o vseh moˇznih kombinacijah, ki jih lahko izberemo



39 39!

N = = = 15380937

7 (39 − 7)!7!



Verjetnost je za vsako kombinacijo enaka.



P 1 1 −8 = = = 6 , 5 · 10 N 15380937

Informacija pravilne kombinacije je torej:

1

I = log = log 15380937 = 23,87 2 2 sh

P



Naloga 5.2: Diskretna spremenljivka X, xi ∈ {1, 2, . . . , 6}. Verjetnost simbolov je

podana z Px(xi) = P .



P = [0,35 0,35 0,1 0,1 0,05 0,05]



Izraˇcunaj informacijo posamezne vrednosti, njeno povpreˇcno vrednost ter entropijo.



Reˇsitev: Pri neenakomerni porazdelitvi vsaka vrednost prispeva razliˇcno informa-

cijo. Najpogostejˇse vrednosti imajo manjˇso informacijo, redkejˇse veˇcjo. Entropija

NALOGE 53



H (X ) je povpreˇcna informacija:



H (X ) = P(xi) · log = P 2X(xi) · IX(xi) P X X 1

i (xi) i

Najprej izraˇcunamo informacijo posameznih vrednosti:



I = log2 P 1

I = [1,515 1,515 3,322 3,322 4,322 4,322 4,322]



Sedaj lahko izraˇcunamo ˇse entropijo:



H (X ) = 0,35 · 1,515 + 0,35 · 1,515 + 0,1 · 3,322 + 0,1 · 3,322

+ 0,05 · 4,322 + 0,05 · 4,322

H (X ) = 2,16



Naloga 5.3: Nakljuˇcni spremenljivki X, Y = 1, 2, 3, 4, 5 sta podani z vezano verjet-

nostjo funkcijo, podani v obliki matrike



  1 1 1 1 1

  0 1 2 1 0

1  

P   ( x , y ); P = 2 0 2 1 1

XY i j XY   25

 

  0 3 1 2 2

 

0 0 1 1 0



Izraˇcunajte entropiji posameznih spremenljivk H (X ) in H (Y ). Katera spre-menljivka je bolj nedoloˇcena?



Izraˇcunajte vezano entropijo H (X, Y ). Kakˇsna je relacija med vezano in en-tropijo posamezne spremenljivke.



Doloˇcite matriko pogojne verjetnosti P K

P XY (xi, yj)

PY (yj | xi) =

P X (xi)

  P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x )

Y 1 1 Y 2 1 Y 3 1 Y 4 1 Y 5 1

  P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x )

  Y 1 2 Y 2 2 Y 3 2 Y 4 2 Y 5 2

P   K  P = ( y | x ) P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x )

Y 1 3 Y 2 3 Y 3 3 Y 4 3 Y 5 3 

 

  P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x ) P ( y | x )

 Y 1 4 Y 2 4 Y 3 4 Y 4 4 Y 5 4 

PY (y1 | x5) PY (y2 | x5) PY (y3 | x5) PY (y4 | x5) PY (y5 | x5)



54 INFORMACIJA IN ENTROPIJA



Reˇsitev: Iz tabele skupne verjetnosti izraˇcunamo marginalni porazdelitvi:



P X X ( x ) = P ( x , y ) , P ( y ) = P (x , y )

X i XY i j Y j XY i j

j i



Pogojna verjetnost:



PXY (xi, yj)

P (Y = y j | X = xi) =

PX(xi)

Entropijo dobimo kot povpreˇcno informacijo:



H (X ) = P X (xi) · log2 P X 1

X i ( x)





i




Zaˇcnemo torej z marginalnima verjetnostma PX(x) in PY (y)

1 h i 1 h i

PX = 5 4 6 8 2 PY = 3 5 7 6 4

25 25

Iz marginalnih verjetnosti izraˇcunamo informacije za posamezne vrednosti x in y:



I = − log P 2

I X = [2,32 2,64 2,06 1,64 3,64] IY = [3,06 2,32 1,84 2,06 2,64]



In za X in Y izraˇcunamo povpreˇcno informacijo:



H X X ( X ) = P ( x ) · I ( x ) H ( Y ) = P (x ) · I (x )

X i X i Y i Y i

i i

H (X ) = 2,20 H (Y ) = 2,26



Spremenljivka Y je bolj nedoloˇcena, ker ima veˇcjo entropijo.

Vezano entropijo H (X, Y ) izraˇcunamo tako, da izraˇcunamo informacijo za vsak par

vrednosti xi, yi (vsak element matrike PXY ) in nato izraˇcunamo povpreˇcno vrednost

informacije:



  4 , 64 4 , 64 4 , 64 4 , 64 4 , 64

  ∞ 4 , 64 3 , 64 4 , 64 ∞

 

I   XY  3 = , 64 ∞ 3 , 64 4 , 64 4 , 64



 

  ∞ 3 , 06 4 , 64 3 , 64 3 , 64

 

∞ ∞ 4,64 4,64 ∞



H (X, Y ) = P XY (xi, yj) · X X I (x , y ) = 4,05

XY i j

i j



Vezana entropija je veˇcja od entropije posameznih spremenljivk.

NALOGE 55



Matrika pogojne verjetnosti P K pa je:



  0 , 2 0 , 2 0 , 2 0 , 2 0 , 2

  0 0 , 25 0 , 5 0 , 25 0

 

P   = 0 , 333 0 0 , 333 0 , 167 0 , 167

K  

 

  0 0 , 375 0 , 125 0 , 25 0 , 25

 

0 0 0,5 0,5 0



I 1 ( x ) = log = log ( ( − Px)) Informacija posameznega do-

2 P(x) 2

godka

H P P ( X ) = P ( x ) I ( i i x i i ) = − P (x ) log P(x ) Entropija diskretne i 2 spre-i

menljivke

H P ( X, Y ) = − P (x, y) log P(x, y) Skupna entropija dveh spre-

x,y 2

menljivk



6. POGLAVJE



VLC KODIRANJE



V tem poglavju bomo obravnavali tehnike kodiranja, pri katerih posamezni simboli nimajo enake dolˇzine predstavitve, temveˇc se njihova kodna dolˇzina prilagaja glede na verjet-nost pojavljanja. Cilj takˇsnega kodiranja je zmanjˇsanje povpreˇcne dolˇzine predstavitve zaporedja podatkov, hkrati pa ohraniti nesporoˇcilnost (angl. prefix-free) kod.

Te tehnike temeljijo na osnovnem naˇcelu teorije informacije: bolj pogosti simboli naj

dobijo krajˇso predstavitev, manj pogosti pa daljˇso, kar vodi k veˇcji povpreˇcni uˇcinkovitosti prenosa. Takˇsne metode kodiranja so ˇse posebej uporabne pri stiskanju podatkov, brez izgube informacij.

Osredotoˇcili se bomo na dve razˇsirjeni metodi:

Huffmanovo kodiranje, ki za dano porazdelitev verjetnosti zagotovi optimalno nes-poroˇcilno kodo z najkrajˇso moˇzno povpreˇcno dolˇzino.

LZW (Lempel–Ziv–Welch) kodiranje, ki temelji na gradnji slovarja med samim kodiranjem, brez predhodnega poznavanja verjetnosti.

Poglavje bomo zaˇceli z analizo entropije in kodne redundance. Praktiˇcne naloge vkljuˇcujejo

generiranje Huffmanovih kod, oceno kodne uˇcinkovitosti ter uporabo LZW kodiranja in dekodiranja.

Pri delu bomo spoznali tudi koncept razˇsirjenih virov – s kombiniranjem osnovnih sim-

bolov v bloke daljˇse dolˇzine lahko dodatno zniˇzamo redundanco, ˇce enosimbolna Huff-manova koda ne dosega zahtevane uˇcinkovitosti.

Na koncu bomo s pomoˇcjo tabel povzemali kljuˇcne enaˇcbe, ki opisujejo povezavo med

entropijo, dolˇzino kod in redundanco.

M. Kunaver, Teorija informacij in izvorno kodiranje. 57

©2025 Zaloˇzba FE

58 VLC KODIRANJE



Za dodatno branje priporoˇcamo naslednje vire:

T. M. Cover, J. A. Thomas: Elements of Information Theory [2]

D. J. C. MacKay: Information Theory, Inference, and Learning Algorithms [3]

N. Paveˇsiˇc: Informacija in kodi [6]



6.1 Naloge



Naloga 6.1: Podane so verjetnosti simbolov informacijskega vira X = {x1, x2, . . . x6}.

Doloˇcite binarne kode za posamezne simbole z najmanjˇsim moˇznim ˇstevilom bitov,

tako da bodo imele vse kode enako dolˇzino. Izraˇcunajte entropijo informacijskega

vira. Doloˇcite Huffmanovo kodo za dani primer. Kolikˇsni sta absolutna in relativna

redundanca informacijskega vira in obeh tipov kodiranja? Kolikˇsna je uˇcinkovitost

obeh tipov kodiranja?



P X = [0,4 0,08 0,1 0,22 0,18 0,02]



Reˇsitev: Za oceno uspeˇsnosti naˇsega kodiranja moramo nujno poznati entropijo

informacijskega vira:



H X ( X ) = − P [i] · log P [i] = 2 19 ,

X 2 X





i




V primeru kodiranje je entropija vira naˇs ideal - povpreˇcno ˇstevilo bitov, ki jih vir

poˇsilja. Naˇs cilj je doseˇci, da bo povpreˇcno ˇstevilo bitov na simbol ˇcim bliˇzje entropiji

vira. Tako smo lahko prepriˇcani, da v kanal ne poˇsiljamo odveˇcnih bitov.

Ce zaˇcnemo s kodiranje s fiksno dolˇzino, za vsak simbol uporabimo enako ˇstevilo ˇ

bitov in dobimo:



Simbol Koda

x 1 000

x 2 001

x 3 010

x 4 011

x 5 100

x 6 101



Povpreˇcna dolˇzina takega kodiranja je:



n X ¯ = P [i] · n = 3

X i





i


saj smo za vsak simbol uporabili isto ˇstevilo bitov. Takoj vidimo da je ta ˇstevilka

veˇcja od entropije vira, kar pomeni, da smo v kanal poslali nekaj odveˇcnih bitov.

NALOGE 59



Huffmanovo kodiranje:

Simbole razvrstimo v tabelo glede na njihove verjetnosti od simbola z najviˇsjo ver-

jetnostjo do simbola z najniˇzjo verjetnostjo. Simboloma z najniˇzjo verjetnostjo dode-

limo logiˇcno 0 in 1 ter ju zdruˇzimo v naslednjem stolpcu. ˇ Ce je verjetnost zdruˇzenih

simbolov enaka verjetnosti katerega drugega simbola, najprej napiˇsemo verjetnost

zdruˇzenega simbola. Tako nadaljujemo, dokler ne ostaneta le ˇse dve verjetnosti

Simbol PX(xi)

x 0,4 0,4 0,4 0,4 0,6 1 1

x 0,22 0,22 0,22 0,38 1 0,4 0 4

x 0,18 0,18 0,2 1 0,22 0 5

x 0,1 0,1 1 0,18 0 3

x 0,08 1 0,1 0 2

x 0,02 0 6



Kode za posamezne simbole odˇcitamo iz tabele tako, da sledimo puˇsˇcicam. Odˇcitamo

jih v obratni smeri. Z rdeˇco je oznaˇcen primer za x 5.



Simbol Koda

x 1 0

x 2 11111

x 3 1110

x 4 10

x 5 110

x 6 11110



Povpreˇcna dolˇzina kode:



n ¯ = PX[i] · X n = 0,4 · 1 + 0,08 · 5 + 0,1 · 4 + 0,22 · 2 + 0,18 · 3 + 0,02 · 5 i





i


= 2,28



Sedaj lahko izraˇcunamo redundanco informacijskega vira, kjer primerjamo entropijo

vira z entropijo idealnega vira (kjer so vsi simboli enako verjetni):



DIV = Hmax − H = log L − H = log 6 − 2,19 = 0,39 2 2



DIV 0,39

RIV = = = 0,15

Hmax log 6 2

Redundanca kodiranja s kodo konstantne dolˇzine (Constant Length Code):



DCLC = ¯ n − H = 3 − 2,19 = 0,81



DCLC 0,81

RCLC = = = 0,27

n ¯ 3

60 VLC KODIRANJE



Uˇcinkovitost kodiranja (kako blizu smo entropiji vira) s kodo konstantne dolˇzine

(Constant Length Code):



H 2,19

ηCLC = = = 0,73

n ¯ 3

Redundanca kodiranja s kodo spremenljive dolˇzine (Variable Length Code):



DV LC = ¯ n − H = 2,28 − 2,19 = 0,09



DV LC 0,09

RV LC = = = 0,04

¯ n 2,28

Uˇcinkovitost kodiranja s kodo spremenljive dolˇzine (Variable Length Code):



H 2,19

ηV LC = = = 0,96

n ¯ 2,28



Naloga 6.2: Izraˇcunajte entropijo ikone, ki je kodirana s ˇstirimi biti na slikovno toˇcko

(0 – ˇcrna, 8 – bela). Kolikˇsno je teoretiˇcno najmanjˇse moˇzno ˇstevilo bitov na slikovno

toˇcko, da pri kodiranju ˇse ne pride do izgube informacije? Doloˇcite Huffmanovo

kodo za dani primer in izraˇcunajte povpreˇcno ˇstevilo bitov na toˇcko. Kolikˇsna je

redundanca dobljene Huffmanove kode? (Da bo vaja krajˇsa, jo izraˇcunajte le za prvih

6×6 toˇck)





Reˇsitev: Za vsako moˇzno vrednost toˇcke (simbol) X = {0, 1, . . . , 15} doloˇcimo



verjetnost s ˇstetjem toˇck, ki imajo to vrednost.



N0 3

N0 = 3, PX (0) = =

N 36



8

N1 = 8, PX (1) =

36

NALOGE 61



itd. . .



N = [3 8 7 9 2 0 0 1 1 5]



1

P = N = [0,083 0,222 0,194 0,250 0,056 0 0 0,028 0,028 0,139]

36

Za vsak simbol izraˇcunamo informacijo



I = − log2 P = [3,58 2,17 2,36 2,00 4,17 ∞ ∞ 5,17 5,17 2,85]



in nato povpreˇcno informacijo vseh toˇck



H X ( X ) = P [i] · I [i] = 2,655

X X





i


To pomeni, da bi bilo dovolj, ˇce bi vsako toˇcko zakodirali v povpreˇcju z 2,66 bita.

xi PX(xi)

3 0,250 0,250 0,250 0,250 0,333 0,417 0,583 0

1 0,222 0,222 0,222 0,222 0,250 0,333 0 0,417 1

2 0,194 0,194 0,194 0,194 0,222 0 0,250 1

8 0,139 0,139 0,139 0,194 0 0,194 1

0 0,083 0,083 0,111 0 0,139 1

4 0,056 0,056 0 0,083 1

6 0,028 0 0,056 1

7 0,028 1



x i koda dolˇzina ni

0 111 3

1 10 2

2 000 3

3 01 2

4 1101 4

5 0 1

6 11000 5

7 11001 5

8 001 3

Povpreˇcna dolˇzina kode na slikovno toˇcko:



n X = n P [i] = 0,083 · 3 + 0,194 · 2 + . . . + 0,139 · 3 = 2,694

i X





i


Redundanca:



D = n − H = 2,694 − 2,66 = 0,040



D 0,040

R = = = 0,015

n 2,694

62 VLC KODIRANJE



Naloga 6.3: Doloˇcite kode simbolov danega informacijskega vira tako, da bo rela-

tivna kodirna redundanca manjˇsa od 5 %. ˇ Ce Huffmanova koda ne zadostuje, razˇsirite

informacijski vir s kombiniranjem simbolov v veˇcje bloke.



P X = [0,2 0,7 0,1]



Reˇsitev: Entropija vira:



H X ( X ) = − P [i] · log P [ ] = 1 157 i ,

X 2 X





i


Huffmanova koda:

Simbol PX(xi)



x 0,7 0,7 1 2

x 0,2 1 0,3 0 1

x 0,1 0 3



Simbol Koda

x 1 01

x 2 1

x 3 00

Povpreˇcna dolˇzina Huffmanove kode:



n = PX[i] · X n = 0,2 · 2 + 0,7 · 1 + 0,1 · 2 = 1,3





i


i




Relativna kodirna redundanca:

n − H (X) 1,3 − 1,157

R = = = 0,11

n 1,3

Huffmanova koda ne zadostuje, zato zdruˇzimo po dva simbola v nov simbol, da do-

bimo razˇsirjeni vir Y. Verjetnost posameznih simbolov razˇsirjenega vira je odvisna od

verjetnosti simbolov primarnega vira. Ker so zaporedni simboli med sabo neodvisni,

izraˇcunamo verjetnost novega simbola kot produkt verjetnosti simbolov primarnega



NALOGE 63



vira.



Simbol yi Kombinacija PY [i]

y1 x1 x1 0,04

y2 x1 x2 0,14

y3 x1 x3 0,02

y4 x2 x1 0,14

y5 x2 x2 0,49

y6 x2 x3 0,07

y7 x3 x1 0,02

y8 x3 x2 0,07

y9 x3 x3 0,01



Huffmanova koda razˇsirjenega vira:

yi PY(yi)

y5 0,49 0,49 0,49 0,49 0,49 0,49 0,49 0,51 1

y2 0,14 0,14 0,14 0,14 0,14 0,23 0,28 1 0,49 0

y4 0,14 0,14 0,14 0,14 0,14 0,14 1 0,23 0

y6 0,07 0,07 0,07 0,09 0,14 1 0,14 0

y8 0,07 0,07 0,07 0,07 1 0,09 0

y1 0,04 0,04 0,05 1 0,07 0

y3 0,02 0,03 1 0,04 0

y7 0,02 1 0,02 0

y9 0,01 0



Simbol Koda

y1 1000

y2 110

y3 10010

y4 101

y5 0

y6 1111

y7 100111

y8 1110

y9 100110

Entropija razˇsirjenega informacijskega vira:



H X ( Y ) = − P [i] · log P [i] = 2 3136 ,

Y 2 Y





i


Povpreˇcna dolˇzina kode razˇsirjenega informacijskega vira:



n ¯ = PY [i] · X n = 2,33





i


i




64 VLC KODIRANJE



Relativna kodirna redundanca razˇsirjenega vira:



n ¯ − H (Y ) 2,33 − 2,3136

R = = = 0,0071

n ¯ 2,33



Naloga 6.4: Podani niz zakodirajte z LZW algoritmom. Dobljeni niz nato ponovno

dekodirajte.

Niz: A A B B A B A A A B A A B A A B A B A B

Abeceda: A, B



Reˇsitev: V zaˇcetni kodni knjigi sta samo simbola podane abecede:

0 A

1 B

V kodni knjigi poiˇsˇcemo najdaljˇso kodo, ki se ujema z danim nizom na trenutnem

mestu in ustrezen del niza zakodiramo z zaporedno ˇstevilko kode:

A A B B A B A A A B A A B A A B A B A B

0

V kodno knjigo dodamo novo kodo tako, da trenutni kodi dodamo naslednji znak iz

niza:



0 A

A A B B A B A A A B A A B A A B A B A B 1 B

0

2 AA



0 A

A A B B A B A A A B A A B A A B A B A B

0 1 B

2 AA



Koraka ponavljamo, dokler ne pridemo do konca niza:



0 A

A A B B A B A A A B A A B A A B A B A B 1 B

0 0 2 AA

3 AB



0 A

1 B

A A B B A B A A A B A A B A A B A B A B

0 2 AA 0 1

3 AB

4 BB

NALOGE 65



0 A

1 B

A A B B A B A A A B A A B A A B A B A B 2 AA

0 0 1 1 3 AB

4 BB

5 BA



0 A

1 B

2 AA

A A B B AB A A A B A A B A A B A B A B

0 3 AB 0 1 1 3

4 BB

5 BA

6 ABA



0 A

1 B

2 AA

A A B B AB AA A B A A B A A B A B A B 3 AB

0 0 1 1 3 2 4 BB

5 BA

6 ABA

7 AAA



0 A

1 B

2 AA

3 AB

A A B B AB AA ABA A B A A B A B A B

0 4 BB 0 1 1 3 2 6

5 BA

6 ABA

7 AAA

8 ABAA



66 VLC KODIRANJE



0 A

1 B

2 AA

3 AB

A A B B AB AA ABA ABAA B A B A B 4 BB

0 0 1 1 3 2 6 8 5 BA

6 ABA

7 AAA

8 ABAA

9 ABAAB



0 A

1 B

2 AA

3 AB

4 BB

A A B B AB AA ABA ABAA BA B A B

5 BA

0 0 1 1 3 2 6 8 5

6 ABA

7 AAA

8 ABAA

9 ABAAB

10 BAB



0 A

1 B

2 AA

3 AB

4 BB

A A B B AB AA ABA ABAA BA BAB

5 BA

0 0 1 1 3 2 6 8 5 10

6 ABA

7 AAA

8 ABAA

9 ABAAB

10 BAB



Zakodiran niz: 0 0 1 1 3 2 6 8 5 10

Zaˇcetna kodnja kniga za dekodiranje:



NALOGE 67



0 A

1 B

S pomoˇcjo kodne knjige dekodiramo prvi znak:

0 0 1 1 3 2 6 8 5 10

A

S pomoˇcjo kodne knjige dekodiramo drugi znak in dodamo novo kodo v kodno kn-

jigo. Nova koda je sestavljena iz kode, ki je bila dekodirana v prejˇsnjem koraku in

prvega znaka kode, ki je bila odkodirana v tem koraku:



0 A

0 0 1 1 3 2 6 8 5 10

1 B

A A

2 AA



Korak 3 ponavljamo, dokler ne pridemo do konca zakodiranega niza:



0 A

0 0 1 1 3 2 6 8 5 10 1 B

A A B 2 AA

3 AB



0 A

1 B

0 0 1 1 3 2 6 8 5 10

2 AA

A A B B

3 AB

4 BB



0 A

1 B

0 0 1 1 3 2 6 8 5 10 2 AA

A A B B AB 3 AB

4 BB

5 BA



68 VLC KODIRANJE



0 A

1 B

2 AA

0 0 1 1 3 2 6 8 5 10

3 AB

A A B B AB AA

4 BB

5 BA

6 ABA



0 A

1 B

2 AA

0 0 1 1 3 2 6 8 5 10 3 AB

A A B B AB AA ABA 4 BB

5 BA

6 ABA

7 AAA



0 A

1 B

2 AA

3 AB

0 0 1 1 3 2 6 8 5 10

4 BB

A A B B AB AA ABA ???

5 BA

6 ABA

7 AAA

8 ???



Pri dekodiranju obˇcasno pride do problema, da za dekodiranje potrebujemo kodo, ki

je pravkar v nastajanju. Nova koda bo sestavljena iz prejˇsnje kode (ABA) in prvega

znaka same sebe (prvi zank od ???):



NALOGE 69



0 A

1 B

2 AA

3 AB

0 0 1 1 3 2 6 8 5 10

4 BB

A A B B AB AA ABA ABA?

5 BA

6 ABA

7 AAA

8 ABA?



Ker je zadnji znak kode enak prvemu znaku, lahko tudi to kodo ugotovimo:



0 A

1 B

2 AA

3 AB

0 0 1 1 3 2 6 8 5 10

4 BB

A A B B AB AA ABA ABAA

5 BA

6 ABA

7 AAA

8 ABAA



0 A

1 B

2 AA

3 AB

0 0 1 1 3 2 6 8 5 10 4 BB

A A B B AB AA ABA ABAA BA 5 BA

6 ABA

7 AAA

8 ABAA

9 ABAAB



70 VLC KODIRANJE



0 A

1 B

2 AA

3 AB

4 BB

0 0 1 1 3 2 6 8 5 10

5 BA

A A B B AB AA ABA ABAA BA BAB

6 ABA

7 AAA

8 ABAA

9 ABAAB

10 BAB



Dekodiran niz: A A B B A B A A A B A A B A A B A B A B



Naloga 6.5: Podani niz zakodirajte z LZW algoritmom. Dobljeni niz nato ponovno

dekodirajte.

Niz: ABADBCDBABCDACCABDBD

Abeceda: A, B, C, D



Reˇsitev:



NALOGE 71



A B A D B C DB AB CD A C C AB DB D

Kodirna knjiga:

0 1 0 3 1 2 7 4 9 0 2 2 4 7 3

0 A

1 B

2 C

3 D

4 AB

5 BA

6 AD

7 DB

8 BC

9 CD

10 DBA

11 ABC

12 CDA

13 AC

14 CC

15 CA

16 ABD

17 DBD



Zakodirani niz: 0 1 0 3 1 2 7 4 9 0 2 2 4 7 3

Dekodiranje:



72 VLC KODIRANJE



0 1 0 3 1 2 7 4 9 0 2 2 4 7 3

Kodna knjiga:

A B A D B C DB AB CD A C C AB DB D

0 A

1 B

2 C

3 D

4 AB

5 BA

6 AD

7 DB

8 BC

9 CD

10 DBA

11 ABC

12 CDA

13 AC

14 CC

15 CA

16 ABD

17 DBD



Naloga 6.6: S pomoˇcjo aritmetiˇcnega kodiranja zakodirajte niz X 2, X3, X3, X1, Xend.

Verjetnosti posameznih simbolov so 4 1 3 1 [ , , , ].

9 9 9 9



Reˇsitev: Pri aritmetiˇcnem kodiranju vzamemo trenutni interval, ter ga razdelimo

na podintervale glede na verjetnosti simbolov. Nato izberemo podinterval, ki ustreza

simbolu, ki ga kodiramo, in postopek ponavljamo, dokler ne zakodiramo celotnega

niza.

Korak 1, ˇclen: 2, zaˇcetni interval: [0.00000, 1.00000]

Simbol Podinterval

X1 [0.00000, 0.44444]

X2 [0.44444, 0.55556] <== izbran

X3 [0.55556, 0.88889]

X end [0.88889, 1.00000]

Korak 2, ˇclen: 3, zaˇcetni interval: [0.44444, 0.55556]



NALOGE 73



Simbol Podinterval

X1 [0.44444, 0.49383]

X2 [0.49383, 0.50617]

X3 [0.50617, 0.54321] <== izbran

X end [0.54321, 0.55556]

Korak 3, ˇclen: 3, zaˇcetni interval: [0.50617, 0.54321]

Simbol Podinterval

X1 [0.50617, 0.52263]

X2 [0.52263, 0.52675]

X3 [0.52675, 0.53909] <== izbran

X end [0.53909, 0.54321]

Korak 4, ˇclen: 1, zaˇcetni interval: [0.52675, 0.53909]

Simbol Podinterval

X1 [0.52675, 0.53224] <== izbran

X2 [0.53224, 0.53361]

X3 [0.53361, 0.53772]

X end [0.53772, 0.53909]

Korak 5, ˇclen: 4, zaˇcetni interval: [0.52675, 0.53224]

Simbol Podinterval

X1 [0.52675, 0.52919]

X2 [0.52919, 0.52980]

X3 [0.52980, 0.53163]

X end [0.53163, 0.53224] <== izbran

Kodirano ˇstevilo (sredina zadnjega intervala): 0.5319311081



Naloga 6.7: S pomoˇcjo aritmetiˇcnega kodiranja smo dobili 0.5319311081. Ob

znanih verjetnosti simbolov 4 1 3 1 [ , , , ] dekodirajte zaporedje.

9 9 9 9



Reˇsitev: V resnici je postopek aritmetiˇcnega dekodiranja praktiˇcno enak kodiranju.

Vsakiˇc trenutni interval razdelimo na podintervale glede na verjetnosti simbolov, nato

pa izberemo podinterval v katerega pade kodirana vrednost. Ta interval ustreza sim-

bolu, ki je bil zakodiran.

Korak 1, vrednost: 0.5319311081, interval: [0.00000, 1.00000]

Simbol Podinterval

X1 [0.00000, 0.44444]

X2 [0.44444, 0.55556]<== izbran

X3 [0.55556, 0.88889]

X end [0.88889, 1.00000]

Korak 2, vrednost: 0.5319311081, interval: [0.44444, 0.55556]

74 VLC KODIRANJE



Simbol Podinterval

X1 [0.44444, 0.49383]

X2 [0.49383, 0.50617]

X3 [0.50617, 0.54321] <== izbran

X end [0.54321, 0.55556]

Korak 3, vrednost: 0.5319311081, interval: [0.50617, 0.54321]



Simbol Podinterval

X1 [0.50617, 0.52263]

X2 [0.52263, 0.52675]

X3 [0.52675, 0.53909] <== izbran

X end [0.53909, 0.54321]

Korak 4, vrednost: 0.5319311081, interval: [0.52675, 0.53909]



Simbol Podinterval

X1 [0.52675, 0.53224] <== izbran

X2 [0.53224, 0.53361]

X3 [0.53361, 0.53772]

X end [0.53772, 0.53909]

Korak 5, vrednost: 0.5319311081, interval: [0.52675, 0.53224]



Simbol Podinterval

X1 [0.52675, 0.52919]

X2 [0.52919, 0.52980]

X3 [0.52980, 0.53163]

X end [0.53163, 0.53224] <== izbran

Prepoznan stop znak (Xend ) – dekodiranje zakljuˇceno.



Zakodirana sekvenca je bila X2, X3, X3, X1, Xend.



H P n vir x x i = − P log P Entropija informacijskega vira =1

2

HM AX = log (N ) N 2 Maksimalna entropija vira z simboli

n Pn ¯ = P · n Povpreˇcna dolˇzina kodnih besed

i=1 x x

R n ¯ −Hvir = Relativna kodirna redundanca ¯ n

η H vir = Uˇcinkovitost kodiranja

¯ n



Povzetek postopkov kodiranja



Huffmanovo kodiranje

1. Pridobi verjetnosti (ali relativne frekvence) vseh simbolov.

2. Uredi simbole po naraˇsˇcajoˇci verjetnosti.

3. Zdruˇzi dve najmanj verjetni vrednosti v nov simbol in po potrebi preuredi simbole.

NALOGE 75



4. Postopek ponavljaj, dokler ne ostaneta samo dva simbola.



5. Dodeli binarne kode tako, da vsak zgornji odcep pomeni 1, spodnji 0.



LZW kodiranje



1. Inicializiraj slovar s posameznimi simboli vhodnega abecednega nabora. Vsak simbol

dobi svojo kodo.



2. Preberi zaporedje simbolov in poiˇsˇci najdaljˇsi niz, ki je ˇze v slovarju.



3. Izdaj kodo za ta niz.



4. Dodaj nov vnos v slovar: trenutni niz + naslednji simbol.

5. Ponovi postopek, dokler ni celoten vhod obdelan.



Opomba: Pri dekodiranju je pomembno, da dekoder uporablja enak slovar kot kodirnik,

ki ga gradi sproti in na enak naˇcin.



LZW dekodiranje



1. Inicializiraj slovar s posameznimi simboli vhodnega abecednega nabora. Vsak simbol

dobi svojo kodo.



2. Preberi prvo kodo iz zaporedja in izpiˇsi ustrezni simbol iz slovarja.



3. Nastavi ta simbol kot zaˇcetni dekodirani niz.



4. Za vsako naslednjo kodo v zaporedju:

Ce je koda v slovarju, pridobi pripadajoˇci niz. ˇ

Ce kode ˇse ni v slovarju, sestavi nov niz tako, da prejˇsnjemu dekodiranemu nizu ˇ dodaˇs njegov prvi znak.

Izpiˇsi dobljeni niz.

Dodaj v slovar nov vnos: prejˇsnji dekodirani niz, dopolnjen s prvim znakom trenutnega niza.

Nastavi trenutni niz kot novi dekodirani niz za naslednji korak.



5. Postopek ponavljaj, dokler ne predelaˇs vseh kod iz zaporedja.



Aritmetiˇcno kodiranje



1. Doloˇci verjetnosti vseh simbolov v zaporedju.



2. Nastavi celotni interval na [0, 1].

3. Intervale razdeli na podintervale za posamezne simbole glede na njihovo verjetnost.



4. Za vsak simbol v zaporedju:



Izberi podinterval, ki ustreza simbolu.

Celotni interval zoˇzaj na ta podinterval.

76 VLC KODIRANJE



Ponovi od tretjega koraka dalje, dokler niso uporabljeni vsi simboli.



5. Konˇcni rezultat je poljubno ˇstevilo iz konˇcnega intervala (obiˇcajno sredina).



6. Za dekodiranje se ˇstevilo iterativno razˇsiri nazaj v posamezne simbole, glede na znane

verjetnosti in intervale.



7. POGLAVJE



VZAJEMNA INFORMACIJA



V tem poglavju bomo raziskali vzajemno informacijo kot kvantitativno mero odvisnosti med dvema nakljuˇcnima spremenljivkama. Ta pojem je kljuˇcen pri analizi informacijskih kanalov, saj nam omogoˇca ovrednotenje koliˇcine informacije, ki jo prejmemo o vhodni spremenljivki, ˇce poznamo izhodno.

Za dve diskretni nakljuˇcni spremenljivki X in Y je vzajemna informacija definirana

kot:



I(X; Y ) = P(x, y) log 2 P X P (x, y)

x,y (x)P(y)



Vzajemna informacija je simetriˇcena in vedno nenegativna. Vzajemna informacija meri,

koliko se negotovost o X zmanjˇsa, ko opazujemo Y , kar je formalno:



I(X; Y ) = H(X ) − H(X |Y ) = H (Y ) − H (Y |X)



Poleg teoretiˇcne osnove bomo v tem poglavju obravnavali:



primer dogodkov in njihove informacije,



binarni simetriˇcni kanal z napakami,



kanal s podano matriko pogojnih verjetnosti,



modeliranje analognega prenosa preko diskretizacije (Gaussov ˇsum in dekodiranje).



M. Kunaver, Teorija informacij in izvorno kodiranje. 77

©2025 Zaloˇzba FE

78 VZAJEMNA INFORMACIJA



Za dodatno branje priporoˇcamo naslednje vire:



T. M. Cover, J. A. Thomas: Elements of Information Theory [2]



D. J. C. MacKay: Information Theory, Inference, and Learning Algorithms [3]



N. Paveˇsiˇc: Informacija in kodi [6]



7.1 Naloge



Naloga 7.1: Meˇcemo poˇsteno igralno kocko. Dogodek A je, da pade ˇst. 3, dogodek B,

da pade liha ˇstevilka in dogodek C, da pade ˇstevilka veˇcja od 3. Doloˇcite informacijo

vsakega dogodka in vzajemno informacijo dogodkov A in B ter vzajemno informacijo

dogodkov B in C.



Reˇsitev:

S = {1, 2, 3, 4, 5, 6}

1

A = {3}, P (A) =

6

3

B = {1, 3, 5}, P (B) =

6

3

C = {4, 5, 6}, P (C) =

6



I(A) = − log P(A) = − log = 2,58 2 2 6 1



I(B) = − log P(B) = − log = 1 2 2 2 1

1

I(C) = − log 2 P(C) = − log2 = 1

2

I(A; B) = I(A) + I(B ) − I(A ∩ B)

A ∩ B = {3}

1

P (A ∩ B) =

6



I(A ∩ B) = − log P(A ∩ B) = − log = 2,58 2 2 6 1

I(A; B) = I(A) + I(B ) − I(A ∩ B) = 2,58 + 1 − 2,58 = 1

1

B ∩ C = {5}, P (B ∩ C) = , I(B ∩ C) = 2,58

6

I(B; C) = I(B) + I(C) − I(B ∩ C) = 1 + 1 − 2,58 = −0,58



NALOGE 79



V tej nalogi smo uporabili izraz:



I(A; B) = I(A) + I(B) − I(A ∩ B)



pri ˇcemer je 1 I ( A ) = log t. i. ”informacija dogodka”. Vendar opozorimo, da

2 P(A)

to ni formalna definicija vzajemne informacije, kot jo sicer uporabljamo v teoriji

informacij za nakljuˇcne spremenljivke. Vzajemna informacija med dogodkoma bi

bila ustrezno definirana ˇsele, ˇce bi definirali spremenljivki, ki zavzemata vrednosti 1

(ˇce se dogodek zgodi) ali 0 (ˇce se ne zgodi), nato pa izraˇcunali entropiji in skupno

entropijo teh spremenljivk:



I(A; B) = H (A) + H (B) − H(A, B)



V tem primeru pa smo raje uporabili izraz, ki se intuitivno bere kot ”kolikˇsen preseˇzek

informacije bi potrebovali, ˇce bi kodirali dogodka posebej, v primerjavi s skupnim

kodiranjem”. Zaradi tega lahko pride tudi do negativnih vrednosti izraza I(A; B), kar

za pravo vzajemno informacijo nikoli ne velja. Ta pristop je torej zgolj intuitivna ilus-

tracija preseˇzne informacije in ni enakovreden formalni vzajemni informaciji med

nakljuˇcnima spremenljivkama. Vzajemna informacija dveh dogodkov (izidov) je

lahko pozitivna ali negativna, medtem ko je povpreˇcna vzajemna informacija dveh

nakljuˇcnih spremenljivk vedno pozitivna ali enaka niˇc.



Naloga 7.2: Verjetnost za napako na simetriˇcnem binarnem kanalu je 0,1. Verjetnost

za simbol x1 vhodne nakljuˇcne spremenljivke znaˇsa PX (x11) = 0,3. Doloˇcite:

informacijo obeh simbolov vhodne in izhodne spremenljivke,



entropijo vhodne nakljuˇcne spremenljivke X in izhodne spremenljivke Y ,



vzajemno informacijo vseh kombinacij simbolov vhodne in izhodne nakljuˇcne spremenljivke,



povpreˇcno preneseno informacijo,



pogojni entropiji H(Y |X ) in H(X |Y ) ter



vezano entropijo H (X, Y ).



0.9

X1 Y1

0.1



0.1

X2 Y2

0.9



Binarni kanal



80 VZAJEMNA INFORMACIJA



Reˇsitev: Informacija simbolov:



I(x 1) = − log 0,3 = 1,74 2



I(x 2) = − log2 0,7 = 0,51



P (y 1) = P (x1) · 0,9 + P (x2) · 0,1 = 0,3 · 0,9 + 0,7 · 0,1 = 0,34

P (y 2) = P (x1) · 0,1 + P (x2) · 0,9 = 0,3 · 0,1 + 0,7 · 0,9 = 0,66

I(y 1) = − log 0,34 = 1,56 2

I(y 2) = − log 2 0,66 = 0,60

H (X ) = P(x1) · I(x1) + P (x2) · I(x2) = 0,3 · 1,74 + 0,7 · 0,51 = 0,88

H(Y ) = P(y 1) · I(y1) + P (y2) · I(y2) = 0,34 · 1,56 + 0,66 · 0,60 = 0,93



I(x1; y1) = I(x1) + I(y1) − I(x1 ∩ y1)

P (x1 ∩ y1) = P (y1 | x1) · P (x1) = 0,9 · 0,3 = 0,27

I(x1 ∩ y1) = − log2 0,27 = 1,89

I(x1; y1) = 1,74 + 1,56 − 1,89 = 1,41



P (x1 ∩ y2) = P (y2 | x1) · P (x1) = 0,1 · 0,3 = 0,03, I(x1 ∩ y2) = 5,06

P (x2 ∩ y1) = P (y1 | x2) · P (x2) = 0,1 · 0,7 = 0,07, I(x2 ∩ y1) = 3,84

P (x2 ∩ y2) = P (y2 | x2) · P (x2) = 0,9 · 0,7 = 0,63, I(x2 ∩ y2) = 0,67

I(x1; y2) = 1,74 + 0,60 − 5,06 = −2,72

I(x2; y1) = 0,51 + 1,56 − 3,84 = −1,77

I(x2; y2) = 0,51 + 0,60 − 0,67 = 0,44



I X X ( X ; Y ) = P (x , y ) · I(x ; y )

XY j k j k

j k

I(X; Y ) = P (x 1 ∩ y1) · I(x1; y1) + P (x1 ∩ y2) · I(x1; y2)

+ P(x2 ∩ y1) · I(x2; y1) + P (x2 ∩ y2) · I(x2; y2)

I(X; Y ) = 0,27 · 1,41 − 0,03 · 2,72 − 0,07 · 1,77 + 0,63 · 0,44 = 0,45



H(Y | X X ) = P (x ) · H (Y | x )

X j j

j

H X ( Y | x ) = P (y | x ) · I(y | x )

1 k 1 k 1

k

= −P (y1 | x1) · log P(y P ( 2 1 | x 1 ) −y2 | x1) · log P (y x ) 2 2 | 1

H (Y | x 1) = −0,9 · log 0,9 − 0,1 · log 0,1 = 0,47 2 2

H X ( Y | x ) = P (y | x ) · I(y | x )

2 k 2 k 2

k

= −P (y1 | x2) · log P(y1 | x2) − P (y2 | x2) · log P (y | 2 2 x2) 2



NALOGE 81



H (Y | x2) = −0,1 · log 0,1 − 0,9 · log 0,9 = 0,47 2 2

H X ( Y | X ) = P (x ) · H (Y | x )

X j j

j

= PX(x1) · H(Y | x1) + PX(x2) · H(Y | x2)

H (Y | X) = 0,3 · 0,47 + 0,7 · 0,47 = 0,47

H X ( X | Y ) = P (y ) · H (X | y )

Y j j

j

H X ( X | y ) = P (x | y ) · I(x | y )

1 k 1 k 1

k

= −P(x1 | y1) · log P (x | y ) − P (x · log P(x 2 1 1 2 | y 1 ) 22 | y1)

P (x1 ∩ y1) = P (y1 | x1) · P (x1) = P (x1 | y1) · P (y1)

P (x1 ∩ y1) 0,27

P (x 1 | y1) = = = 0,79

P(y 1) 0,34

0,03

P (x 1 | y2) = = 0,045

0,66

0,07

P (x 2 | y1) = = 0,21

0,34

0,63

P (x 2 | y2) = = 0,95

0,66

H(X | y 1) = −0,79 · log 0,79 21 2 − 0 , · log 0,21 = 0,74 2

H X ( X | y ) = P (x | y ) · I(x | y )

2 k 2 k 2

k

= −P(x1 | y2) · log P (x y ) 2 1 | 2 − P (x2 | y2) · log P(x y 2 2 |2)

H(X | y 2) = −0,045 · log 0,045 − 0,95 · log 0,095 = 0,27 2 2

H (X | X Y ) = P (y ) · H (X | y ) = P (y ) · H (X | y ) + P (y ) · H (X | y )

Y j j Y 1 1 Y 2 2

j

H (X | Y ) = 0,34 · 0,74 + 0,66 · 0,27 = 0,43



H (X, Y ) = P XY (xj, yk) · X X I (x , y )

XY j k

j k

H (X, Y ) = H(X ) + H(Y ) − I(X; Y ) = 0,88 + 0,93 − 0,45 = 1,36

Opomba: Pri izraˇcunu entropij in vzajemne informacije smo uporabili znane izraze

za diskretne nakljuˇcne spremenljivke:



I(X; Y ) = H (X) + H(Y ) − H (X, Y )



Ker imamo podano matriko pogojnih verjetnosti P(Y |X ) in porazdelitev P (X ),

lahko vse ostale verjetnosti (npr. P (X, Y ), P (Y )) izrazimo preko produktov in vsot.

To ustreza modelu sporoˇcilnega kanala, kot ga definira teorija informacij. Kljub temu,

da je kanal simetriˇcen, rezultat ni popolnoma enak za vse vrednosti, saj vhodna po-

razdelitev P (X) ni enakomerna. Ta naloga lepo ponazori, kako se napake v kanalu

odraˇzajo kot zmanjˇsanje vzajemne informacije.

82 VZAJEMNA INFORMACIJA



Naloga 7.3: Za brez spominski informacijski kanal je podana matrika pogojnih

verjetnosti:

 

0,8 0,1 0,05 0,05

  0 , 03 0 , 85 0 , 02 0 , 1

P   =

K  

  0 , 03 0 , 05 0 , 9 0 , 02

 

0,06 0,06 0,08 0,8



Za vhodno nakljuˇcno spremenljivko predpostavite enakomerno porazdelitev.

Doloˇcite:



entropijo vhodne nakljuˇcne spremenljivke X in izhodne spremenljivke Y,

vezano entropijo H (X, Y ),



povpreˇcno preneseno informacijo I(Y ; X ) ter



pogojni entropiji H(Y |X ) in H(X |Y ).



Reˇsitev: Vhodna nakljuˇcna spremenljivka X ima ˇstiri simbole z enako verjetnostjo

0, 25:

P X = [0,25 0,25 0,25 0,25]

Verjetnost hkratnega nastopa doloˇcene kombinacije simbolov spremenljivk X in Y

lahko doloˇcimo iz pogojne verjetnosti PY |X in verjetnosti PX :



P XY (xi, yj) = P Y |X(xi, yj) · PX(xi)

 

0,2 0,025 0,0125 0,0125

  0 , 0075 0 , 2125 0 , 005 0 , 025

P   =

XY   0 , 0075 0 , 0125 0 , 225 0 , 005

 

 

0,015 0,015 0,02 0,2

Marginalno verjetnost PY doloˇcimo s seˇstevanjem posameznih stolpcev vezane ver-

jetnosti P XY :

P Y = [0,23 0,265 0,2625 0,2425]

Iz marginalnih verjetnosti P X in PY doloˇcimo entropiji nakljuˇcnih spremenljivk X

in Y :

H (X ) = 2

H(Y ) = 1.9976



Vezano entropijo izraˇcunamo iz vezane verjetnosti P XY :



H (X, Y ) = P XY (xi, yj) · X X I (x , y )

XY i j

i j

= − X X P (x , y ) · log (P (x , y )) = 2,8679

XY i j 2 XY i j

i j

NALOGE 83



Povpreˇcno preneseno informacijo lahko izraˇcunamo iz entropij posameznih nakljuˇcnih

spremenljivk in vezane entropije.



I(X; Y ) = H (X) + H(Y ) − H (X, Y ) = 2 + 1,9976 − 2,8679 = 1,1296



Pogojno entropijo lahko izrazimo iz povpreˇcne prenesene informacije in entropije

posamezne nakljuˇcne spremenljivke.



I(X; Y ) = H (X ) − H (X |Y ) = I(Y ; X ) = H (Y ) − H(Y |X )

H (X |Y ) = H (X ) − I(X ; Y ) = 2 − 1,1296 = 0,8704

H (Y |X) = H (Y ) − I(X; Y ) = 1,9976 − 1,1296 = 0,8679



Naloga 7.4: Tri-nivojski signal z nivoji −1V , 0V in 1V ima dodan beli Gaussov ˇsum

z efektivno vrednostjo 0,4V in povpreˇcno vrednostjo −0,1V . Linijski dekodirnik in-

terpretira napetosti pod −0,5V kot simbol y1, napetosti med −0,5V in 0,5V kot y2 in

napetosti nad 0,5V kot y3. Doloˇcite matriko pogojnih verjetnosti PK informacijskega

kanala.



Reˇsitev: Matrika pogojnih verjetnosti informacijskega kanala doloˇca verjetnosti

sprejetih simbolov pri doloˇcenih oddanih simbolih:



  P ( y | x ) · · · P ( y | x )

1 1 n 1

P   K  . = .. . . ..

. . 

 

P (y1 | xn) · · · P (yn | xn)



Pogojne verjetnosti za dani primer so ilustrirane na spodnji sliki:



Verjetnosti posameznih izhodnih simbolov pri danem vhodnem simbolu doloˇcimo s

pomoˇcjo tabele normirane normalne porazdelitve. V ta namen normiramo razdaljo od

sredine Gaussove krivulje do meje med simboli. Kjer tabela ne zadostuje, uporabimo



84 VZAJEMNA INFORMACIJA



pribliˇzek Q(x).



0 , 6

P (y 1 | x1) = Φ = Φ(1,5) = 0,93319

0,4

1 , 6 0 , 6

P (y 2 | x1) = Φ − Φ = Φ(4) − Φ(1,5) = 1 − Q(4) − Φ(1,5)

0,4 0,4



Q 1 2 − x/2 −5 ( x ) = √ e , Q (4) = 3 , 35 · 10

x 2π

P −5 ( y | x ) = 1 − 3 , 35 · 10 − 0,93319 = 0,06678

2 1

1 , 6

P −5 ( y | x ) = F ( ∞ ) − F = 1 − F (4) = 1 − 1 + Q (4) = 3 , 35 · 10

3 1 0,4



0 , 4

P (y 1 | x2) = 1 − Φ = 1 − Φ(1) = 1 − 0,84134 = 0,15866

0,4

0 , 6 0 , 4

P (y 2 | x2) = Φ − 1 − Φ = Φ(1,5) − 1 + Φ(1)

0,4 0,4

= 0,93319 − 1 + 0,84134 = 0,77453

0 , 6

P (y 3 | x2) = 1 − Φ = 1 − Φ(1,5) = 1 − 0,93319 = 0,06681

0,4

1 , 4

P (y 1 | x3) = 1 − Φ = 1 − Φ(3,5) = 1 − 0,99977 = 0,00023

0,4

1 , 4 0 , 4

P (y 2 | x3) = Φ − Φ = Φ(3,5) − Φ(1)

0,4 0,4

= 0,99977 − 0,84134 = 0,15843



0 , 4

P (y 3 | x3) = Φ = Φ(1) = 0,84134

0,4



  0 , 93319 0 , 06678 0 , 00003

PK =  0,15866 0,77453 0,06681  

0,00023 0,15843 0,84134



Opomba: V tej nalogi smo preˇsli iz zveznega v diskreten model s tem, da smo

analogne vrednosti ˇsuma diskretizirali v tri izhodne razrede. To pomeni, da obrav-

navamo sistem kot kanal z diskretnimi izhodi in zveznimi napakami (Gaussov ˇsum).

Za doloˇcitev verjetnosti P (Y |X) smo uporabili porazdelitveno funkcijo normalne po-

razdelitve:



Z b 1

P (y σ2 j | − (t−µ)2 xi) = √

e 2 dt

a 2πσ



NALOGE 85



pri ˇcemer so meje a, b odvisne od dekodirnih pragov in trenutne vrednosti xi. Ta

pristop je obiˇcajen pri modeliranju kanalov, kjer je vhod simbolen, ˇsum pa analogni —

in temelji na numeriˇcni aproksimaciji z uporabo Z-tabele ali numeriˇcne integracije.



I 1 ( x ) = log Informacija posameznega dogodka

2 P(x)

I(A; B) = I(A) + I(B) − I(A ∩ B) Vzajemna informacija dveh dogodkov

I(X; Y ) = H (X) + H(Y ) − H (X, Y ) Vzajemna informacija dveh spremenljivk

H (Y |X) = H (Y ) − I(X ; Y ) Pogojna entropija

P A−µ ( x ≤ A ) = Φ( ) Verjetnost, da je nakljuˇcna spremenljivka

σ

manjˇsa od A v normalni porazdelitvi z efek-

tivno vrednostjo σ in povpreˇcjem µ

P (x ≥ A) = 1 − P(x ≤ A) Verjetnost, da je nakljuˇcna spremenljivka

veˇcja od A v normalni porazdelitvi

P (x ≤ −A) = P(x ≥ A) Verjetnost, da je nakljuˇcna spremenljivka

manjˇsa od −A v normalni porazdelitvi



8. POGLAVJE



KAPACITETA KANALA



V tem poglavju bomo raziskali, kako koliˇcinsko opiˇsemo zmoˇznost komunikacijskega kanala za prenos informacij. Glavni cilj je doloˇciti kapaciteto kanala — najveˇcjo koliˇcino informacij, ki jo lahko kanal prenese brez napak.

Obravnavali bomo razliˇcne tipe kanalov:

sploˇsne diskretne kanale z matriko prehodnih verjetnosti,

binarni simetriˇcni kanal (BSC),

vpliv napake na prenosno zmogljivost.

Posebno pozornost bomo namenili pojmom:

entropija izhodne spremenljivke H(Y ),

pogojna entropija H(Y |X ),

vzajemna informacija I(X ; Y ),

kapaciteta C = max I(X; Y ).

Razumevanje teh konceptov je temeljno za zasnovo uˇcinkovitih kodirnikov in ocenje-

vanje izgub v prenosnih sistemih. Za dodatno branje priporoˇcamo naslednje vire:

C. E. Shannon: A Mathematical Theory of Communication [4]

T. M. Cover, J. A. Thomas: Elements of Information Theory [2]

S. Tomaˇziˇc: Osnove telekomunikacij I [5]

M. Kunaver, Teorija informacij in izvorno kodiranje. 87

©2025 Zaloˇzba FE

88 KAPACITETA KANALA



8.1 Naloge



Naloga 8.1: Doloˇcite kapaciteto simetriˇcnega binarnega kanala z verjetnostjo napake

0,2.



Reˇsitev: Skica simetriˇcnega binarnega kanala:



0,8

X1 Y1

0,2



0,2

X2 Y2

0,8



Kapaciteta kanala je maksimalna moˇzna vzajemna informacija vhodne in izhodne

spremenljivke. Vzajemna informacija je odvisna od kanala in verjetnostne porazdelitve

vhodne nakljuˇcne spremenljivke. Vzajemno informacijo izrazimo kot funkcijo verjet-

nostne porazdelitve in poiˇsˇcemo njen maksimum.



I(X; Y ) = H (X) + H(Y ) − X X H ( X, Y ) = P (x , y ) · I(x ; y )

XY i j i j

i j



Povpreˇcno preneseno informacijo lahko izraˇcunamo kot razliko vsote entropij vhodne

in izhodne spremenljivke ter vezano entropijo ali kot povpreˇcno vzajemno informacijo

posameznih parov vhodnih in izhodnih simbolov. Za iskanje ekstrema je ugodneje, ˇce

je izraz za povpreˇcno preneseno informacijo zapisan ˇcim krajˇse, zato ga raje zapiˇsemo

kot povpreˇcno vzajemno informacijo.



P ( y | x )

I X X j i ( X ; Y ) = P XY i j 2 (

x , y ) · log

i P (yj) j

PX(x1) = a

PX(x2) = 1 − a

PY (y1) = PX(x1) · 0,8 + PX (x2) · 0,2 = 0,8a + 0,2(1 − a) = 0,2 + 0,6a

PY (y2) = PX(x2) · 0,8 + PX (x1) · 0,2 = 0,8(1 − a) + 0,2a = 0,8 − 0,6a

P (y 1 | x1) = 0,8

P (y 1 | x2) = 0,2

P (y 2 | x1) = 0,2

P (y 2 | x2) = 0,8



NALOGE 89



" # P (x 1 ∩ y 1 ) P (x 2 ∩ y1

)

PXY =

P (x 1 ∩ y2) P (x2 ∩ y2)

" # P (y1 | x ) · P ( x ) P ( y | x ) · P ( x )

= 1 1 1 2 2

P (y2 | x1) · P (x1) P (y2 | x2) · P (x2)

" # 0,8 · a 0 , 2 · (1 − a )

PXY =

0,2 · a 0,8 · (1 − a)

0 , 8 0 , 2

I(X; Y ) = 0,8a · log 2 + 0,2a · log2

0,2 + 0,6a 0,8 − 0,6a

0 , 2 0 , 8

+ 0,2(1 − a) · log + 0,8(1 log 2 − a ) ·2

0,2 + 0,6a 0,8 − 0,6a

Povpreˇcno preneseno informacijo imamo zapisano kot funkcijo porazdelitve verjet-

nosti vhodne nakljuˇcne spremenljivke. Njen maksimum poiˇsˇcemo z odvajanjem. Ker

je laˇzje odvajati naravni logaritem, funkcijo nekoliko predelamo, da na desni strani

dobimo le naravne logaritme.



ln ln 0 0 , 8 0 , 2

,2+0,6a 0,8 −0,6a

I(X ; Y ) = 0,8a · + 0,2a ·

ln 2 ln 2

ln ln 0 0 , 2 0 , 8

,2+0,6a 0,8 −0,6a

+0,2(1 − a) · + 0,8(1 − a) ·

ln 2 ln 2

0 , 8 0 , 2

ln 2 · I(X; Y ) = 0,8a · ln + 0,2a · ln

0,2 + 0,6a 0,8 − 0,6a

0 , 2 0 , 8

+0,2(1 − a) · ln + 0,8(1 − a) · ln

0,2 + 0,6a 0,8 − 0,6a



d (f (x) · g(x)) df (x) dg(x)

= · g(x) + f (x) ·

dx dx dx

d a d

ln −1 = ln a · ( b + cx )

dx b + cx dx



= 1 c − 2 · ( − 1) a ( b + cx ) · c = − − a · 1 ( b + cx ) b + cx

dI(X ; Y ) 0,8 −0,6

ln 2 · = 0,8 · ln + 0,8a ·

da 0,2 + 0,6a 0,2 + 0,6a

0,2 +0,6

+0,2 · ln + 0,2a ·

0,8 − 0,6a 0,8 − 0,6a

−0,6 0,2 −0,6

+0,2 · − 0,2 · ln − 0,2a ·

0,2 + 0,6a 0,2 + 0,6a 0,2 + 0,6a

+0,6 0,8 +0,6

+0,8 · − 0,8 · ln − 0,8a ·

0,8 − 0,6a 0,8 − 0,6a 0,8 − 0,6a



90 KAPACITETA KANALA



0 , 8 0 , 8 − 0 , 6 a 0 , 2 0 , 2 + 0 , 6 a

0 = 0,8 · ln · + 0,2 · ln ·

0,2 + 0,6a 0,8 0,8 − 0,6a 0,2

+0,6 +0,6 +0,6

+0,8 · − 0,8a · + 0,2a ·

0,8 − 0,6a 0,8 − 0,6a 0,8 − 0,6a

−0,6 −0,6 −0,6

+0,2 · − 0,2a · + 0,8a ·

0,2 + 0,6a 0,2 + 0,6a 0,2 + 0,6a

0 , 8 − 0 , 6 a 0 , 2 + 0 , 6 a

0 = 0,8 · ln + 0,2 · ln

0,2 + 0,6a 0,8 − 0,6a

0,6

+ · (0,8 − 0,8a + 0,2a)

0,8 − 0,6a

−0,6

+ · (0,2 − 0,2a + 0,8a)

0,2 + 0,6a



0 ! ! , 8 0 , 2 0 , 8 − 0 , 6 a 0 , 2 + 0 , 6 a

0 = ln + ln

0,2 + 0,6a 0,8 − 0,6a

0,6 −0,6

+ · (0,8 − 0,6a) + · (0,2 + 0,6a)

0,8 − 0,6a 0,2 + 0,6a

0,8 0,2 (0 , 8 − 0 , 6 a ) · (0 , 2 + 0 , 6 a )

0 = ln 0,8 0,2 (0 , 2 + 0 , 6 a ) · (0 , 8 − 0 , 6 a )

0 ! , 6 0 , 8 − 0 , 6 a

0 = ln

0,2 + 0,6a

0 , 8 − 0 , 6 a

0 = 0,6 ln

0,2 + 0,6a

0, 8 − 0, 6a

1 =

0, 2 + 0, 6a

0, 2 + 0, 6a = 0, 8 − 0, 6a

1, 2a = 0, 6

a = 0, 5

Vzajemna informacija je najveˇcja, kadar je verjetnost za oba vhodna simbola enaka.



C = I(X ; Y ) a=0,5



C = 0, 4 · log + 0, 1 · log + 0, 1 · log + 0, 4 · log 2 2 22 0 0, 8 0, 2 0, 2 0, 8

, 5 0, 5 0, 5 0, 5

= 0, 8 · log2 1, 6 + 0, 2 · log2 0, 4

C = 0, 28 bit/sim



NALOGE 91



Naloga 8.2: Doloˇcite kapaciteto danega binarnega kanala.



0,8

X1 Y1

0,1



0,2

X2 Y2

0,9



Binarni kanal



Reˇsitev:

P ( y | x )

I X X j i ( X ; Y ) = P XY i j 2 (

x , y ) · log

i P(yj ) j

P X (x1) = a

P X (x2) = 1 − a

PY (y1) = PX (x1) · 0,8 + PX (x2) · 0,1 = 0,8a + 0,1(1 − a) = 0,1 + 0,7a

PY (y2) = PX (x2) · 0,9 + PX (x1) · 0,2 = 0,9(1 − a) + 0,2a = 0,9 − 0,7a

P (y 1|x1) = 0,8

P (y 1|x2) = 0,1

P (y 2|x1) = 0,2

P (y 2|x2) = 0,9

" # " #

P (x 1 ∩ y1) P (x2 ∩ y1) P(y1|x1) · P (x1) P(y1|x2) · P (x2)

PXY = =

P (x 1 ∩ y2) P (x2 ∩ y2) P(y2|x1) · P (x1) P(y2|x2) · P (x2)

" # 0,8 · a 0 , 1 · (1 − a )

PXY =

0,2 · a 0,9 · (1 − a)



I(X; Y ) = 0,8a · log + 0,2a · log 22 0 0,8 0,2

,1 + 0,7a 0,9 − 0,7a



+ 0,1(1 − a) · log + 0,9(1 − a) · log 22 0 0,1 0,9

,1 + 0,7a 0,9 − 0,7a

0,8 0,2

ln 2 · I(X; Y ) = 0,8a · ln + 0,2a · ln

0,1 + 0,7a 0,9 − 0,7a

0,1 0,9

+ 0,1(1 − a) · ln + 0,9(1 − a) · ln

0,1 + 0,7a 0,9 − 0,7a

d (f (x) · g(x)) df(x) dg(x)

= · g(x) + f (x) ·

dx dx dx

d a −c

ln =

dx b + cx b + cx

92 KAPACITETA KANALA



d 0,8 −0,7

ln 2 · I(X ; Y ) =0,8 · ln + 0,8a ·

da 0,1 + 0,7a 0,1 + 0,7a

0,2 0,7

+ 0,2 · ln + 0,2a ·

0,9 − 0,7a 0,9 − 0,7a

−0,7 0,1 −0,7

+ 0,1 · − 0,1 · ln − 0,1a ·

0,1 + 0,7a 0,1 + 0,7a 0,1 + 0,7a

0,7 0,9 0,7

+ 0,9 · − 0,9 · ln − 0,9a ·

0,9 − 0,7a 0,9 − 0,7a 0,9 − 0,7a

d 0,8 0,2

ln 2 · I(X ; Y ) =0,8 · ln + 0,2 · ln

da 0,1 + 0,7a 0,9 − 0,7a

0,1 0,9

− 0,1 · ln − 0,9 · ln

0,1 + 0,7a 0,9 − 0,7a

0,7 0,7 0,7

+ 0,2a · − 0,9a · − 0,8a ·

0,9 − 0,7a 0,9 − 0,7a 0,1 + 0,7a

0,7 0,7 0,7

+ 0,1a · − 0,1 · + 0,9 ·

0,1 + 0,7a 0,1 + 0,7a 0,9 − 0,7a



ln 2 · I(X ; Y ) = ln + ln − ln 0 , 8 0 , 2 0,1 da d 0,8 0,2 0,1 0 , 8 0 , 2 0 , 1

(0,1 + 0,7a) (0,9 − 0,7a) (0,1 + 0,7a)

0 0,9 , 9 0,7 0,7

− ln − 0,7a · + 0,9 · 0 , 9 (0 , 9 − 0 , 7 a ) 0 , 9 − 0 , 7 a 0,9 − 0,7a

0,7 0,7

− 0,7a · − 0,1 ·

0,1 + 0,7a 0,1 + 0,7a

d 0,8 0,2 0 , 8 0 , 2

ln 2 · I(X ; Y ) = ln · 0 , 8 (0,9 − 0,2 da (0 , 1 + 0 , 7 a ) 0 , 7 a )



· · 0 , 1 0,9 0 (0 0,1 0,9 , 1 + 0 , 7 a ) (0 , 9 − 0 , 7 a )

,1 0,9

0,7 0,7

+ (0,9 − 0,7a) · − (0,1 + 0,7a) ·

0,9 − 0,7a 0,1 + 0,7a



ln 2 · I(X ; Y ) = ln + 0,7 − 0,7 0 , 7 0 , 1 0 , 9 da d 0,7 0,2 0,8 (0 , 9 − 0 , 7 a ) · 0 , 2 · 0 , 8 (0,1 + 0,7a) · 0,1 · 0,9



NALOGE 93



0,7 0,2 0,8 (0 , 9 − 0 , 7 a ) · 0 , 2 · 0 , 8

0 = ln 0,7 0,1 0,9 (0 , 1 + 0 , 7 a ) · 0 , 1 · 0 , 9

0 0 ! 0 , 9 − , 7,2 0,8 0 , 7 a 0 , 2 · 0 , 8

= ln + ln 0,1 0,9 0 , 1 + 0 , 7 a 0 , 1 · 0 , 9



0,1 0,9 0 ! , 7 0 , 1 · 0 , 9 0 , 9 − 0 , 7 a

ln = ln 0 , 2 0 , 8 0 , 2 · 0 , 8 0,1 + 0,7a



0 0 7 , 1 0 , 9 , 1 · 0 , 9 0 , 9 − 0 , 7 a

10

0 0 = , 2 0 , 8 , 2 · 0 , 8 0,1 + 0,7a

10

0,1 0,9 7 0 , 1 · 0 , 9 0,9 − 0,7a

0 0 = = K = 1,285 , 2 0 , 8 , 2 · 0 , 8 0 , 1 + 0 , 7 a

0,1K + 0,7Ka = 0,9 − 0,7a

0,9 − 0,1K

a = = 0,482

0,7 + 0,7K

Kapaciteta kanala bo najveˇcja, kadar bo verjetnost za simbol x 1 0,482 in verjetnost

za simbol x2 0,518.



C = I ( X ; Y )

a=0,482



C = 0,8 · 0,482 · log + 0,2 · 0,482 · log 22 0 0,8 0,2

,1 + 0,7 · 0,482 0,9 − 0,7 · 0,482



+ 0,1(1 − 0,482) · log + 0,9(1 − 0,482) · log 22 0 0,1 0,9

,1 + 0,7 · 0,482 0,9 − 0,7 · 0,482

C = 0,398



Naloga 8.3: Izraˇcunajte diferencialno entropijo zveznega informacijskega vira z

enakomerno verjetnostno porazdelitvijo signala med -1 in 1.



Reˇsitev: Po analogiji z entropijo diskretnega informacijskega vira



H (X ) = − X P (x ) log P (x )

X i 2 X i





i




zapiˇsemo diferencialno entropijo zveznega informacijskega vira z

Z ∞

h(X ) = − p X(x) log p x) dx. 2 X (

−∞

Verjetnostna porazdelitev na danem intervalu je dana z

(

0,5 ; −1 < x < 1

p X (x) =

0 ; sicer

94 KAPACITETA KANALA



Verjetnostno porazdelitev vstavimo v izraz za izraˇcun diferencialne entropije in do-

bimo

Z 1 Z 1 1

h(X ) = − 0,5 log 0,5 dx = 0,5 dx = −0,5 · x = 0,5 · 2 = 1. 2 − 1 − 1 − 1



Naloga 8.4: Izraˇcunajte diferencialno entropijo zveznega informacijskega vira z dano

verjetnostno porazdelitvijo signala



p x(x) = (1 − |x|)u(1 + x)u(1 − x)



Reˇsitev: Verjetnostno porazdelitev zapiˇsemo po posameznih intervalih



1 + x ; −1 < x < 0





p X (x) = 1 − x ; 0 ≤ x < 1

0 ; sicer





in vstavimo v izraz za izraˇcun diferencialne entropije

Z ∞

h(X ) = − p X(x) log p (x) dx 2 X

−∞

Z 0 Z 1

= − (1 + x) log (1 + x) dx − (1 − x) log (1 − x) dx 2 2

−1 0

1 0 1 Z Z

h(X ) = − (1 + x) ln(1 + x) dx − (1 − x) ln(1 − x) dx

ln 2 −1 0

Z 0

(1 + x) ln(1 + x) dx =

−1

1 + x = u x = −1 : u = 0

dx = du x = 0 : u = 1

Z 1 1 ln u 1

= 2 u ln u du = u −

0 0 2

4

ln 1 1 ln 0 1 1

= 2 − − 0 − = −

2 4 2 4 4



NALOGE 95



Z 1

(1 − x) ln(1 − x) dx =

0

1 − x = u x = 0 : u = 1

− dx = du x = 1 : u = 0

Z 0 0 ln u 1

= 2 − u ln u du = u −

1 1 2

4

ln 0 1 ln 1 1 1

= 02 − − − =

2 4 2 4 4

1 1 1 1

h(X ) = − + =

ln 2 4 4 2 ln 2



Naloga 8.5: Podana je vezana gostota verjetnosti vhodne spremenljivke X in izhodne

spremenljivke Y. Izraˇcunajte entropiji vhodne in izhodne spremenljivke ter povpreˇcno

preneseno informacijo.



96 KAPACITETA KANALA



Reˇsitev: Velikost konstante k doloˇcimo iz volumna pod povrˇsino, ki predstavlja

gostoto verjetnosti:

Z Z

pXY (x, y) dx dy = 4k = 1 ⇒ k = 0,25



Za izraˇcun diferencialnih entropij potrebujemo marginalni porazdelitvi verjetnosti:

Z ∞

p X (x) = pXY (x, y) dy

−∞



− 1 < x < 0 :

Z 0 Z 1+x 0 1+x

p X (x) = k dy + 2k dy = k y + 2k y − 1 − x0 − 1 − x 0

= k(1 + x) + 2k(1 + x) = 3k(1 + x)



0 ≤ x < 1 :

Z 0 Z 1−x 0 1−x

p X ( x ) = 2 k dy + 3 k dy = 2 k y + 3k y − 1+ x0 − 1+ x 0

= 2k(1 − x) + 3k(1 − x) = 5k(1 − x)



 3k(1 + x) ; −1 < x < 0





p X (x) = 5k(1 − x) ; 0 ≤ x < 1

 0 ; sicer



∞

Z

p Y (y) = pXY (x, y) dx

−∞

− 1 < y < 0 :

Z 0 Z 1+y 0 1+y

p ( y ) = k dx + 2 k dx = ky + 2 ky

Y

− 1 − y 0 − 1 − y0

= k(1 + y) + 2k(1 + y) = 3k(1 + y)



0 ≤ y < 1 :

Z 0 Z 1−y 0 1−y

p ( y ) = 2 k dy + 3 k dy = 2 ky + 3 ky

Y

− 1+ y 0 − 1+ y0

= 2k(1 − y) + 3k(1 − y) = 5k(1 − y)



 3k(1 + y) ; −1 < y < 0





p Y (y) = 5k(1 − y) ; 0 ≤ y < 1

 0 ; sicer





NALOGE 97



Diferencialni entropiji:

∞ ∞



h(X) = − p X (x) log p ) dx − 2 X ( x = pX(x) ln pX (x) dx ln 2 Z Z 1

−∞ −∞

0 1

1 Z 1 Z

h(X ) = − 3k(1 + x) ln 3k(1 + x) dx − 5k(1 − x) ln 5k(1 − x) dx

ln 2 ln 2

−1 0

3k(1 + x) = u x = −1 : u = 0 x = 0 : u = 3k 3k dx = du

5k(1 − x) = v x = 0 : v = 5k x = 1 : v = 0 − 5k dx = dv



3k 0

1 Z du 1 Z dv

h(X ) = − u ln u + v ln v

ln 2 3k ln 2 5k

0 5k



= 1 3 ln u 1 k ln v 1 0 2 2 − u − + v − ln 2 2 4 0 2 4 5 k

1 ln 3 k 1

h 2 ( X ) = − 9 k −

ln 2 2 4

ln 0 1 ln 0 1 ln 5 k 1

+ 02 2 2 − + 0 − − 25 k −

2 4 2 4 2 4

1 ln 3 k 1 ln 5 k 1

h 2 2 ( X ) = − 9 k − − 25 k − = 0,63

ln 2 2 4 2 4

p Y (y) = pX(x) ⇒ h(Y ) = h(X ) = 0,63

Vezana diferencialna entropija:

Z Z

h(X, Y ) = − p XY (x, y) log p x, y) dxdy 2 XY (

0 0 0 1+x

Z Z Z Z

h(X, Y ) = − k log k dydx − 2k log 2k dydx 2 2

−1 −1−x −1 0

1 0 1 1−x

Z Z Z Z

− 2k log 2k dydx − 3k log 3k dydx 2 2

0 −1+x 0 0

0 0 0 1+x

Z Z Z Z

h(X, Y ) = − 0,25 log2 0,25 dydx − 0,5 log2 0,5 dydx

−1 −1−x −1 0

1 0 1 1−x

Z Z Z Z

− 0,5 log 0,5 dydx − 0,75 log 0,75 dydx 2 2

0 −1+x 0 0



98 KAPACITETA KANALA



Z 0 Z 0 0 0 0

Z Z 2 x 1

dydx 0 0 = y | dx = (1 + x ) dx = x | + = 1 − = 0,5

− 1 − x − 1 2 2

−1

−1 −1−x −1 −1

Z Z Z Z 2 0 0 1+x 0 0

dydx = y | dx = (1 + x)dx = x| + = 1 − , − = 05 0 1 2 1+x 0 x 1

2

−1

−1 0 −1 −1



Z1 0 1 1 1 Z Z Z 2 x 0 1 1 dydx = y | dx = (1 − x ) dx = x | − = 1 − = 0,5 − 1+ x 0 2 2 0 − 0 1+ x 0 0

1 1−x 1 1

Z 1 Z Z Z 2 x 1

dydx 1−x 1 = y | dx = (1 − x ) dx = x | − = 1 − = 0,5

0 0 2 2

0

0 0 0 0



h(X, Y ) = 0,5 · 0,5 + 0,5 · 0,5 + 0,5 · 0,5 + 0,31 · 0,5 = 0,905

Iz diferencialnih entropij marginalnih verjetnostnih porazdelitev in vezane diferen-

cialne entropije izraˇcunamo povpreˇcno preneseno informacijo:



I(X; Y ) = h(X) + h(Y ) − h(X, Y ) = 0,63 + 0,63 − 0,91 = 0,35



I P P P(y|x) ( x ; y ) = P xy 2 ( x, y) · log Vzajemna informacija med dvema P

(y)

spremenljivkama

I(X; Y ) = H (X) + H(Y ) − H (X, Y ) Vzajemna informacija dveh spre-

menljivk

h R ∞ ( X ) = − p (x) log p (x) dx. Diferencialna entropija

−∞ X 2 X

h R R ( x, y ) = − pxy 2 ( x, y ) log p (x, y) dx dy Vezana diferencialna entropija xy



9. POGLAVJE



KAPACITETA KANALA ZA RAZLI ˇ CNE



PORAZDELITVE



V tem poglavju bomo raziskali eno najpomembnejˇsih lastnosti komunikacijskih kanalov: njihovo kapaciteto. Osredotoˇcili se bomo predvsem na Gaussov kanal, ki modelira vpliv ˇsuma z normalno porazdelitvijo, kar je v realnih sistemih pogosto zelo dober pribliˇzek.

Kapaciteta kanala nam pove, kakˇsna je najveˇcja moˇzna hitrost prenosa informacij, pri

kateri ˇse vedno lahko doseˇzemo zanemarljivo napako s primerno kodiranjem. Spoznali bomo tudi diferencialno entropijo kot orodje za kvantifikacijo informacije v neomejenih, zveznih porazdelitvah.

Poglobljeno bomo obravnavali Gaussovo in Laplaceovo porazdelitev, izrazili entropijo

signalov in ˇsuma, povezali moˇc signala z napakami pri prenosu in nazorno izraˇcunali ka-pacitete za razliˇcne realne komunikacijske scenarije (npr. audio kanal, televizijski signal, HD-video).

Za dodatno branje priporoˇcamo naslednje vire:



C. E. Shannon: A Mathematical Theory of Communication [4]



T. M. Cover, J. A. Thomas: Elements of Information Theory [2]



S. Haykin: Communication Systems, 5th ed. [7]



9.1 Naloge



M. Kunaver, Teorija informacij in izvorno kodiranje. 99

©2025 Zaloˇzba FE

100 KAPACITETA KANALA ZA RAZLI ˇ CNE PORAZDELITVE



Naloga 9.1: Izraˇcunajte diferencialno entropijo Gaussove nakljuˇcne spremenljivke z

enosmerno vrednostjo 3 in standardno deviacijo 2.



Reˇsitev:



p 1 1 x−µ 2 − ( ) X ( x ) = √ · e 2 σ

σ 2π



Z Z ∞ ∞ 1

h(X ) = − p X(x) log p dx = 2 X ( x ) − pX(x) ln pX (x) dx

−∞ ln 2 −∞



h 1 Z ∞ 2 1 1 x − µ 1 2 1 x − µ − ( ) − ( ) ( X ) = − √ · e 2 σ ln √ · e 2 σ dx ln 2 −∞ σ 2 π σ 2 π



h 1 Z ∞ 1 x − µ 2 1 x − µ 2 − ( ) 1 − ( ) ( X ) = − √ e 2 σ ln √ + ln e 2 σ dx

σ 2π ln 2 −∞ σ 2π



h 1 Z ∞ 2 ! 1 x − µ 2 1 1 x − µ − ( ( X ) = − √ e 2 σ ) ln √ − dx 2 σ 2 π ln 2 −∞ σ 2 π σ



h 1 Z ∞ − 1 1 − ( xµ 2 e 2 σ ) ( X ) = − √ ln √ dx

σ 2π ln 2 σ 2π −∞



− 1 Z ∞ 2 ! − x − µ 1 − ( x µ 2 e 2 σ ) dx 2 σ −∞



h 1 Z ∞ − 1 1 1 xµ 2 − ) e 2 ( ( X ) = − ln √ √ σ dx ln 2 σ 2 π −∞ 2 π

1 Z ∞ 2 ! x − µ

− p X (x) dx

2 σ −∞

1 Z ∞ Z ∞ 1 1

h 2 ( X ) = − ln √ p ( x ) dx − ( x − µ )p (x) dx

ln 2 X X 2 σ 2 π 2 σ

−∞ −∞

1 1 1

h 2 ( X ) = − ln √ · 1 − · σ

ln 2 2 σ 2 π 2 σ



h(X ) = − log √ 2 − = log2 σ 2π + log2 e = log2 σ 2πe 2 √ 1 1 ln e 1 √

σ 2π ln 2 2



h 1 2 ( X ) = log 2 2 πeσ = 3,05 2



Naloga 9.2: Izraˇcunajte diferencialno entropijo nakljuˇcne spremenljivke z Laplaceovo

verjetnostno porazdelitvijo, enosmerno vrednostjo 0,1 in standardno deviacijo 0,5.



NALOGE 101



Reˇsitev:

1 √

p − 2|x−µ| X σ (

x) = √ · e

σ 2

Z Z ∞ 1

∞

h(X) = − p X (x) log p ) = (x p ( ) 2 X ( x dx − p X ) ln X x dx

−∞ −∞ ln 2



h 1 Z ∞ √ √ | 1 2 x − µ | 1 2 | x − µ | − − ( X ) = − √ · e σ · ln √ · e σ dx ln 2 −∞ σ 2 σ 2



h 1 1 Z ∞ √ √ 2 | x − µ | 1 2 | x − µ | − − ( X ) = − · √ e σ ln √ + ln e σ dx

ln 2 σ 2 −∞ σ 2



h 1 ∞ √ ! √ 1 Z 2 | x − µ | 1 2 | x − µ | − ( X ) = − · √ e σ ln √ − dx

ln 2 σ 2 −∞ σ 2 σ



h 1 1 1 Z ∞ √2|x−µ| − ( X ) = − · √ ln √ e σ dx ln 2 σ 2 σ 2 −∞ √ ∞ Z √ 1 1 2 | x − µ | 2 | x − µ | − + · √ e σ dx ln 2 σ 2 σ −∞

x − µ

t = x = −∞ : t = −∞ x = ∞ : t = ∞

σ

dx

dt =

σ



h 1 1 Z ∞ ∞ 1 1 Z √ −2|t| ( X ) = − ln √ p X ( x ) dx + · | t | eσ dx ln 2 σ 2 ln 2 σ −∞ −∞



h 1 1 1 Z ∞ √ −2|t| ( X ) = − ln √ · 1 + | t | edx ln 2 σ 2 ln 2 −∞



h 1 1 1 Z ∞ √ −2t ( X ) = − ln √ · 1 + · 2 tedx

ln 2 σ 2 ln 2 0



= log 2t σ 2 + 2 · e − √ − 2 ln 2 2 2 0 √ ∞ 1 √ t 1 −



h √ √ 1 t 1 − 2 t ( X ) = log σ 2 + lim 2 · e − √ − 2 ln 2 t →∞ 2 2

√ 0 1

− − 2·0 2 · e −√ −

2 2

√

Clen ˇ 2t e raste veliko hitreje kot t, zato celota upada proti 0.



√ √ √ 1 1 1 ln e

h(X ) = log σ 2 + 0 − 2 − = log σ 2 + = log σ 2 + 2 2 2 ln 2 2 ln 2 ln 2

√ √

h(X ) = log2 σ 2 + log2 e = log2 2eσ



h 1 2 ( X ) = log 2 eeσ = 0,942 2 2

102 KAPACITETA KANALA ZA RAZLI ˇ CNE PORAZDELITVE



Naloga 9.3: Nakljuˇcna spremenljivka Y je definirana kot vsota nakljuˇcnih spre-

menljivk X in Z z Gaussovo porazdelitvijo gostote verjetnosti. Izrazite pogojno difer-

encialno entropijo h(Y |X) z diferencialnima entropijama h(X ) in h(Z).



Reˇsitev: ˇ Ce seˇstejemo dve nakljuˇcni spremenljivki, ima dobljena nakljuˇcna spre-

menljivka povpreˇcno vrednost, ki je vsota povpreˇcnih vrednosti originalnih spre-

menljivk in moˇc nove nakljuˇcne spremenljivke je enaka vsoti moˇci originalnih nakljuˇcnih

spremenljivk.



Y 2 2 2 = X + Z, µ = µ + µ , σ = σ + σ

Y X Z Y X Z



Izraz za pogojno diferencialno entropijo h(Y |X ) moramo predelati tako, da ga bomo

lahko izrazili s pomoˇcjo diferencialnih entropij h(X) in/ali h(Z), zato si ju tu izpiˇsimo:

Z ∞ Z ∞

h(X ) = − p X(x) log2 pX (x) dx, h(Z ) = − pZ(z) log2 pZ (z) dz

−∞ −∞

Pogojna diferencialna entropija h(Y |X) je povpreˇcje vseh pogojnih diferencialnih

entropij h(Y |X = x), kjer nakljuˇcno spremenljivko X fiksiramo na eno vrednost x:

Z ∞

h(Y | X ) = pX(x) · h(Y | X = x) dx

−∞

Z ∞

h(Y | X = x) = − p Y ) log p (y, x | X = x ( y, x 2 Y dx | X = x )

−∞



Ce je nakljuˇcna spremenljivka X fiksirana na vrednost x, je nakljuˇcna spremenljivka ˇ

Y definirana kot:



Y 2 2 Y Z X = = x + Z, µ = x + µ , σ = σ . x

Y Z



Skratka nakljuˇcna spremenljivka Y je enaka nakljuˇcni spremenljivki Z, le da je njena

srednja vrednost premaknjena za x. Ker je entropija neodvisna od srednje vrednosti

nakljuˇcne spremenljivke, velja



h(Y | X = x) = h(Z).

NALOGE 103



Sedaj lahko zapiˇsemo:

Z ∞

h(Y | X) = p X (x) · h(Y | X = x) dx

−∞

Z ∞ Z ∞

= p X (x) · h(Z) dx = h(Z ) pX (x) dx

−∞ −∞



h(Y | X) = h(Z)



Naloga 9.4: Izrazite povpreˇcno moˇc diskretne nakljuˇcne spremenljivke z L nivoji,

povpreˇcno vrednostjo 0 in enakomerno verjetnostno porazdelitvijo. Pri tem pred-

postavite, da so posamezni diskretni nivoji razmaknjeni za kσ , kjer σ predstavlja

standardno deviacijo prisotnega ˇsuma, in k faktor s katerim bomo na koncu nastavili

varno razdaljo med posameznimi nivoji.



Reˇsitev: ˇ Ce za L izberete sodo ˇstevilo boste potrebovali izraz



N N

X 2 2 (2 n − 1) = 4 N − 1

3

n=1



Ce za L izberete liho ˇstevilo boste potrebovali izraz ˇ

N −1

X 2 N 2

n 2 = N − 1

− 12

n N 1 = −

2

Povpreˇcna moˇc nakljuˇcne spremenljivke:



S 2 X 2 = X = xP (x ) i X i





i




Izraziti moramo posamezne nivoje x i:



104 KAPACITETA KANALA ZA RAZLI ˇ CNE PORAZDELITVE



kσ

xi = ikσ − , i = 1, 2, 3, . . . , L/2

2

Verjetnost vseh nivojev je 1/L. Upoˇstevajmo, da je moˇc pozitivnih in negativnih nivo-

jev enaka:



L/2 L/2 2 L/2 2 2

X X X 1 2 kσ 2 k σ

S 2 2 2 = 2 x · = (2 i − 1) = · (2 i − 1)

i L L 2 L 4

i=1 i=1 i=1

2 2 2 2 ! 2 2 k σ L/ 2 L k σ

S 2 = · · 4 − 1 = ( L − 1)

L 4 3 2 12



Entropija nakljuˇcne spremenljivke z enakomerno verjetnostno porazdelitvijo je

H (X ) = log (L) Zato iz moˇci izrazimo L: 2



k 12S 2 = L − 1 2 2 σ



L = + 1 2 2 k r 12S

σ

In ga vstavimo v izraz za entropijo:



r ! 12 S 1 12 S

H (X ) = log + 1 = log + 1 2 2 2 2 2 2 k σ 2 k σ



Ce upoˇstevamo, da je ˇ 2 σ standardna deviacija ˇsuma, je σ moˇc ˇsuma N:



H (X ) = log 2 1 + · 2 2 1 12 S

k N



NALOGE 105



Ta izraz je zelo podoben izrazu za kapaciteto Gaussovega kanala 1 S C = log (1 + ).

2 2 N

Razlikuje se le za ˇclen 12 . Oba izraza postaneta enaka, ˇce faktor k izberemo tako, da

k2

ta ˇclen postane 1:

√

k = 12 ≈ 3, 464



Ce za odmik med posameznimi nivoji vhodnega signala izberemo ˇ 3, 46σ , bo verjet-

nost, da pride do napake pri prenosu 8, 4%.



Naloga 9.5: Ali je teoretiˇcno moˇzno brez napak prenaˇsati signal s standardno de-

viacijo 0, 1V s hitrostjo 10M bit/s preko Gaussovega kanala s pasovno ˇsirino 100kHz

in karakteristiˇcno impedanco 50Ω pri temperaturi 20 °C? Izraˇcunajte energijo posa-

meznega bita informacije? Na kolikˇsno vrednost bi morali nastaviti standardno de-

viacijo signala, da bi bila kapaciteta kanala enaka ˇzeleni hitrost prenosa? Kolikˇsna

bi morala biti pasovna ˇsirina kanala, da bi bila kapaciteta kanala enaka ˇzeleni hitrost

prenosa pri nespremenjeni velikosti? k = 1, 3810J/K



Reˇsitev: Moˇc signala:



S U 2 2 2 ef σ 0 , 01 V = = = = 0,0002 W R R 50 Ω



ˇSumna moˇc:



N 5 −23 −16 = BkT = 10 Hz · 1 , 38 · 10 J/K · 293 K = 4 , 04 · 10 W



Kapaciteta kanala:



S

C 6 = B · log 1 + = 3 , 88 · 10 sh/s

2 N



Energija bita:



E S 0,0002 W −11 = b = = 5 , 16 · 10 J 6 C 3 , 88 · 10 bit/s



Zahtevana moˇc signala za mejno kapaciteto kanala:



B = log 1 + 2 N C S



C S

2 B = 1 +

N



S C 107 bit/s −16 14 B = 2 − 1 N = 2 105 Hz − 1 · 4 , 04 · 10 W = 5 , 12 · 10 W



106 KAPACITETA KANALA ZA RAZLI ˇ CNE PORAZDELITVE



σ √ p 14 = U ef = RS = 5 , 12 · 10 W · 50 Ω = 160 MV



Naloga 9.6: Telefonski avdio kanal ima pasovno ˇsirino 3,4 kHz. Izraˇcunajte ka-

paciteto kanala za SNR 30 dB. Izraˇcunajte minimalno SNR za prenos 57600 bit/s.



Reˇsitev: Kapaciteta kanala:

S 30

= 30 dB = 1010 = 1000

N



C = B log 1 + = 3400 · log 1001 = 33889 bit/s 2 2 N S

Minimalno razmerje SNR:



C S

2 B = 1 +

N



S C 57600

= 2 B − 1 = 2 3400 − 1 = 125834 = 51 dB

N



Naloga 9.7: Telefonski avdio kanal s pasovno ˇsirino 3400 Hz in razmerjem med sig-

nalom in ˇsumom 20 dB, ˇzelimo uporabiti za tekstovni terminal, ki pozna 128 znakov.

Predpostavite, da je verjetnostna porazdelitev znakov enakomerna in da je informaci-

jski vir brez-spominski. Izraˇcunajte kapaciteto kanala in maksimalno moˇzno hitrost

prenosa znakov, da ˇse ne prihaja do napak.



Reˇsitev: Kapaciteta kanala:



C = B log 1 + = 3400 log (1 + 100) = 22638 2 2 N S



Entropija vira:



H (X ) = log L = log 128 = 7 2 2



Maksimalna moˇzna hitrost prenosa znakov:



C 22638 sh/s

fD = = = 3234 baud

H(X ) 7 sh/sim



NALOGE 107



Naloga 9.8: ˇ 5 Crno-bela televizijska slika je sestavljena iz 4 x 10 toˇck, od katerih lahko

vsaka zasede enega izmed 220-ih odtenkov sivine z enako verjetnostjo. Frekvenca

osveˇzevanja slike je 25 Hz. Kolikˇsna mora biti pasovna ˇsirina informacijskega kanala,

ˇce predpostavimo razmerje signal/ˇsum 50 dB. (Dejanska pasovna ˇsirina kanala za tele-vizijski video signal v standardni loˇcljivosti znaˇsa 5 MHz in je umeˇsˇcena v frekvenˇcni pas ˇsirine 8 MHz). Kolikˇsna bi morala biti kapaciteta kanala za prenos ne-stisnjene barvne slike v HD loˇcljivosti (1920×1080 toˇck, povpreˇcno 16 bitov na toˇcko (barvna prostorska loˇcljivost 4:2:2), 25 slik na sekundo)?



Reˇsitev: Entropija ene slike (ob predpostavki, da slikovne toˇcke niso med sabo

odvisne):



H N 5 ( X ) = log L = N log L = 4 10 log · 220 = 3112544 sh

2 2 2



Potrebna kapaciteta kanala:



C −1 = H ( X ) · f = 3112544 sh · 25 s = 77813597 sh/s

SLIK



Pasovna ˇsirina kanala, potrebna za prenos videa:



B = = = 4684841 Hz ≈ 4,7 MHz S log C 77813597 sh/s

2 1 + log (1 + 100000) 2 N

Entropija ene slike v HD loˇcljivosti:



HHD (X) = NHD log L = 1920 · 1080 · 16 = 33177600 sh 2 HD



Potrebna kapaciteta kanala za video HD loˇcljivosti:



C −1 = H ( X ) · f = 33177600 sh · 30 s = 99532800 sh/s

HD HD HDSLIK



Pasovna ˇsirina kanala, potrebna za prenos HD videa:



BHD = = = 59924665 Hz ≈ 60 MHz S log CHD 99532800 sh/s

2 1 + log (1 + 100000) N 2



p 1 1 x −µ 2 − 2 ( ) X ( x ) = √ · e σ Gaussova porazdelitev σ 2 π √ | x − µ | 1 − 2 p X ( x ) = √ · e σ Laplaceova porazdelitev σ 2

h 1 2 ( X ) = log 2 πeσ Diferencialna entropija Gaussove porazdelitve

2 2

h 1 2 ( X ) = log 2 eeσ Diferencialna entropija Laplaceove porazdelitve

2 2

SN R S = 10 log Razmerje signal/ˇsum v decibelih

dB 10 N

C S = B · log 1 + Kapaciteta kanala

2 N



10. POGLAVJE



VZOR ˇ CENJE



V tem poglavju bomo obravnavali osnovne pojme vzorˇcenja analognih signalov, kot jih naletimo pri digitalizaciji v sodobnih komunikacijskih sistemih. Pri pretvorbi analognega signala v diskretno ˇcasovno obliko moramo zagotoviti, da signal vsebuje dovolj informacij, da ga lahko kasneje rekonstruiramo.

Kljuˇcni koncept, ki ga bomo podrobneje spoznali, je Nyquistov vzorˇcevalni teorem,

ki doloˇca najmanjˇso vzorˇcevalno frekvenco, potrebno za brezizgubno rekonstrukcijo sig-nala. ˇ Ce vzorˇcimo z niˇzjo frekvenco, se lahko zgodi aliasing — pojav, pri katerem viˇsje frekvence navidezno postanejo niˇzje zaradi zrcaljenja spektra.

Na konkretnih primerih bomo prikazali:



kako frekvence v signalih vplivajo na spekter po vzorˇcenju,



kako ugotovimo, ali bo pri dani vzorˇcevalni frekvenci priˇslo do aliasinga,



kako se spektralne komponente preslikajo po vzorˇcenju.



Poglavje vkljuˇcuje veˇc grafiˇcnih primerov, ki prikazujejo zrcaljenje spektra okoli veˇc-

kratnikov vzorˇcevalne frekvence in kako se doloˇcajo zaznane frekvence.

Za dodatno branje priporoˇcamo naslednje vire:



S. Haykin: Communication Systems, 5th ed. [7]



S. Tomaˇziˇc: Osnove telekomunikacij I [5]



M. Kunaver, Teorija informacij in izvorno kodiranje. 109

©2025 Zaloˇzba FE

110 VZOR ˇ CENJE



10.1 Naloge



Naloga 10.1: Z vzorˇcevalno frekvenco 20kHz vzorˇcimo sinusni signal s frekvenco

32kHz. Kolikˇsna bo frekvenca najniˇzje spektralne komponente vzorˇcenega signala.



Reˇsitev: Pri vzorˇcenju se spekter zrcali okoli veˇckratnikov vzorˇcevalne frekvence f0

v obmoˇcju f0 okoli vsakega veˇckratnika vzorˇcevalne frekvence.

2



Veˇckratniki vzorˇcevalne frekvence so 20, 40, 60 kHz,. . . V graf vriˇsemo spektralno

komponento merjenega signala (oznaˇcena z debelo ˇcrto). Prezrcalimo jo okoli na-

jbliˇzjega veˇckratnika vzorˇcevalne frekvence. Nato spekter okoli tega veˇckratnika

vzorˇcevalne frekvence skopiramo ˇse okoli vseh ostalih veˇckratnikov vzorˇcevalne fre-

kvence. Nato z grafa odˇcitamo frekvenco najniˇzje spektralne komponente



Frekvenca najniˇzje spektralne komponente znaˇsa 8 kHz.



Naloga 10.2: Doloˇcite minimalno vzorˇcevalno frekvenco f0, da bo velikost tu-

jega spektra v vzorˇcenem signalu vsaj za 40dB manjˇsa od koristnega spektra, ki je

v frekvenˇcnem obmoˇcju od 0 do 3400Hz. Za proti-prekrivni filter uporabite nizko-

prepustni filter z normiranim potekom na sliki.



NALOGE 111



Reˇsitev: Tuji spekter je tisti del spektra, ki se zaradi vzorˇcenja preslika v osnovni

spekter. V danem primeru je osnovni spekter v obmoˇcju med 0 Hz in polovico

vzorˇcevalne frekvence. Filter nastavimo tako, da bo zgornja frekvenˇcna meja filtra

na zgornji meji koristnega signala



f z = 3400Hz



Filter dovolj zaduˇsi spektralne komponente nad 1,35fz, da ne motijo, tudi ˇce se

preslikajo nazaj v osnovni frekvenˇcni pas, ato je lahko pri tej frekvenci polovica

vzorˇcevalne frekvence. Vzorˇcevalna frekvenca je torej



f0 = 2 · 1,35fz = 2 · 1,35 · 3400 Hz = 9180 Hz.



Naloga 10.3: Doloˇcite minimalno vzorˇcno frekvenco f 0 za rekonstrukcijo govornega

signala v frekvenˇcnem obmoˇcju od 0 do 3400Hz. Maksimalna velikost tujega spektra

sme biti −40dB. Za protiprekrivni in rekonstrukcijski filter uporabite nizkoprepustni

filter z normiranim potekom na sliki.





Reˇsitev: ˇ Ce je poleg proti-prekrivnega filtra znan tudi rekonstrukcijski filter, lahko

pri izbiri vzorˇcevalne frekvence upoˇstevamo oba. V tem primeru lahko vzorˇcevalno

frekvenco ˇse malo zniˇzamo tako, da proti-prekrivni filter ne zaduˇsi tujega spektra

popolnoma, temveˇc preostanek tujega spektra dovolj zaduˇsi ˇsele rekonstrukcijski fil-

ter. Primer je prikazan na sliki:



112 VZOR ˇ CENJE



V primeru, ko je frekvenˇcni potek proti-prekrivnega in rekonstrukcijskega filtra enak

in linearen v semi-logaritmiˇcnem merilu, lahko polovico vzorˇcevalne frekvence nas-

tavimo na sredino med zgornjo mejno frekvenco filtra in frekvenco pri kateri filter

doseˇze zadostno duˇsenje. Skica:



NALOGE 113



f0 fz + 1,35 · fz

=

2 2



f0 = 2,35 · fz = 7990 Hz ≈ 8 kHz



Naloga 10.4: Podan je dvostranski amplitudni spekter zveznega signala. Zvezni

signal vzorˇcimo s frekvenco 40kHz. Skicirajte spekter rekonstruiranega signala pred

rekonstrukcijskim filtrom, ˇce uporabimo regularno vzorˇcenje s ˇsirino impulza T τ = .

3

Doloˇcite zgornjo frekvenˇcno mejo fz rekonstrukcijskega filtra in njegovo minimalno

duˇsenje pri frekvenci f0 − fz, da bo tuji spekter zaduˇsen vsaj za 40dB.



Reˇsitev: ˇ Ce bi lahko rekonstruirali signal z idealnim vzorˇcenjem (z Diracovimi

impulzi) bi imel rekonstruirani signal periodiˇcen spekter:



Spekter regularno vzorˇcenega signala, kjer je ˇcas zadrˇzevanja enak ˇcasu med vzorci,

je enak spektru idealno vzorˇcenega signala pomnoˇzenim s prevajalno funkcijo za-

drˇzevalnega vezja.



τ sin( πτ f )

| H ( f ) | = .

R T πτ f

114 VZOR ˇ CENJE



Ce je ˇcas zadrˇzevanja krajˇsi od ˇcasa med vzorci, se funkcija ˇ |HR(f )| ustrezno raztegne

in velikost spektra signala se zniˇza za faktor τ . Pred rekonstrukcijo velikost signala

T

obiˇcajno ustrezno poveˇcamo za faktor T , tako da velikost spektra ostane enako velika,

τ

a se tega dostikrat niti ne omeni:



Zgornja frekvenˇcna meja rekonstrukcijskega filtra fz mora biti 5kHz. Duˇsenje za-

drˇzevalnega vezja pri frekvenci 0 je

τ 1

|H R (0 kHz)| = =

T 3

Duˇsenje zadrˇzevalnega vezja pri f0 − fz = 35kHz je



| T T 35 kHz sin π · · 35 kHz 1 sin π · 1 3 3 H R (35 kHz ) | = · = 3 · 40 kHz = · 0,866 T T π · · 35 kHz 3 35 kHz 3 π · 3 3 · 40 kHz

Glede na duˇsenje pri frekvenci 0 je to



H (35 kHz )

R = 0,866

R H (0 kHz )

oziroma

H (35 kHz )

R [dB] = 20 · log(0,866) = −1,25 dB

R H (0 kHz )



Skupno duˇsenje zadrˇzevalnega vezja in rekonstrukcijskega filtra pri frekvenci f0–fz

mora biti 40dB, kar pomeni, da mora biti duˇsenje rekonstrukcijskega filtra



H (35 kHz )

| R H ( f − f ) | = − 40 dB − [dB]

r 0 z H (0 kHz )

R

= −40 dB − (−1,25 dB) = −38,75 dB



Naloga 10.5: Spekter zveznega signala je omejen na frekvenˇcno obmoˇcje 20,6 do

23,6kHz. Doloˇcite najniˇzjo vzorˇcevalno frekvenco f0 tako, da bosta frekvenˇcna

razmika osnovnega spektra do zrcalnih na obeh mejah enaka. Za izbrano frekvenco

f0 nariˇsite tudi simboliˇcno predstavitev spektra idealno vzorˇcenega signala



NALOGE 115



Reˇsitev: Nalogo lahko reˇsimo z uporabo neenaˇcbe



2f z 2fs

≤ f 0 ≤

K K − 1

kjer



f 23 , 6

K z = int = int = 7

fz − fs 23,6 − 20,6



pove, kolikˇsno je najveˇcje ˇstevilo frekvenˇcnih pasov dane ˇsirine, ki jih lahko umes-

timo na frekvenˇcno obmoˇcje med 0 in f .



2f z 2fs

≤f0 ≤

7 7 − 1

6,743 kHz ≤f0 ≤ 6,867 kHz



Vzorˇcevalno frekvenco postavimo v sredino med obe meji



6,743 kHz + 6,867 kHz

f0 = = 6,805 kHz

2

Nalogo lahko reˇsimo tudi s pomoˇcjo skice. Tudi v tem primeru izraˇcunamo najveˇcje

moˇzno ˇstevilo frekvenˇcnih pasov v obmoˇcju med 0 in fz na enak naˇcin:



f 23 , 6

K z = int = int = 7

fz − fs 23,6 − 20,6



Nato nariˇsemo skico in iz skice zapiˇsemo enaˇcbe:



B = fz − fs = 23,6 kHz − 20,6 kHz = 3 kHz

f s = 13∆ + 6B

fs − 6B 20,6 kHz − 6 · 3 kHz

∆ = = = 0,2 kHz

13 13

f0 = 4∆ + 2B = 4 · 0,2 kHz + 2 · 3 kHz = 6,8 kHz



2fz 2fs ≤ f ≤ Nastavek za najniˇzjo vzorˇcevalno frekvenco

K 0 K−1

K = int z dodatek k zgornji enaˇcbi f f

z s − f

F min = min |f − kfs| Najniˇzja opaˇzena (aliasna) frekvenca po vzorˇcenju

k∈Z





DODATEK A




ANALIZA ˇ CASOVNIH VRST



Primer ureditve vhodnih podatkov:



Month,#Passengers

1949-01,112

1949-02,118

1949-03,132

1949-04,129

1949-05,121



S pomoˇcjo spodnje kode, lahko potem podatke uvozimo, analiziramo in izdelamo primeren

model ˇcasovne vrste.



import pandas as pd

import numpy as np

import matplotlib.pyplot as plt

from statsmodels.tsa.stattools import adfuller, acf, pacf from statsmodels.tsa.seasonal import seasonal_decompose from statsmodels.tsa.arima.model import ARIMA import warnings

warnings.filterwarnings(’ignore’)



# Uvoz podatkov

df = pd.read_csv(’AirPassengers.csv’)

M. Kunaver, Teorija informacij in izvorno kodiranje. 117

©2025 Zaloˇzba FE

118 ANALIZA ˇ CASOVNIH VRST



df[’Month’] = pd.to_datetime(df[’Month’], format=’%Y-%m’) df.set_index(’Month’, inplace=True)

ts = df[’#Passengers’]



# Funkcija za testiranje stacionarnosti

def test_stationarity(timeseries,figName):



#Determing rolling statistics

rolmean = timeseries.rolling(12).mean()

rolstd = timeseries.rolling(12).std()



#Plot rolling statistics:

plt.figure()

orig = plt.plot(timeseries, color=’blue’,label=’Original’) mean = plt.plot(rolmean, color=’red’, label=’Rolling Mean’) std = plt.plot(rolstd, color=’black’, label = ’Rolling Std’)



plt.legend(loc=’best’)

plt.title(’Tekoˇ ce povpreˇ cje in standardni odklon’) plt.xlabel("Leto")

plt.ylabel("ˇ Stevilo potnikov")

plt.savefig(figName, format="pdf", bbox_inches="tight") plt.show()



#Perform Dickey-Fuller test:

print (’Results of Dickey-Fuller Test:’)

dftest = adfuller(timeseries, autolag=’AIC’)

dfoutput = pd.Series(dftest[0:4], index=[’Test Statistic’,’p-value’, ’#Lags Used’,’Number of Observations Used’])

for key,value in dftest[4].items():

dfoutput[’Critical Value (%s)’%key] = value

print (dfoutput)



# Naslednji koraki sluˇ zijo doseganju zadovoljive stopnje stacionarnosti.



# Logaritemska pretvorba

ts_log = np.log(ts)



# Odstranitev trenda: drseˇ ce povpreˇ cje

moving_avg = ts_log.rolling(window=12).mean() ts_log_mv_diff = ts_log - moving_avg

ts_log_mv_diff.dropna(inplace=True)



# EWMA

expwighted_avg = ts_log.ewm(halflife=12).mean() ts_log_ewma_diff = ts_log - expwighted_avg



# Diferenciranje

ANALIZA ˇ CASOVNIH VRST 119



ts_log_diff = ts_log.diff().dropna()



# Sezonska razˇ clenitev

decomposition = seasonal_decompose(ts_log, model=’additive’) trend = decomposition.trend

seasonal = decomposition.seasonal

residual = decomposition.resid



# Ko doseˇ zemo stacionarnost s pomoˇ cjo ACF in PACF # doloˇ cimo parametre ARIMA modela

# ACF in PACF

lag_acf = acf(ts_log_diff, nlags=20)

lag_pacf = pacf(ts_log_diff, nlags=20)



# ARIMA model

model = ARIMA(ts_log, order=(2, 1, 2))

results_ARIMA = model.fit()



# Inverzna transformacija in napoved

predictions_ARIMA_diff = results_ARIMA.fittedvalues predictions_ARIMA_log = ts_log + predictions_ARIMA_diff predictions_ARIMA = np.exp(predictions_ARIMA_log)





DODATEK B




ARITMETI ˇ CNO KODIRANJE



Spodnjo kodo lahko uporabimo za aritmetiˇcno kodiranje, opisano v poglavju 6.



def aritmeticnoKodiranje(verjetnosti,zaporedje,interval,reverse=False):

if reverse: # ˇ ce ˇ zelimo, da je stop znak na vrhu

verjetnosti.reverse()



new_int = [];

output = ""

for j in zaporedje:

new_int = [];

for i in range(len(verjetnosti)):

razpon = (interval[1] - interval[0])/100

if i == 0:

temp = [interval[0],interval[0]

temp += razpon*verjetnosti[i]*100]

new_int.append(temp)

next_b = temp[1];

elif i == (len(verjetnosti)-1):

temp = [next_b,interval[1]]

new_int.append(temp)

else:

temp = [next_b,next_b + razpon*verjetnosti[i]*100]

M. Kunaver, Teorija informacij in izvorno kodiranje. 121

©2025 Zaloˇzba FE

122 ARITMETI ˇ CNO KODIRANJE



new_int.append(temp)

next_b = temp[1]

if not reverse:

interval = new_int[j-1]

else:

interval = new_int[len(verjetnosti)-j]

output += f"Trenutni ˇ clen je {j}"

output += f"interval pa je {interval[0]:.5f}" output += f"------{interval[1]:.5f}\n"

print(output)



Primer uporabe:

verjetnosti = [4/9,1/9,3/9,1/9]

zaporedje = [2,3,3,1,4]

interval = [0.0,1.0]

reverse = False

aritmeticnoKodiranje(verjetnosti,zaporedje,interval,reverse)





DODATEK C




LZW (DE)KODIRANJE



Spodnji funckiji uporabimo za LZW kodiranje in dekodiranje. Pri tem smo pozorni, da je potrebno ustrezno inicializirati slovar (loˇceno podati zaˇcetne simbole).



def kodiraj(uncompressed,dictionary):

dict_size = len(dictionary)

w = ""

result = []

for c in uncompressed:

wc = w + c

if wc in dictionary: #preverim ˇ ce sem kombinacijo ˇ ze sreˇ cal

w = wc

else:

result.append(dictionary[w])

# Dodam v slovar.

dictionary[wc] = dict_size

dict_size += 1

w = c

# Dodam kodo v kodirano vsebino

if w:

result.append(dictionary[w])

print("Kodirni slovar:", dictionary)

return result

M. Kunaver, Teorija informacij in izvorno kodiranje. 123

©2025 Zaloˇzba FE

124 LZW (DE)KODIRANJE



def dekodiraj(compressed,dictionary):

from io import StringIO

dict_size = len(dictionary)

result = StringIO()

w = dictionary[compressed.pop(0)]

result.write(w)

for k in compressed:

if k in dictionary:

entry = dictionary[k]

elif k == dict_size:

entry = w + w[0]

else:

raise ValueError(’Napaka pri kodiranju k: %s’ % k)

result.write(entry)



# Razˇ sirim slovar

dictionary[dict_size] = w + entry[0]

dict_size += 1



w = entry

print("Dekodirni slovar:", dictionary)

return result.getvalue()

Primer uporabe:

# Niz, ki ga kodiramo

input_string = "BITIALINEBITI"



# Pripravimo zaˇ cetna slovarja

char_to_num = {}

num_to_char = {}

count = 0



# Preletimo vhodni niz

for char in input_string:

if char not in char_to_num:

# ˇ Ce znak ni v slovarju, ga dodamo

char_to_num[char] = count

num_to_char[count] = char

count += 1



# Izpis zaˇ cetnih slovarjev

print("Kodirni slovar:", char_to_num)

print("Dekodirni slovar:", num_to_char)



# Kodiramo

compressed = kodiraj(input_string,char_to_num) print ("Kodirana vsebina:", compressed)

LZW (DE)KODIRANJE 125



# Dekodiramo

decompressed = dekodiraj(compressed,num_to_char) print ("Dekodirana vsebina:", decompressed)





DODATEK D




HUFFMANOVO KODIRANJE



# Razred za vozliˇ sˇ ce Huffmanovega drevesa

class Vozlisce:

def __init__(self, verjetnost, simbol, levo=None, desno=None):

self.verjetnost = verjetnost # verjetnost simbola self.simbol = simbol # znak (simbol)

self.levo = levo # levo poddrevo

self.desno = desno # desno poddrevo

self.koda = ’’ # dodeljena binarna koda



# Slovar za shranjevanje kod posameznih simbolov kode = dict()



def izracunaj_kode(drevo, trenutna_koda=’’):

"""

Rekurzivni sprehod po drevesu za doloˇ citev kod posameznih simbolov. """

nova_koda = trenutna_koda + str(drevo.koda)



if drevo.levo:

izracunaj_kode(drevo.levo, nova_koda)

if drevo.desno:

izracunaj_kode(drevo.desno, nova_koda)

M. Kunaver, Teorija informacij in izvorno kodiranje. 127

©2025 Zaloˇzba FE

128 HUFFMANOVO KODIRANJE



if not drevo.levo and not drevo.desno:

kode[drevo.simbol] = nova_koda



return kode



def prestej_frekvence(besedilo):

"""

Preˇ steje frekvence pojavitve posameznih simbolov. """

frekvence = dict()

for znak in besedilo:

frekvence[znak] = frekvence.get(znak, 0) + 1

return frekvence



def zakodiraj(besedilo, kodiranje):

"""

Zakodira besedilo s pomoˇ cjo slovarja kod.

"""

return ’’.join([kodiranje[znak] for znak in besedilo])



def izpisi_kompresijo(besedilo, kodiranje):

"""

Izpiˇ se ˇ stevilo bitov pred in po stiskanju.

"""

pred = len(besedilo) * 8

po = sum(besedilo.count(simbol) * len(koda) for simbol, koda in kodiranje.items()) print("Bitov pred stiskanjem:", pred)

print("Bitov po stiskanju:", po)



def huffmanovo_kodiranje(besedilo):

"""

Glavna funkcija za gradnjo Huffmanovega drevesa in kodiranje podatkov. Vrne: zakodirano besedilo in koren drevesa.

"""

frekvence = prestej_frekvence(besedilo)

vozlisca = [Vozlisce(frekvence[s], s) for s in frekvence]



while len(vozlisca) > 1:

vozlisca = sorted(vozlisca, key=lambda x: x.verjetnost) levo = vozlisca.pop(0)

desno = vozlisca.pop(0)



levo.koda = ’0’

desno.koda = ’1’



zdruzeno = Vozlisce(

levo.verjetnost + desno.verjetnost,

levo.simbol + desno.simbol,

HUFFMANOVO KODIRANJE 129



levo,

desno

)

vozlisca.append(zdruzeno)



drevo = vozlisca[0]

kodne_kombinacije = izracunaj_kode(drevo)

print("Kode simbolov:", kodne_kombinacije)

izpisi_kompresijo(besedilo, kodne_kombinacije) kodirano = zakodiraj(besedilo, kodne_kombinacije) return kodirano, drevo



def huffmanovo_dekodiranje(kodirano_besedilo, drevo):

"""

Dekodira besedilo na osnovi Huffmanovega drevesa. """

izhod = []

trenutni = drevo



for bit in kodirano_besedilo:

trenutni = trenutni.desno if bit == ’1’ else trenutni.levo



if not trenutni.levo and not trenutni.desno:

izhod.append(trenutni.simbol)

trenutni = drevo



return ’’.join(izhod)



# === TESTNI PRIMER ===

if __name__ == "__main__":

besedilo = "AAAAAAABCCCCCCDDEEEEE"

print("Izvirno besedilo:", besedilo)

kodirano, drevo = huffmanovo_kodiranje(besedilo) print("Kodirano besedilo:", kodirano)

print("Dekodirano besedilo:", huffmanovo_dekodiranje(kodirano, drevo))





VIRI




[1] Papoulis, A., Pillai, S. U. (2002). Probability, Random Variables, and Stochastic Processes,

McGraw-Hill.

[2] Cover, T. M., Thomas, J. A. (2006). Elements of Information Theory, 2nd ed., Wiley-

Interscience.

[3] MacKay, D. J. C. (2003). Information Theory, Inference and Learning Algorithms, Cambridge

University Press.

[4] Shannon, C. E. (1948). A Mathematical Theory of Communication, Bell System Technical

Journal.

[5] Tomaˇziˇc, S. (2002). Osnove telekomunikacij I, Zaloˇzba FE in FRI.

[6] Paveˇsiˇc, N. (2010). Informacija in kodi, Zaloˇzba FE in FRI.

[7] Haykin, S. (2009). Communication Systems, 5th ed., John Wiley & Sons, Inc., New York.



M. Kunaver, Teorija informacij in izvorno kodiranje. 131

©2025 Zaloˇzba FE

https://fides.fe.uni-lj.si/˜matevzk/Ucbeniki/

TIIK/TIIK_Kunaver.pdf