© Ernest 2004
5. Teorie informace 5.1 Informace a entropie • Kvantitativní vyjád ení množství informace ve zpráv . • Syntax versus sémantika (zde nás zajímá syntaktická ást). • D ležité pojmy: o Abeceda nap . {a,b,c,bd,cd}. o Zpráva (nap . aabcbdcda). o Symbol (prvek abecedy – nap . cd). Z dané abecedy lze sestavit jisté množství zpráv o stanovené délce. M jme zprávu o délce n sestavené z s symbol abecedy. Množství informace I ve zpráv bude rostoucí funkcí po tu možných zpráv N, kde platí N = sn , bude funkcí po tu t chto zpráv, tedy I = f(N). Uvažujme dv zprávy délek n1 a n2. Spojíme-li ob zprávy ve zprávu jedinou, potom celková informace s ohledem na požadavek aditivity musí být sou tem díl ích informací obou zpráv. Tedy
I = I1 + I 2 = f ( s n1 + n2 ) = f ( s n1 ) + f ( s n2 ) = = f ( N1.N 2 ) = f ( N1 ) + f ( N 2 )
.
Funkce, která by spl ovala p edcházející požadavek bude potom funkcí logaritmickou a lze ji napsat ve tvaru I = f(N) = K ln N = K n ln s. Tuto veli inu nazýváme Hartleyovou mírou informace a dosp l k ní poprvé v r. 1928 R. Hartley.
© Ernest 2004
Uvažujme dále absolutní výskyty symbol ve zpráv jako etnosti jednotlivých symbol n1, n2, ….., ns. Pro celkovou informaci I charakterizující množství informace lze napsat (Hartleyova míra informace 1928) s ni ni I = − K .n. ln , n i =1 n kde K je konstanta. Za p edpokladu, že zpráva bude dostate n dlouhá (n velké), m žeme relativní etnosti symbol považovat za pravd podobnosti, tedy
I = − K .n.
s
i =1
(Pi ln Pi ) ,
což je celkové množství informace obsažené ve zpráv délky n, jejíž symboly nejsou rovnom rn rozd leny, ale vyskytují se s pravd podobností Pi. Pod líme-li celkové množství informace I po tem symbol abecedy n, dostaneme st ední hodnotu informace p ipadající na jeden symbol zprávy s I H = = − K . (Pi ln Pi ) . n i =1
Tuto st ední hodnotu informace p ipadající na jeden symbol zprávy H nazval známý C.E. Shannon entropie (informa ní nebo shannonovská). Pro nejjednodušší možnou abecedu o dvou symbolech {0,1} ur íme hodnotu konstanty K tak, že položíme hodnotu informace této abecedy na jeden symbol rovno jedné. Za p edpokladu stejné pravd podobnosti výskytu obou symbol ve zpráv bude platit 1 I = K . ln 2 = 1, K = . ln 2 Potom pro informa ní entropii platí s 1 s H =− . (Pi ln Pi ) = − (Pi log 2 Pi ) , ln 2 i =1 i =1 a informaci m íme v jednotkách [bit – binary digit]. Jestliže konstantu K zvolíme rovnu jedné a použijeme p irozené logaritmy, m íme informaci v p irozených jednotkách [nat].
© Ernest 2004
P íklad:
Spo t te entropii „p i házení kostkou“, která má ísla: 2, 2, 4, 5, 5, 6. Pro jaká ísla na kostce by byla entropie maximální a pro jaká minimální?
5.2 Vlastnosti entropie P edpokládejme kone nou abecedu A = {a1, a2, ….., as} ze které je tvo ena zpráva, nebo že každému symbolu abecedy m žeme p i adit ur itou hodnotu signálu xi: xi ∈ X, X = { x1, x2, …. xs}. Dále p edpokládejme, že známe pravd podobnosti, s jakými se budou vyskytovat symboly abecedy P(ai), nebo hodnoty signálu P(xi). Pro informa ní entropii množiny hodnot signálu xi platí H(X ) = −
s i =1
(P( xi ) log 2 P( xi ) ) ,
Vlastnosti entropie lze potom shrnout jako: • H(X) = 0 tehdy a jen tehdy, jsou-li všechny pravd podobnosti krom jedné rovny nule a jedna pravd podobnost je rovna jedné. (Hodnota signálu, pro kterou je pravd podobnost rovna jedné, nastává s jistotou, není zde žádná neur itost.) • Jestliže jsou pravd podobnosti výskytu všech hodnot signálu stejné a platí 1 P( x1 ) = P( x2 ) = .... = P( xs ) = , s Potom dosahuje entropie svého maxima, což je H max ( X ) = log 2 s . • Sdružená entropie. Uvažujme dva signály xi ∈ X, X = { x1, x2, …. xs} a yj ∈ Y, Y = { y1, y2, …. yr}. Potom sdruženou entropii definujeme jako
© Ernest 2004
H ( X ,Y ) = −
s
r
i =1 j =1
P( xi , y j ) log 2 P( xi , y j ) ,
kde P(xi, yj) je sdružená pravd podobnost (pravd podobnost, že signál x nabývá hodnoty xi a zárove signál y nabývá hodnoty yj). Pro jednorozm rnou (marginální) entropii platí H(X ) = −
s
r
i =1 j =1
P( xi , y j ) log 2
r j =1
P( xi , y j ) .
Mezi sdruženou entropií a marginálními entropiemi platí nerovnost H ( X , Y ) ≤ H ( X ) + H (Y ) . • Pro entropii spojité veli iny platí vztah +∞
H ( X ) = − f ( x). log 2 f ( x).dx , −∞
kde f(x) je hustota pravd podobnosti spojité veli iny x.
5.3 Komunika ní kanál a kódování Strukturu komunika ního kanálu lze chápat jako n kolik ástí – zdroj informace, kódovací za ízení, které kóduje tuto informaci, samotný p enosový kanál, do kterého vstupuje šum a které p enáší samotnou zakódovanou informaci z místa poskytovatele informace (zdroj informace) do místa p íjemce informace. Dekódovací za ízení dekóduje zakódovanou zprávu na p vodní zdroj informace až k p íjemci informace. Podle typu p enosového kanálu lze komunika ní kanál d lit na • Spojitý komunika ní kanál • Diskrétní komunika ní kanál
© Ernest 2004
P i samotném procesu kódování informace se m ní množství symbol ve zpráv a m ní se i rozložení pravd podobnosti výskyt jednotlivých symbol . U n kterých kód je t eba více symbol k p enesení stejné zprávy než u jiných kód . Je tedy možné najít takový kód, který bude mít nejv tší entropii, tzn. nejmenší po et symbol na dané množství informace v p enášené zpráv . Takový kód potom vyžaduje nejkratší dobu p enosu informace daným kanálem. Mírou úspornosti kódování je pom rná entropie h definovaná vztahem H h= , H max kde H je entropie daného kódu a Hmax je maximální entropie. Pro optimální kód dosahuje hodnota pom rné entropie jedné. Nadbyte nost symbol v kódované zpráv lze vyjád it pomocí veli iny, kterou nazýváme redundance r a je definována jako r =1− h =
H max − H . H max
Redundance kódování vzniká jednak u zdroje informace a jednak kódováním, které ješt zhorší nerovnom rnost výskytu jednotlivých symbol ve zpráv . Pro redundanci zdroje bude platit H H0 rz = 1 − 0 = 1 − , H max log 2 s kde H0 je entropie zdroje a log2 s je maximální entropie zdroje. Dodate ná redundance zp sobená kódováním bude H rz = 1 − 1 , H0 kde H1 je entropie zakódované zprávy. Celkovou redundanci ur íme ze vztahu H1 rc = rz + rk − rz .rk = 1 − . log 2 s Jak již bylo e eno, výhodn jší kód z hlediska využití komunika ního kanálu by byl takový, kde by byl výskyt jednotlivých symbol se
© Ernest 2004
stejnou pravd podobností. Ale tato podmínka ješt nezaru í, že bude mít minimální redundanci. Kódy lze d lit podle délky kódových slov • Rovnom rné kódy (kódové slova stejn dlouhá – není problém se zjiš ování, kde kon í jedno a za íná druhé kódové slovo, ASCII tabulka) • Nerovnom rné kódy (délka kódových slov r zná, typickým p íkladem Morseova abeceda – používá t i symboly a to árku, te ku a mezeru, což zvyšuje redundanci) Je možné vytvo it takové kódy, kde žádné kódové slovo nebude za átkem jiného slova. Potom není t eba k odd lení kódových slov používat další redundantní symbol, p estože se bude jednat o nerovnom rné kódy. Takové kódy nazýváme jako kódy s prefixovou vlastností. Podle toho d líme dále kódy na • Kódy s prefixovou vlastností • Kódy bez prefixové vlastnosti O tom, zda má kód i nemá prefixovou vlastnost se lze snadno p esv d it pomocí znázorn ní kódu ve form stromového grafu. Každému uzlu grafu odpovídá kódové slovo tvo ené z jednotlivých hran od ko ene grafu k p íslušnému uzlu. Pokud jsou kódová slova uspo ádána tak, že žádné slovo neleží na cest od jiného slova ke ko enu grafu, má uvedený kód prefixovou vlastnost. P íklad
M jme dva kódy
symbol a b c d kód 1 00 01 10 11 kód 2 0 10 1101 0111 Ur ete který z kód je rovnom rný a má prefixovou vlastnost.
© Ernest 2004
P íklad
Nech zdroj generuje ty i nezávislé symboly a, b, c, d s pravd podobnostmi P(a) = 1/2, P(b) = 1/4, P(c) = P(d) = 1/8. M jme dva kódy symbol a b c d kód 1 00 01 10 11 kód 2 0 10 1101 0111 Spo t te entropii zdroje informace, redundanci zdroje informace a redundanci obou kód . Redundance a její vlastnosti
• s rostoucí redundancí se zvyšuje po et p enášených symbol ve zpráv , než za použití optimálního kódu • redundance má opodstatn ní v p ípad zarušení komunika ního kanálu nap . opakováním zprávy, nebo p idáním speciálních znak ke zpráv , které umožní chybu indikovat pop ípad opravit (paritní bit, CRC kód atd.) Dalším d ležitým pojmem u vlastností kód je tzv. Hammingova vzdálenost ρ(a,b) - po et míst, ve kterých se dv kódová slova A, B liší. Tato vzdálenost vyhovuje axiom m metriky, lze ji teda oprávn n považovat za vzdálenost.
© Ernest 2004
Pro nap . t íprvkový kód a jeho Hammingovu vzdálenost lze napsat ρ(000,001) = ρ(000,010) = ρ(000,100) = 1, ρ(000,011) = ρ(000,110) = 2, ρ(000,111) = 3. D ležitou vlastností Hammingovy vzdálenosti je, že charakterizuje odolnost kódu proti rušení a schopnost kódu chybu identifikovat, pop ípad opravit. Pro ρ = 1 (kód bez redundance) nelze identifikovat chybu, protože chybn p ijaté slovo bude odpovídat jinému kódovému slovu. Pro ρ = 2 je možné zjistit chybu v jednom ádu (paritní bit odhalí chybu v jednom bitu), pro ρ = 3 je možné zjistit chybu ve dvou ádech a opravit chybu v jednom ádu. Pro vícemístné kódy stanovíme Hamingovu vzdálenost tak, že se teme p íslušná kódová slova modulo 2 (logická nonekvivalence) a spo ítáme po et jedni ek v sou tu modulo 2. P íklad
Ur ete Hammingovu vzdálenost pro dv desetiprvková kódová slova a = 0 1 1 0 1 0 1 0 0 0 a b = 1 1 1 0 0 1 0 1 0 0.
5.4 St ední vzájemná informace Uvažujme dva signály xi ∈ X, X = { x1, x2, …. xs} a yj ∈ Y, Y = { y1, y2, …. yr}, které jsou ur itým zp sobem závislé. Neur itost výb ru hodnoty x za p edpokladu znalosti hodnoty y je dána podmín nou entropií H(X|Y). Zm na neur itosti ve výb ru hodnoty z X bez znalosti výb ru z Y a p i znalosti výb ru z Y bude dána H(X) − H(X|Y) = T(X:Y). Veli inu T(X:Y) nazýváme st ední vzájemnou informací (lze zobrazit pomocí Vennova diagramu). Vyjád íme-li podmín nou entropii pomocí sdružené, potom pro st ední vzájemnou informaci platí T(X:Y) = H(X) + H(Y) − H(X,Y).
© Ernest 2004
Vlastnosti st ední vzájemné informace
• • • •
Je nezáporná funkce: T(X:Y) ≥ 0 Je symetrická funkce svých argument : T(X:Y) = T(Y:X) Je rovna nule jsou-li x a y statisticky nezávislé veli iny. Platí-li T(X:Y) = min{H(X), H(Y)} pak jsou x a y vázány funk ní závislostí y = f(x), kde f(x) je monotónní funkce.
5.5 Diskrétní kanál a jeho kapacita Zprávu nech kódujeme pomocí kodéru vyjád enou v abeced zdroje informace na hodnoty signálu ui. Množinu p ípustných hodnot signálu ozna me U (ui ∈ U). Nech signál nabývá na výstupu komunika ního kanálu hodnoty yj (yj ∈ Y). Množina Y je množinou p ípustných hodnot výstupního signálu. V ideální p ípad by existovalo mezi hodnotami vstupního a výstupního signálu jednozna né zobrazení, v reálném komunika ním kanálu je ale signál ovliv ován šumem a rušením. Komunika ní kanál bude charakterizován pravd podobnostmi p ijetí yj za p edpokladu vyslání ui nebo pravd podobnostmi vyslání ui za p edpokladu p ijetí yj, i = 1, 2, ..., s, j = 1, 2, ...., r. Potom diskrétní kanál je popsán trojicí (U, Y, P(ui|yj)) nebo (U, Y, P(yj|ui)), kde P(ui|yj) a P(yj|ui) jsou matice podmín ných pravd podobností ve tvaru P( y1 | u1 ) P ( y2 | u1 ) .. .. P( yr | u1 ) P( y1 | u2 ) P( y2 | u2 ) .. .. P( yr | u2 ) P ( y j | ui ) = , .. .. .. .. .. .. .. P( y1 | u s ) P ( y2 | u s ) P(u1 | y1 ) P (u2 | y1 ) P(u1 | y2 ) P(u2 | y2 ) P(ui | y j ) = .. .. .. .. P(u1 | yr ) P(u2 | yr )
.. .. .. .. .. .. ..
.. .. .. .. .. .. ..
.. P ( yr | u s ) P(u s | y1 ) P(u s | y2 ) . .. .. P (u s | y r )
© Ernest 2004
K ohodnocení schopnosti kanálu p enášet informace je vhodná st ední vzájemná informace, tzn. informaci, kterou nese signál y o signálu u nebo signál u o signálu y T(U:Y) = H(U) − H(U|Y) = H(Y) − H(Y|U) = H(U) + H(Y) − H(U,Y). • H(U|Y) nebo H(Y|U) udává ztráty informace zp sobené p enosem komunika ním kanálem • platí-li H(U|Y) = H(Y|U) = 0, pak se jedná o komunika ní kanál bez šumu a rušení • z hlediska využití komunika ního kanálu nás zajímá rychlost p enosu R informace kanálem Pro rychlost p enosu informace R komunika ním kanálem platí [bit.s−1 ],
R = vu T(U:Y)
kde vu je rychlost p enosu jednotlivých symbol daného kódu, pro kterou platí 1 vu = ,
τu
kde τu je st ední doba p enosu jednoho symbolu zprávy (v p ípad , že symboly nemají stejnou délku). Rychlost vu je omezena fyzikálními vlastnostmi komunika ního kanálu, z hlediska kódování a teorie informace ji nelze ovlivnit. St ední vzájemná informace T(U:Y) závisí nejen na pravd podobnostech P(yj|ui) ale i na pravd podobnostech P(ui) (pravd podobnost P(ui) m níme vhodným kódováním). tedy zajímá nás tedy maximální rychlost p enosu, kterou m žeme dosáhnout vhodnou volbou kódu. Tuto maximální rychlost ozna ujeme jako kapacita kanálu C a platí
C = vu . max {T (U : Y )}, P (U )
kde maximum st ední vzájemné informace hledáme p es všechna možná rozložení pravd podobnosti P(U).
© Ernest 2004
Výpo et kapacity diskrétního kanálu se zna n zjednoduší, budou-li všechny ádky matice P(yj|ui), permutacemi ísel P1, P2, ...., Ps. Z toho plyne, že šum stejným zp sobem ovlivní p enos každého vstupního symbolu. Takový komunika ní kanál nazýváme symetrickým kanálem vzhledem ke vstupu. Bude-i stejný p edpoklad spln n i pro sloupce matice P(yj|ui), bude kanál symetrický i k výstupu a takový kanál nazýváme symetrický kanál. Pro s = r = 3 m že mít matice P(yj|ui) tvar P2 P( y j | ui ) = P1 P3
P3 P2 P1
P1 P3 . P2
Pro kapacitu symetrického kanálu platí (odvození [1]) C = vu log 2 r +
r
Pj log 2 Pj .
j =1
etným p ípadem symetrického kanálu je tzv. binární symetrický kanál, který na vstupu i výstupu kanálu rozlišuje pouze dv hodnoty 0 a 1. Vyslanou 0 nebo 1 p ijmeme s pravd podobností P, nesprávn p ijatou jedni ku p ijmeme jako nulu a naopak nesprávn p ijatou nulu p ijmeme jako jedni ku s pravd podobností 1 − P. Matice podmín ných pravd podobností P(yj|ui) bude mít tvar P ( y j | ui ) =
P
1− P
1− P
P
.
Kapacitu binárního symetrického kanálu tedy ur íme podle tedy
C = vu (log 2 2 + P log 2 P + (1 − P) log 2 (1 − P ) ), C = vu (1 + P log 2 P + (1 − P) log 2 (1 − P) ) .
© Ernest 2004
P íklad Ur ete kapacitu binárního symetrického kanálu s pravd podobností správného p enosu symbolu P = 0.3 a st ední rychlostí p enosu symbolu 1000 znak za sekundu. Shannonova v ta: Jestliže je entropie zdroje menší než kapacita kanálu, je možné najít takový kód, který by umožnil p enášet zprávy daným kanálem s libovoln malou pravd podobností chyby. V ta platí i obrácen - je-li entropie zdroje v tší než kapacita kanálu, není možné najít takový kód, který by umož oval p enášet tímto kanálem zprávy, které generuje zdroj tak, aby byla pravd podobnost chyby libovoln malá.
Úlohy 1. Spo t te entropii „p i házení kostkou“, která má ísla: 1, 2, 2, 2, 5, 6. 2. Nech zdroj generuje dva nezávislé symboly X a Y s pravd podobnostmi P(X) = 0.3 a P(Y) = 0.7. M jme dva kódy symbol kód 1 kód 2
X 0 01
Y 001 101
Spo t te entropii zdroje informace, redundanci zdroje informace a redundanci obou kód . Který z kód má v tší redundanci a jaký je význam této veli iny? Jaký z kód je prefixový a pro ? 3. Ur ete kapacitu binárního symetrického kanálu s pravd podobností P = 0.5 správného p enosu symbolu a st ední rychlostí p enosu symbolu vu = 1000 s-1.
© Ernest 2004
Použitá literatura [1] [2]
Kotek, Vysoký, Zdráhal, Kybernetika, SNTL, 1990. Stránky p edm tu – p ednášky http://gerstner.felk.cvut.cz.
