KYBERNETIKA A UMĚLÁ INTELIGENCE 3. Přenos informace
laboratory
Gerstner
Gerstnerova laboratoř katedra kybernetiky fakulta elektrotechnická ČVUT v Praze
Přenos informace
Uvažujme dvojice systémů: systém 1
systém 2
Stav: napětí U
Stav: úhelα
Stav: úhel α
Stav: úhel β
Stav: znak X
Stav: znak Y
Co mají dvojice společného? Stavy systému 1 a systému 2 jsou navzájem závislé. Je mezi nimi přenášena informace komunikačním kanálem. Ze stavu systému 1 lze odhadnout stav systému 2 a obráceně.
Komunikační kanál
Všechny tyto příklady lze společně zobecnit:
Systém 1 Veličina X
Komunikační kanál
Systém 2 Veličina Y
Pro jednoduchost: pouze jedna stavová proměnná v každém systému. X a Y jsou náhodné proměnné s distribucemi P(x), P(y) resp. hustotami f(x), f(y) tj. stochastický popis. Deterministický stav je speciálním případem! Uvažujme nejprve pouze diskrétní veličiny (tj. distribuce P(x), P(y) ). Vlastnosti komunikačního kanálu určují sílu vazby mezi X a Y. Jak ji měřit?
Jaká je neurčitost X, pokud víme, že Y = y ? Použijme koncept entropie X, kde místo P(x) uvažujeme podmíněnou distribuci P(x|y) :
H ( X | y ) = −∑ P ( x | y ) log 2 P ( x | y ) x
Entropie X podmíněná znalostí o konkrétní hodnotě Y = y
Pozn.: zjednodušenou notací
∞
∞
x = −∞
y = −∞
∑ , ∑, atd. značíme ∑ , ∑ atd. x
y
Podmíněná a sdružená entropie
Zobecnění pro všechny možné případy y
střední hodnota H(X,y) přes všechny y.
H ( X | Y ) = ∑ P( y ) H ( X | y ) = −∑ P( y )∑ P( x | y ) log 2 P( x | y ) y
y
x
Entropie X podmíněná Y H(X|Y) je tedy střední hodnota neurčitosti X při průběžném pozorování Y. Analogicky k pravděpodobnostním pojmům: H(X) a H(Y) = “marginální entropie”. Vedle marginální a podmíněné entropie, definujeme také sdruženou entropii:
H ( X , Y ) = −∑∑ P( x, y ) log 2 P ( x, y ) x
y
Sdružená entropie X a Y Celková neurčitost systému sestávajícího ze dvou systémů (se stavy X resp Y ). Platí
H ( X , Y ) = H ( X | Y ) + H (Y )
H(X,Y) = ∑∑ P( x, y ) log 2 P( x, y ) =∑∑ P( x | y ) P( y ) log 2 [ P( x | y ) P ( y )] = x
y
x
y
= ∑ P( y )∑ P( x | y ) log 2 P( x | y ) + ∑ P( y ) log 2 P( y )∑ P( x | y ) = H ( X | Y ) + H (Y ) ⋅1 y
x
y
x
Vlastnosti podmíněné entropie
H(X|Y), tj. neurčitost X podmíněná Y, je minimální, pokud je hodnota X jednoznačně určena z Y, tj. X=g(Y), kde g je nějaká funkce. Potom platí
X Y
a tedy H ( X | Y ) = −∑ P( y )∑ P( x | y ) log 2 P( x | y ) = −∑ P ( y )P( g ( y ) | y ) log 2 P ( g ( y ) | y ) = −∑ P( y ) ⋅1 ⋅ 0 = 0 y
x
y
y
H(X|Y) je maximální, pokud je hodnota X nezávislá na Y, tj. P(X|Y) = P(X).
X Y
Potom platí
H ( X | Y ) = −∑ P ( y )∑ P( x | y ) log 2 P( x | y ) = −∑ P( y )P( x) log 2 P( x) = ∑ P( y )H ( X ) = H ( X ) y
x
y
Víme tedy, že
0 ≤ H (X |Y) ≤ H (X )
y
Vzájemná informace
Informační vazbu mezi dvěma systémy pak kvantifikujeme jako rozdíl neurčitosti stavu X jednoho systému před a po zjištění hodnoty stavu Y druhého systému. Tedy
T (X :Y ) = H (X ) − H (X | Y )
„před“ „po“ T(X:Y) se nazývá vzájemná informace, též transmise (proto T ). Víme, že 0 ≤ H(X|Y) ≤ H(X). Platí tedy
0 ≤ T (X :Y ) ≤ H (X )
Dvojtečka vyjadřuje symetrii mezi systémy. Platí:
T ( X : Y ) = H ( X ) − H ( X | Y ) = H (Y ) − H (Y | X ) = T (Y : X )
Víme, že H(X|Y) = H(X,Y) – H(Y), dostáváme tedy:
T ( X : Y ) = H ( X ) + H (Y ) − H ( X , Y )
Příliš mnoho vztahů? Udělejme v tom pořádek!
Entropie a vzájemná informace – vztahy
Grafické znázornění Vennovým diagramem (plocha odpovídá hodnotě)
H(X)
H(X|Y)
H(Y)
T(X:Y) = T(Y:X)
H(X,Y) = H(Y,X)
H(Y|X)
Často kladené otázky
Přepokládejme diskrétní komunikační kanál. X – vysílaný znak, Y – přijímaný znak.
Zmatení 1: H(X) – entropie vysílacího systému („zdroje“) - je zároveň: neurčitost stavu (vysílaného znaku) zdroje. střední hodnota informace připadající na jeden vyslaný znak. Jak to, že množství informace stoupá s neurčitostí ?! Správná interpretace: Čím více je informace ve znacích vyslaných zdrojem, tím těžší je tyto znaky předvídat (vyšší neurčitost).
Zmatení 2: T(X:Y) – vzájemná informace, nejvyšší pro nejsilnější informační vazbu. T(X:Y) = H(X) čím více marginální informace, tím lépe (větší T), - H(X|Y) čím více podmíněné informace, tím hůře (menší T) ?! Správná interpretace: H(X) je střední míra informace produkované zdrojem – té chceme co nejvíce H(X|Y) je střední míra informace produkované šumem – té chceme co nejméně „šum“ – nedeterminismus vazby mezi X a Y. Pro X=g(Y): žádný šum, H(X|Y) = 0.
Vzájemné informace pro spojité stavové veličiny
Pro spojité náhodné veličiny X, Y zavádíme vzájemnou informaci analogicky diskrétním. Nechť f(x) a g(y) jsou hustoty X resp. Y a h(x,y) je jejich sdružená hustota. Vyjděme ze vztahu T(X:Y) = H(X,Y) – H(X) – H(Y) a dosaďme: ∞ ∞
T (X :Y ) =
∞
∫ ∫ h( x, y) log h( x, y)dxdy − ∫ f ( x) log 2
− ∞− ∞
−∞
T(X :Y ) =
∫ ∫ h( x, y) log h( x, y)dxdy − ∫ ∫ h( x, y)dy log 2
− ∞− ∞
−∞
∞ ∞ 2
f ( x)dx −
∫ ∫ h( x, y)dx log g ( y)dy 2
− ∞− ∞
Odtud sečtením: ∞ ∞
T (X :Y ) =
∫
∫ h ( x , y ) log 2
− ∞− ∞
f ( x) dx − ∫ g ( y ) log 2 g ( y )dy
∞ ∞
− ∞− ∞
2
přičemž prvním sčítancem jsme definovali sdruženou diferenciální entropii H(X,Y). Z principu marginalizace (minulá přednáška) vyplývá: ∞ ∞
∞
h( x, y ) dxdy f ( x) g ( y)
Zatímco marginální diferenciální entropie je závislá na měřítku veličiny (min. přednáška), vzájemná informace pro dvě spojité veličiny je na měřítku nezávislá. Dále se budeme věnovat diskrétním komunikačním kanálům.
Kódování
Uvažovali jsme zatím model
Zdroj
Komunikační kanál
Cíl
Vzájemná informace je symetrický vztah, ale pro názornost volíme orientaci: Informaci ve znacích vysílá zdroj signálu a přjímá cíl – příjemce signálu.
Komunikační kanál nemusí být schopný přenášet všechny stavy zdrojového systému. Příklad:
Zdroj/cíl: text v ASCII 128 možných stavů (znaků)
Binární komunikační kanál 2 možné stavy (úrovně napětí)
Je třeba převést znaky zdroje na posloupnosti znaků kanálu (a zpět) Kódování: transformace z kódu zdroje do jiného kódu.
Kódování Zdroj
Kodér
Komunikační kanál
Dekodér
Cíl
Obecněji: převod posloupností znaků - tzv. slov zdroje na slova znaků kanálu. Proč kódovat slova a ne jen individuální znaky? Uvidíme dále!
Formálně: kódování je zobrazení: k: {x1, x2 ..., xn }* → {y1, y2, ..., ym }*, kde x1, x2 ..., xn jsou možné stavy zdroje a cíle a y1, y2, ..., ym jsou možné stavy kanálu, v kontextu přenosu informace se těmto množinám stavů říká abecedy {...}* znamená množina všech posloupností znaků z množiny {...}. dekódování je inverzní zobrazení d = k-1, tj. d(k(p)) = p pro p ∈ {x1, x2 ..., xn }* Vám známý termín codec = coder + decoder.
Zjednodušení Dále budeme uvažovat pouze binární komunikační kanály, tj kódování k: {x1, x2 ..., xn }* → {0,1}*
Důležitá podmínka pro kódování: musíme být schopni jednoznačně dekódovat! Za jakých podmínek je toto možné?
Jednoznačnost dekódování
Příklad kódu 1: a → 00
b → 01
c → 10
d → 11
Kódování po jednotlivých znacích definuje i kód pro každou posloupnost zdroje. Pevný počet kódových znaků pro každý symbol zdroje. Jednoznačná dekódovatelnost. Např.: 00001100100001 → AADACAB
Příklad kódu 2: a → 0
b → 01
c → 10
d → 11
Proměnný počet kódových znaků pro jednotlivé symboly zdroje. K čemu by takové kódování mohlo být užitečné? Je-li a nejčastějším znakem, generuje krátké kódy. Např. zpráva aadacab z předchozího příkladu → 0011010001 10 znaků oproti 14 výše. ALE: Nejednoznačná dekódovatelnost. Např.: 0110 → ada, ale také 0110 → bc Důvod: kód pro a je prefixem (začátkem) kódu pro b.
Prefixové kódy
Pozorování: má-li být kód s proměnným počtem kódových znaků pro každý symbol zdroje jednoznačně dekódovatelný, nesmí být kód žádného znaku zdroje prefixem kódu jiného znaku zdroje.
Tuto vlastnost mají
Prefixové kódy. Ty lze znázornit stromovým grafem. Např:
kořen 0 list a
1 0
list b list c
Kód znaku: hodnoty hran na cestě od kořene k příslušnému listu. Tj.
1 0
1 list d
znak a b c d
→ → → →
Je Morseova abeceda prefixový kód? Pouze pokud se mezi možné znaky počítá mezera.
kód 0 10 110 111
Další využití kódování
Vhodnou volbou kódování můžeme zesílit informační vazbu mezi systémy, tj. zvýšit vzájemnou informaci. Strategie obecně: T(X:Y) = H(X) .... chceme zvýšit komprese dat .... chceme snížit opravy chyb H(X|Y)
Obojího se dosahuje kódováním. Je ale třeba rozlišit, „kde“ upravujeme T(X:Y) Komprese dat spočívá ve zvýšení H(X), je to tedy úprava vlastností zdroje
Vylepšená T(X:Y)
Vylepšený zdroj Zdroj
Kodér
X
Komunikační kanál
Vylepšený cíl Y
Dekodér
Cíl
Opravy chyb směřují ke snížení H(X|Y), jde o úpravu vlastností komunikačního kanálu
Vylepšená T(X:Y) Vylepšený komunikační kanál Zdroj
Kodér X
Komunikační kanál
Dekodér
Cíl Y
Komprese dat
Uvažujme znovu zdroj se čtyřmi stavy (znaky abecedy), s distribucí P(a) = 0.5 P(b) = 0.3 P(c) = 0.1 P(d) = 0.1
Kód k1: přiřazuje stejně dlouhý kód všem znakům zdroje a → 00
b → 01
c → 10
d → 11
Střední hodnota počtu bitů (znaků kódu) na jeden znak zdroje: L = 2.
Kód k2 (prefixový): přiřazuje nejkratší kód nejčastějšímu znaku zdroje a→0
b → 10
c → 110
d → 111
Střední hodnota počtu bitů (znaků kódu) na jeden znak zdroje: L = 0.5 * 1 + 0.3 * 2 + 0.1 * 3 + 0.1 * 3 = 1.7
Kód k2 tedy dosahuje 15% komprese oproti kódu k1 – zprávy v kódu k2 jsou v průměru od 15% kratší než v kódu k1. Otázky: Jaké nejlepší komprese můžeme dosáhnout ? Jakým algoritmem sestrojit příslušný kód ?
Entropie zdroje a komprese
Shannonova věta o kompresi:
H ( X ) ≤ L ≤ H ( X ) +1 Entropie zdroje udává nejnižší dosažitelný průměrný počet bitů na jeden znak zdroje L. Vždy jsme schopni dosáhnout hodnoty maximálně o 1 větší než je entropie zdroje. Předpokladem věty je vzájemná statistická nezávislost znaků zdroje, tedy: P(zm | zm-1,zm-2, ...) = P(zm), kde zi ∈ {x1, x2 ..., xn } je i-tý vyslaný znak
Z minulého příkladu:
P(a) = 0.5 P(c) = 0.1
P(b) = 0.3 P(d) = 0.1
Nejnižší možné L ≈ 1.68
H ( X ) = −0.5 log 2 0.5 − 0.3 log 2 0.3 − 0.1log 2 0.1 − 0.1 log 2 0.1 ≈ 1.68 Kódem k1 jsme dosáhli L = 2, kódem k2 jsme dosáhli L = 1.7
Redundance
Námitka: bez jakéhokoliv kódování bychom ale dosáhli L = 1 ?! Museli bychom použít 4 znaky abecedy, což s binárním kanálem nelze. L nelze srovnávat pro kódování s různými velikostmi abeced!
Ke srovnávání efektivity kódů s různými abecedami slouží pojem redundance r : r = 1−
H H [⋅100%] = 1 − [⋅100%] H max log 2 n
n je počet znaků abecedy použité v kódu (původním kódu zdroje, nebo výstupu kódování) H je entropie kódu Hmax je maximální možná entropie kódu, tj. log2 n.
Předpokladem výpočtu redundance je opět statistická nezávislost vysílaných znaků. Čím nižší redundance, tím vyšší efektivita. Komprese dosahujeme, pokud rzdroje > rkódu . Nejnižší možná redundance pokud H = Hmax. Lze dosáhnout pouze rovnoměrnou distribucí P znaků v kódu.
Redundace Z minulého příkladu:
Zdroj: H(X) = 1.68, n = 4, r = 1 – 1.68 / 2 = 16 % Kód k1: P(0) = 0.7, P(1) = 1-P(0) = 0.3 H ( X k1 ) = −0.7 log 2 0.7 − 0.3 log 2 0.3 ≈ 0.88 n = 2, r = 1 – 0.88 / 1 = 12 % Kód k2: P(0) = 0.53, P(1) = 1-P(0) = 0.47 H ( X k 1 ) ≈ −0.53 log 2 0.53 − 0.47 log 2 0.47 ≈ 0.99 n = 2, r = 1 – 0.99 / 1 = 1 % Pro výpočet redundance je předpokládána statistická nezávislost znaků. Pro k1 a k2 platí pouze přibližně! Proto rozdíl mezi zdrojem (16 %) a k1 (12 %). Výpočet P(0) v kódech k1 a k2
P(z) pro znak zdroje
a
a
a
a
a
b
b
b
c
d
k1
00
00
00
00
00
01
01
01
10
11
110
111
50%
P(0) v k1 k2 P(0) v k2
30%
10%
10%
počet nul / počet číslic = 14 / 20 = 0.7 0
0
0
0
0
10
10
10
počet nul / počet číslic = 9 / 17 = 0.53
Huffmanovo kódování znaků zdroje
Jak sestrojit kompresní prefixový kód: konstrukce Huffmanova stromu
Algoritmus: 1. Uzly := znaky zdroje Hrany := {} 2. Je-li právě jeden uzel, do kterého nevede hrana, skonči. 3. Z uzlů, do kterých nevedou hrany, vyber dva: u1, u2 s nejnižší P. Vytvoř nový uzel z něhož vedou hrany do u1 a do u2. Hrany označ 0 resp. 1. P(nového uzlu):= P(u1)+P(u2) 3. Jdi na 2.
David A. Huffman 1925 - 1999
Příklad: znak P(znak)
a b
0.2
c
0.2
d
0
0.5
0.1
0 0
0.3
0.5 1
1
Výsledný prefixový kód (totožný s k2) a → 0 b → 10 c → 110 d → 111
1
Huffmanovo kódování slov zdroje
Jak sestrojit Huffmanův kód, pokud je kód zdroje již binární? Příklad: znak P(znak) 0 0.7 1
0.3
0
0→0
1
1→1
1 bit je kódován 1 bitem. Výsledek standardního Huffmanova algoritmu je k ničemu.
Je třeba kódovat po n-ticích znaků, tj. slovech zdroje. Např. pro n = 2: Příklad: dvojice P(dvojice)
00
0.7*0.7=0.49
01
0.7*0.3=0.21
10
0.3*0.7=0.21
11
0.3*0.3=0.09
Výsledné kódování: 2 znaky pref. kód
0 0 0
0.3 1
0.51 1
1
00
→ 0
01
→ 10
10
→ 11
11
→ 111
Úspěšnost: 1.6 znaků na 2 znaky zdroje. L = 0.49 ⋅1 + 0.21 ⋅ 2 + 0.21 ⋅ 2 + 0.09 ⋅ 3 = 1.6 Techniku lze použít i pro nebinární zdroje. Pro rostoucí n se lze libovolně přiblížit maximální možné kompresi dané entropií zdroje, platí totiž: lim n→∞ L = H ( X ) Při nezávislosti znaků tedy neexistuje algoritmus s lepší bezeztrátovou kompresí než H.A.
Vzájemná závislost znaků
V minulé přednášce: entropie přirozeného jazyka H ≈ 4.1 Maximální entropie pro rovnoměrnou distribuci P všech 27 písmen: H ≈ 4.8 Tj. redundance r ≈ 1-4.1/4.8 ≈ 14%. Tak nízká redundance by připouštěla velmi malou možnost komprese. Přirozený jazyk lze ale komprimovat značně. V čem je tedy chyba? Přirozený jazyk není sekvence vzájemně nezávislých znaků! Jde o příklad systému, kde neplatí podmínka P(zm | zm-1,zm-2, ...) = P(zm) nezávislosti znaku na předešlých znacích.
Systémy se závislostí následných stavů lze modelovat Markovským modelem: M.m. řádu n je distribuce P(zm | zm-1,zm-2, ..., zm-n) – „stacionární“ - nezávislá na m a počáteční podmínka – distribuce P(z) Jde vlastně o model dynamiky stochastického systému (m lze chápat jako diskr. čas).
Příklad: M.m. pro binární systémy: binární abeceda zi ∈ {0,1}, řád n = 1 P(1|0) = 0.8
P(0|0) = 0.2
0
1
P(0) = 0.5
P(0) = 0.5
P(1|0) = 0.3
P(1|1) = 0.7
“stochastický automat“
Vzájemná závislost znaků
Pro přirozený jazyk: 27 stavů a 272 přechodů (pro řád 1). Konstrukce modelu: pravděpodobnostní distribuce nutno odhadnout ze skutečných textů. Náhodná simulace vývoje systému z M.m.: průchod stavy s náhodnými přechody dle pravděpodobností zadaných modelem. Příklady náhodných simulací z M.m. jazyků: řád 1, angličtina: OUCTIE IN ARE AMYST TE TUSE SOBE CTUSE... řád 2, angličtina:
HERE AREAT BEIS HEDE THAT WISHBOUT SEED DAY OFTE AND HE IS FOR THAT LOOTS WILL AND GIRLS DOLL WILL SAYS...
řád 3, francouzština: DU PARUT SE NE VIENNER PERDENT LA TET...
Neuspořádanost systému se závislostmi je dána
podmíněnou entropií řádu n:
H n ( Z m | Z m −1 , Z m − 2 ,..., Z m − n ) = ∑ ∑ ...∑ P ( z m −1 , z m − 2 ,..., z m − n ) H ( Z m | z m −1 , z m − 2 ,..., z m − n ) z m−1 z m−2
z m−n
H1(angličtina) ≈ 4.42, H15(angličtina) ≈ 2.1, H100(angličtina) ≈ 1.3 ... tím se rozpor vysvětluje!
Kompresní metody pro systémy se závislostní strukturou jsou mimo rámec KUI.
Detekce a opravy chyb
Komunikační kanál ovlivněn šumem, pokud H(X|Y) ≠ 0 ≠ H(Y|X). Nastávají chyby přenosu. Opakovaný kód: jednoduchá metoda rozpoznání chyb v přenosu. Příklad: Binární zdroj
Kódování 0 → 00 1 → 11
Binární kom. kanál
Dekódování 00 → 0 11 → 1 01, 10 → chyba!
Cíl
Pro n násobné opakování možno detekovat až n-1 chybných bitů v jednom slově. Při dostatečném n je ale možno již při dekódování chyby opravovat. Příklad pro n = 3: Dekodér přiřazuje došlé n-tici nejbližší Dekódování s opravou chyb přípustné slovo, ve smyslu Hammingovy 000, 001, 010, 100 → 0 vzdálenosti (tj. počtu rozdílných bitů). 111, 110, 101, 011 → 1 Při n násobném opakování lze opravit < n/2 chyb v jednom slově. Pozn.: n liché, jinak opravy nejednoznačné! Opravami chyb snižujeme nejednoznačnost přenosu, tedy H(X|Y). Zatímco kompresí jsme redundanci snižovali, opakováním ji zvyšujeme. Hádanka: Opravdu? Počítejme na příkladu: Zdroj X: P(0) = 0.5, P(1) = 0.5, tedy H(X) = 1 a r = 0% Opakovaný kód k: 0 → 00 1 → 11, tedy znovu P(0) = 0.5, P(1) = 0.5 a r = 0% Jak to, že se nezvýšila redundance r ? Vysvětlete!
Rekapitulace
Kódováním nyní umíme zvýšit T(X:Y) = H(X) – H(X|Y) na T(X*:Y*) buďto: Kompresí, tedy úpravou vlastností zdroje: H(X*) > H(X)
Zdroj
X
Kodér
X*
T(X*:Y*) Komunikační kanál
Y*
Dekodér
Y
Cíl
Opravou chyb, tedy úpravou vlastností kanálu: H(X*|Y*) < H(X|Y)
T(X*:Y*) Zdroj
X*
Kodér
X
Komunikační kanál
Y
Dekodér
Cíl Y*
Obě metody mohou být ale navzájem protichůdné: H(X) upravujeme změnou P(x). V důsledku symetrie T(X:Y) = H(X) – H(X|Y) = H(Y) – H(Y|X), kde H(Y|X) závisí na P(x). Úpravou zdroje tedy obecně ovlivňujeme i chybovost kanálu. Toto naštěstí neplatí v obvyklém případě tzv. symetrického kanálu (viz dále). Opravou chyb naopak zvyšujeme „redundanci“, přestože to náš model redundance nedokáže zachytit: vzhledem k statistické závislosti v opak. kódu platí H(X) = H(X*). Takto způsobenou redundanci můžeme ale formálně zachytit při výpočtu rychlosti přenosu informace (viz dále).
Rychlost a kapacita kanálu
Rychlost přenosu informace závisí na T(X:Y) a na fyzické rychlosti přenosu 1 bitu v:
R = v ⋅T ( X : Y )
[bit.s-1] („Redundanci“ v opakovaných kódech můžeme formálně zachytit snížením rychlosti přenosu jednoho bitu zdroje, tj. v* = v / n, neboť k jeho přenosu je vyslat n bitů skrz k.k.) Chceme-li popsat kvalitu samotného komunikačního kanálu, potřebujeme veličinu nezávislou na konkrétním zdroji a případné kompresi dat, tj nezávislou na distribuci P(x). Kapacita komunikačního kanálu je definována jako maximální rychlost přenosu informace přes všechny možné distribuce P(x) znaků zdroje:
C = v ⋅ max P ( X ) T ( X : Y )
[bit.s-1]
Pro kanál bez šumu: H(X|Y) = 0, tedy T(X:Y) = H(X) a C = v maxP(X) H(X) Kapacita kanálu bez šumu je tedy dána rychlostí přenosu maximálně komprimovaných dat (signálu). Kanál bez šumu nejlépe využijeme maximální kompresí kódu zdroje.
Kapacita binárního symetrického kanálu
Obecně je obtížné vypočítat maxP(X) T(X:Y). Častým případem v přenosu informace je binární symetrický kanál, kde je výpočet jednoduchý. Binární symetrický kanál: platí Pr(y = 0|x = 0) = Pr(y = 1|x = 1) = p Šum tedy stejnou měrou narušuje oba zdrojové znaky. Pravděpodobnost chyby = 1-p. Výpočet maxP(X) T(X:Y) = maxP(X) [H(X) –H(X | Y)] = maxP(X) [H(Y) –H(Y | X)] X=0 Y=0 p 1-p Pro H(Y | X) platí: H (Y | X ) = −∑ P( x)∑ P( y | x) log 2 P( y | x) = 1-p x
y
= −∑ P ( x)[ p log 2 p + (1 − p ) log 2 (1 − p )] = x
= −[ p log 2 p + (1 − p ) log 2 (1 − p )]∑ P( x) = x
= −[ p log 2 p + (1 − p ) log 2 (1 − p )]⋅1
H(X | Y) zde nezávisí na P(x) ani P(y) . H(Y) lze tedy maximalizovat zvlášť. Maximum H(Y) je log2 2 = 1. Kapacita je tedy: C = v [1 + p log2 p + (1-p) log2 (1-p)] Dosahuje maxima pro p = 1 i p = 0. Interpretujte!
X=1
p
Y=1
Souhrn přednášky
Stavy dvou různých systémů mohou být navzájem závislé v důsledku přenosu informace. Přenos informace modeluje kybernetika konceptem komunikačního kanálu. Vlastnosti komunikačního kanálu určují sílu informační vazby mezi dvěma systémy, která je kvantifikována hodnotou vzájemné informace T(X:Y). Vzájemná informace mezi náhodnými veličinami X a Y je rozdíl marginální entropie H(X) a podmíněné entropie H(X|Y). Při modelování přenosu informace obvykle jeden systém označujeme jako zdroj a druhý jako cíl (příjemce). Stavy jsou reprezentovány znaky, posloupnosti znaků jsou slova. Převod slov zdroje na slova přenositelná komunikačním kanálem zajišťuje kódování. Jednoznačně dekódovatelné jsou kódy s pevnou délkou slova a kódy prefixové. Vhodným kódováním je možno zlepšit informační vazbu mezi zdrojem: kompresí (např. použitím Huffmanova algoritmu) detekcí resp. opravou chyb přenosu (např. použitím opakovaného kódu) Maximální možná komprese (za předpokladu vzáj. nezávislosti vysílaných znaků) je určena entropií zdroje. Rychlost přenosu informace komunikačním kanálem je součinem vzájemné informace T(X:Y) a fyzické rychlosti přenosu jednoho bitu. Kapacita komunikačního kanálu je maximální možná rychlost přenosu informace přes všechny možné distribuce P(x) znaků zdroje.
