Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Teorie kódování - Kapitola 3 Komunikace kanály se šumem Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 26. dubna 2023 □ t3 Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Komunikační systém • Základní pojmy Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Fl Komunikační systém je mechamismus, který zprostředkovává přenos informace od zdroje zprávy až k zařízení, které tuto informaci zpracovává. Obecně sestává z kodéru, sdělovacího (komunikačního) kanálu a následně dekodéru. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Fl Komunikační systém je mechamismus, který zprostředkovává přenos informace od zdroje zprávy až k zařízení, které tuto informaci zpracovává. Obecně sestává z kodéru, sdělovacího (komunikačního) kanálu a následně dekodéru. vstup Kodér Komunikační kanál Dekodér výstup Obrázek 1: Blokový diagram obecného sdělovacího systému. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Fl Komunikační systém je mechamismus, který zprostředkovává přenos informace od zdroje zprávy až k zařízení, které tuto informaci zpracovává. Obecně sestává z kodéru, sdělovacího (komunikačního) kanálu a následně dekodéru. vstup Kodér Komunikační kanál Dekodér výstup Obrázek 1: Blokový diagram obecného sdělovacího systému. Zdrojová zpráva je obvykle v podobě sekvence binárních nebo desítkových číslic, nebo sekvence abecedních znaků převedených do technicky zpracovatelné pq^JDy^ = Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem vstup Kodér Komunikační kanál Dekodér výstup ^ Kódovací zařízení převádí tyto zprávy na signály kompatibilní se vstupem kanálu - obvykle se jedná o elektrické signály, které mají jistá omezení na velikost napětí, šířku pásma a délku trvání impulzu. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem vstup Kodér Komunikační Dekodér výstup ^ kanál Kódovací zařízení převádí tyto zprávy na signály kompatibilní se vstupem kanálu - obvykle se jedná o elektrické signály, které mají jistá omezení na velikost napětí, šířku pásma a délku trvání impulzu. Takto upravené pak vstupují do sdělovacího kanálu a jsou vystaveny šumu (tj. možnosti vzniku chyby). Výstup z kanálu vstupuje do dekodéru, jehož funkcí je rozhodnout, jakou podobu měla původní zdrojová zpráva, a tu pak přivést na výstup celého sdělovacího systému. «fl>«»><»> Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Většina komunikačních kanálů má konečnou kapacitu přenosu informace, tj. míru schopnosti přenášet informaci měřenou v bitech za sekundu nebo bitech na symbol. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Většina komunikačních kanálů má konečnou kapacitu přenosu informace, tj. míru schopnosti přenášet informaci měřenou v bitech za sekundu nebo bitech na symbol. Díky vynikající teoretické práci Shannona (r. 1948) se dá ukázat, že pokud je průměrná rychlost přenosu informace menší než kapacita kanálu, je možné vybrat množinu signálů (kódových slov) takovou, že pravděpodobnost výskytu chyby při dekódování bude libovolně malá. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Většina komunikačních kanálů má konečnou kapacitu přenosu informace, tj. míru schopnosti přenášet informaci měřenou v bitech za sekundu nebo bitech na symbol. Díky vynikající teoretické práci Shannona (r. 1948) se dá ukázat, že pokud je průměrná rychlost přenosu informace menší než kapacita kanálu, je možné vybrat množinu signálů (kódových slov) takovou, že pravděpodobnost výskytu chyby při dekódování bude libovolně malá. Nicméně jakkoliv je tato teorie mocná, výsledek nevypovídá nic o tom, jak tyto signály volit, ani zda je možné je pomocí současných technických prostředků konstruovat. Používání samoopravných kódů je pokusem výše uvedené dva problémy obejít. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Ovšem celý přenos informace od zdroje až po zpracování není tak jednoduchý, jak znázorňuje (obr.4). Sestává z komplexnějšího sdělovacího systému; jednu takovou možnost nabízí (obr.2). vstup Vstup-bin. Bin.-bin. Modulátor Převodník Kodér _j_ Komunikační kanál výstup B in.-výstup Převodník Bin.-bin. Dekodér Demodulator Obrázek 2: Konkrétní sdělovací systém. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Kodéry (převodníky) převádí znaky jedné abecedy na znaky abecedy jiné. Obvykle mají obě abecedy poměrně malou mohutnost - typický převod může být z desítkové do dvojkové soustavy. vstup Vstup-bin. Převodník Bin-bin Kodér Modulátor Komunikační kanál výstup Bin-výstup Převodník Bin-bin. Dekodér Demodulator Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Modulátor na vstupu přijímá jednotlivé znaky a ke každému znaku vytváří proudový impuls, který vstupuje do kanálu. Tato operace s každým znakem zvlášť je omezením při přenosu informace a způsobí tak ztrátu kapacity kanálu. vstup Vstup-bin. Převodník Bin-bin. Kodér Modulátor Komunikační kanál výstup Bin-výstup Převodník Bin-bin. Dekodér Demodulator Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Demodulator provádí inverzní operaci. Ke každému obdrženému impulsu hledá znak tak, aby pravděpodobnost přenosové chyby byla co nejmenší. A opět jako při modulaci, i zde individuální modulace způsobuje ztrátu kapacity. vstup Vstup-bin. Převodník Bin-bin. Kodér Modulátor Komunikační kanál výstup Bin-výstup Převodník Bin-bin. Dekodér Demodulator Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat De finice r-té rozšíření kanálu Obsah Q Diskrétní kanál bez paměti • Definice • r-té rozšíření kanálu Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Definice r-té rozšíření kanálu Fl Ve svém nejširším smyslu lze komunikační kanál považovat za černou skříňku, která akceptuje řetězce symbolů ze vstupní abecedy Z1 a vysílá řetězce symbolů z výstupní abecedy Z2. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Definice r-té rozšíření kanálu Fl Ve svém nejširším smyslu lze komunikační kanál považovat za černou skříňku, která akceptuje řetězce symbolů ze vstupní abecedy Z1 a vysílá řetězce symbolů z výstupní abecedy Z2. Můžeme zřejmě tvrdit jen málo o takovéto struktuře. Omezme pozornost na diskrétní kanál bez paměti, který je charakterizován vstupní abecedou Z1 = {a-i,..., am}, výstupní abecedou Z2 = {£>i,..., bn} a maticí P kanálu ( P11 021 P = P12 P22 P^n-^ 02n-1 Pm-\\ Pm-\2 \ PmA Pm2 P^n Pln \ Pa77— 1 /i— 1 Pm-\n Pmn-\ P m n ) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Definice r-té rozšíření kanálu Způsob používání kanálu je následující: každá posloupnost , l/2, ..., un) symbolů ze vstupní abecedy Z-i na vstupu se převede na posloupnost (v-i, v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = ai) = Pij (1 < / < m, 1 > —>> Dekódovací zařízení Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Budeme předpokládat, že zakódování do binárního kódu proběhne bez šumu a že způsob zakódování je znám dekódovacímu zařízení. Předpokládejme pro jednoduchost, že N = 8; za symboly můžeme považovat např. písmena abecedy, různé měny nebo cokoliv jiného. Efektivní (tj. kompaktní) zakódování ve smyslu předchozího odstavce je pak S1 s2 s3 s4 s5 s6 Sy s8 1 r v 000 100 010 001 110 101 011 111. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Zpráva je řetězec zdrojových slov s/5 která jsou postupně zakódovaná, přenesená a pak dekódovaná. Tudíž, dle výše uvedeného kódovacího schématu, je pravděpodobnost, že jisté slovo je správně přeneseno, rovna q3. Pravděpodobnost, že zpráva o n slovech je korektně přenesena, je q3n. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Zpráva je řetězec zdrojových slov s/5 která jsou postupně zakódovaná, přenesená a pak dekódovaná. Tudíž, dle výše uvedeného kódovacího schématu, je pravděpodobnost, že jisté slovo je správně přeneseno, rovna q3. Pravděpodobnost, že zpráva o n slovech je korektně přenesena, je q3n. Lze to provést lépe? Odpověď je samozřejmě ano, jinak bychom se vůbec neptali. Zajímavé otázky jsou (a) jak moc lépe a (b) na čí náklady? Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Příklady Příklad 3.1 Uvažme výše uvedený příklad s osmi stejně pravděpodobnými zdrojovými slovy a předpokládejme, že použijeme zdvojené zakódování následovně: se s, » 000000 100100 010010 001001 110110 101101 011011 111111 Pokud dekódovací zařízení prijme pravidlo, že bude pouze dekódovat v případě, že první tři symboly a druhé tři symboly jsou totožné, a jinak "zavolá o pomoc", pravděpodobnost, že se vyskytne chyba a zůstane neobjevena, se drasticky redukuje. Zajisté budeme platit podstatnou cenu tím, že jsme snížili poměr přenosu faktorem 2. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Příklady Příklad 3.1 (Pokračování) Navíc se jedná o čistě detekční systém, který nebude využitelný v případě, že se dekódovací zařízení nemůže kontaktovat s kódovacím zařízením a požádat ho o znovuposlání slova, u kterého byla detekována chyba. Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Příklad 3.1 (Pokračování) Navíc se jedná o čistě detekční systém, který nebude využitelný v případě, že se dekódovací zařízení nemůže kontaktovat s kódovacím zařízením a požádat ho o znovuposlání slova, u kterého byla detekována chyba. Zbývající část této kapitoly je věnována způsobu získání dostatečné míry přenosu kanálu se šumem bez příliš velkého prodloužení zprávy Komunikační systém Kapacita jako hranice Diskrétni kanál bez paměti Dekódovací pravidla Zpracování dat Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Cvičení 3.2 Jednoduchý způsob detekování nejvýše jedné chyby je použít zařízení přidávajícího kontrolu parity, abychom měli zajištěno, že součet čísel v přenášeném slově je sudý. Tedy kontrola parity z výše uvedeného příkladu má tvar S1 s2 s3 s4 S5 s6 S7 s8 1 r 1 r ir 0000 1001 0101 0011 1100 1010 0110 1111. Ukažte, že jestliže přeneseme kód s kontrolou parity binárním symetrickým kanálem, pravděpodobnost, že není objevena chyba, je rovna 6p2(1 - p)2 + p4, kde p je pravděpodobnost výskytu chyby při přenosu kanálem. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost • Hammingova vzdálenost Q Kódování a dekódovací pravidla • Dekódování • Optimalizace Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Fl Buď dán kanál bez paměti se vstupní abecedou Z1 = {a-i,..., am} a výstupní abecedou Z2 = {ď-i ,..., bk}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze Z1. Prvky z C se nazývají kódová slova. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Fl Buď dán kanál bez paměti se vstupní abecedou Z1 = {a-i,..., am} a výstupní abecedou Z2 = {ď-i ,..., bk}- Kód délky n je libovolný systém C různých posloupností délky n symbolů ze Z1. Prvky z C se nazývají kódová slova. Je-li dán kód C délky n s kódovými slovy Ci, c2,..., c a/, dekódovací pravidlo je libovolný rozklad množiny možných obdržených posloupností do disjunktních množin fí-i, f?2j • • • j Rn se zřejmou interpretací toho, že je-li obdržená posloupnost y prvkem množiny Rj, je y dekódováno jako kódové slovo c Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce ř:I^Cu{?}. Aplikaci dekódovacího pravidla nazýváme dekódování. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce ř:I^Cu{?}. Aplikaci dekódovacího pravidla nazýváme dekódování. Je-li y (obdržené) slovo v ZÍJ, pak rozhodovací pravidlo dekóduje y jakožto kódové slovo f(y) nebo v opačném případě nahlásí dekódovací chybu, jestliže f(y) =?. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Formálně vzato, předpokládáme-li, že kód C neobsahuje např. symbol "?"jakožto kódové slovo, rozhodovací (dekódovací) pravidlo pro kód C je funkce ř:I^Cu{?}. Aplikaci dekódovacího pravidla nazýváme dekódování. Je-li y (obdržené) slovo v ZÍJ, pak rozhodovací pravidlo dekóduje y jakožto kódové slovo ř(y) nebo v opačném případě nahlásí dekódovací chybu, jestliže ř(y) =?. Výběr dekódovacího pravidla je podstatný k úspěchu každého komunikačního systému. Jako extrémní příklad je snadné zkonstruovat dekódovací pravidlo, které zcela zničí bezchybnost kanálu bez šumu. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Příklad - dekódovací pravidla Příklad 4.1 Předpokládejme, že máme zdroj s právě dvěma zdrojovými slovy s-i as2, který můžeme zakódovat pro přenos binárním symetrickým kanálem jako s-i i y 000 = c-i, s2 h> 111 = c2. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Příklad - dekódovací pravidla Příklad 4.1 Předpokládejme, že máme zdroj s právě dvěma zdrojovými slovy s-i as2, který můžeme zakódovat pro přenos binárním symetrickým kanálem jako s-i i y 000 = c-i, s2 h> 111 = c2. Máme pak osm možných obdržených zpráv Možné dekódovací pravidlo by mohlo být dekódovat zprávu jako s-i, pokud obsahuje více nul než jedniček. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Příklad - dekódovací pravidla Příklad 4.1 Předpokládejme, že máme zdroj s právě dvěma zdrojovými slovy s-i as2, který můžeme zakódovat pro přenos binárním symetrickým kanálem jako s-i i y 000 = c-i, s2 h> 111 = c2. Máme pak osm možných obdržených zpráv Možné dekódovací pravidlo by mohlo být dekódovat zprávu jako s-i, pokud obsahuje více nul než jedniček. Méně citlivé pravidlo by mohlo být dekódovat zprávu jako s-i, pouze když obdržená zpráva byla 000. A priori, každé z těchto pravidel má stejnou váhu, i s pravidlem: dekódujte každé obdržené slovo iako Si / Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Naší snahou bude najít dekódovací pravidlo, které maximalizuje pravděpodobnost správného dekódování tj. pravděpodobnost, že x = ř(y) je opravdu to kódové slovo c, které bylo odesláno. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Naší snahou bude najít dekódovací pravidlo, které maximalizuje pravděpodobnost správného dekódování tj. pravděpodobnost, že x = ř(y) je opravdu to kódové slovo c, které bylo odesláno. Poznamenejme, že příjemce nemá žádnou možnost zjistit, zdali dekódovací proces opravdu dekódoval správně. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Naší snahou bude najít dekódovací pravidlo, které maximalizuje pravděpodobnost správného dekódování tj. pravděpodobnost, že x = ř(y) je opravdu to kódové slovo c, které bylo odesláno. Poznamenejme, že příjemce nemá žádnou možnost zjistit, zdali dekódovací proces opravdu dekódoval správně. Pravděpodobnost správného dekódování lze vyjádřit mnoha způsoby. Použijeme-li například formuli úplné pravděpodobnosti, obdržíme následující dva vztahy: P(správné dekódování) = ^ P(správné dekódování|c odesláno)P(c odesláno), (4.1) vztahujeme-li podmínku na množinu kódových slov resp. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování timalizace Hammingova vzdále nost P(správné dekódování) = ^ P(správné dekódování|y obdrženo)P(y obdrženo), (4.2) vztahujeme-li podmínku na množinu slov ze Z?. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost P(správné dekódování) = ^ P(správné dekódování|y obdrženo)P(y obdrženo), (4.2) vztahujeme-li podmínku na množinu slov ze ZÍJ. Poznamenejme, že vztah (4.1) explicitně obsahuje pravděpodobnosti P(c odesláno), že různá kódová slova byla poslána pomocí kanálu. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost P(správné dekódování) = ^ P(správné dekódování|y obdrženo)P(y obdrženo), (4.2) vztahujeme-li podmínku na množinu slov ze ZÍJ. Poznamenejme, že vztah (4.1) explicitně obsahuje pravděpodobnosti P(c odesláno), že různá kódová slova byla poslána pomocí kanálu. Tyto pravděpodobnosti nejsou nic jiného než pravděpodobnosti zdroje C. Mluvíme pak o vstupním rozdělení kanálu. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost P(správné dekódování) = ^ P(správné dekódování|y obdrženo)P(y obdrženo), (4.2) vztahujeme-li podmínku na množinu slov ze ZÍJ. Poznamenejme, že vztah (4.1) explicitně obsahuje pravděpodobnosti P(c odesláno), že různá kódová slova byla poslána pomocí kanálu. Tyto pravděpodobnosti nejsou nic jiného než pravděpodobnosti zdroje C. Mluvíme pak o vstupním rozdělení kanálu. Přitom (4.2) rovněž obsahuje vstupní rozdělení, protože pravděpodobnost, že dané slovo y je obdrženo, obvykle závisí na tom, které kódové slovo bylo odesláno. = Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Nechť f je dekódovací pravidlo pro kód C. Je-li odesláno kódové slovo c, pak správné dekódování nastane právě tehdy, když f(y) = c pro obdržené slovo y. Platí tedy P(správné dekódování|c odesláno) = ^ P(y obdrženo|c odesláno). (4.3) yezg,/(y)=c Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Nechť f je dekódovací pravidlo pro kód C. Je-li odesláno kódové slovo c, pak správné dekódování nastane právě tehdy, když ř(y) = c pro obdržené slovo y. Platí tedy P(správné dekódování|c odesláno) = ^ P(y obdrženo|c odesláno). (4.3) yezg,/(y)=c Provedeme-li substituci do (4.1), obdržíme P(správné dekódování) = ^ P(y obdrženo|c odesláno)P(c odesláno). ceC,yeEg,/(y)=c (4.4) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Tato dvojnásobná suma není však vždy zcela příhodná. Přitom vztah (4.2) nám podává vhodnější návod, jak obdržet dobré dekódovací pravidlo. □ t3 Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Tato dvojnásobná suma není však vždy zcela příhodná. Přitom vztah (4.2) nám podává vhodnější návod, jak obdržet dobré dekódovací pravidlo. Podle dekódovacího pravidla f je obdržené slovo y dekódováno správně, jestliže odeslané slovo bylo ř(y). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Tato dvojnásobná suma není však vždy zcela příhodná. Přitom vztah (4.2) nám podává vhodnější návod, jak obdržet dobré dekódovací pravidlo. Podle dekódovacího pravidla f je obdržené slovo y dekódováno správně, jestliže odeslané slovo bylo ř(y). Platí tedy P(správné dekódování| y obdrženo)=P(f(y) odesláno| y obdrženo) (4.5) a přitom se ve výše uvedeném výrazu nevyskytuje žádná suma. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Dosaďme do vztahu (4.2). Pak máme P(správné dekódování) = ^ P(f(y) odesláno|y obdrženo)P(y obdrženo). (4.6) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Dekódovací pravidla Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Dosaďme do vztahu (4.2). Pak máme P(správné dekódování) = ^ P(f(y) odesláno|y obdrženo)P(y obdrženo). (4.6) Pravděpodobnost správného kódování lze maximalizovat tím, že budeme postupovat podle takového dekódovacího pravidla, které maximalizuje každou z podmíněných pravděpodobností P(ř(y) odesláno|y obdrženo). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Jinak řečeno, za předpokladu, že jsme obdrželi y, rozhodneme se tak, že kódové slovo, které bylo posláno, je to nepravděpodobnější, které mohlo být odesláno. To jde konkrétně zajistit tak, že se procházíme zpětnými kanálovými pravděpodobnostmi P(ci odesláno|y obdrženo),..., P(c/v odesláno|y obdrženo) a vybereme kódové slovo c, s největší pravděpodobností. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Jinak řečeno, za předpokladu, že jsme obdrželi y, rozhodneme se tak, že kódové slovo, které bylo posláno, je to nepravděpodobnější, které mohlo být odesláno. To jde konkrétně zajistit tak, že se procházíme zpětnými kanálovými pravděpodobnostmi P(ci odesláno|y obdrženo),..., P(c/v odesláno|y obdrženo) a vybereme kódové slovo c, s největší pravděpodobností. Toto pravidlo se nazývá pravidlo ideálního pozorovatele neboli pravidlo minimální chyby. Nicméně, přepis těchto podmíněných pravděpodobností nám ukazuje, že tyto podmíněné pravděpodobnosti nelze použít bez znalosti pravděpodobností výskytu kódových slov cy. Máme totiž podle Bayesovy věty: , „ P(y obdrženolc odesláno)P(c odesláno) P(c odeslano|y obdrženo) = ——----• Z)ř=i ^(y obdrženo^ odesláno)P(c/( odesláno) (4.7) Nicméně, přepis těchto podmíněných pravděpodobností nám ukazuje, že tyto podmíněné pravděpodobnosti nelze použít bez znalosti pravděpodobností výskytu kódových slov cy. Máme totiž podle Bayesovy věty: , „ P(y obdrženolc odesláno)P(c odesláno) P(c odeslano|y obdrženo) = ——----• Z)ř=i ^(y obdrženo^ odesláno)P(c/( odesláno) (4.7) V praxi je to vážná nevýhoda. Totiž, abychom určili dekódovací funkci, musíme znát, s jakou pravděpodobností jsou kódová slova posílána pomocí kanálu, tj. musíme znát jistou informaci o zprávě, což není zrovna vždy možné. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pravidlo maximální pravděpodobnosti Toto, společně se skutečností, že není snadné toto pravidlo aplikovat v případě, kdy máme velký počet kódových slov, opravňuje užití následujícího pravidla nazývaného pravidlem maximální pravděpodobnosti {maximum-likelihood (ML)). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pravidlo maximální pravděpodobnosti Toto, společně se skutečností, že není snadné toto pravidlo aplikovat v případě, kdy máme velký počet kódových slov, opravňuje užití následujícího pravidla nazývaného pravidlem maximální pravděpodobnosti {maximum-likelihood (ML)). Toto pravidlo dekóduje každý obdržený vektor y do kódového slova Cy tak, že maximalizuje P(y obdrženo|Cy odesláno). Pro ty, kteří jsou obeznámeni s odhady maximální pravděpodobnosti ve statistice, je analogie zřejmá. (4.8) Za předpokladu nedostatku informace o pravděpodobnostech různých kódových slov máme následující: Mají-li kódová slova stejnou pravděpodobnost, pak pravidlo maximální pravděpodobnosti splývá s pravi- (4.9) dlem ideálního pozorovatele. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování timalizace Hammingova vzdále nost Za předpokladu nedostatku informace o pravděpodobnostech různých kódových slov máme následující: Mají-li kódová slova stejnou pravděpodobnost, pak pravidlo maximální pravděpodobnosti splývá s pravi- (4.9) dlem ideálního pozorovatele. Důkaz je snadný. Totiž platí P(c odesláno) = ^. Tedy platí dle (4.7) P(C odesiénoly obdrženo) = ^^S.cľoSno,- <" °> Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování timalizace Hammingova vzdále nost Za předpokladu nedostatku informace o pravděpodobnostech různých kódových slov máme následující: Mají-li kódová slova stejnou pravděpodobnost, pak pravidlo maximální pravděpodobnosti splývá s pravi- (4.9) dlem ideálního pozorovatele. Důkaz je snadný. Totiž platí P(c odesláno) = ^. Tedy platí dle (4.7) P(C odesiénoly obdrženo) = ^^S.cľoSno,- <" °> Odtud pak máme, že maximum na pravé straně obdržíme právě tehdy, když budeme mít maximum na levé^traně. ^ ^ ^ Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost V hlavní části této přednášky budeme pracovat s binárním symetrickým kanálem. Pro tento kanál má pravidlo maximální pravděpodobnosti obzvlášť snadnou implementaci. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost V hlavní části této přednášky budeme pracovat s binárním symetrickým kanálem. Pro tento kanál má pravidlo maximální pravděpodobnosti obzvlášť snadnou implementaci. Nechť Vn označuje množinu všech posloupností délky n složených z nul a jedniček a, pokud to bude nutné, považujme Vn za vektorový n-dimenzionální prostor nad tělesem celých čísel modulo 2. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost V hlavní části této přednášky budeme pracovat s binárním symetrickým kanálem. Pro tento kanál má pravidlo maximální pravděpodobnosti obzvlášť snadnou implementaci. Nechť Vn označuje množinu všech posloupností délky n složených z nul a jedniček a, pokud to bude nutné, považujme Vn za vektorový n-dimenzionální prostor nad tělesem celých čísel modulo 2. Jsou-li x a y vektory z Vn, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pro binární symetrický kanál je přirozeným dekódovacím pravidlem pravidlo minimální vzdálenosti, totiž: dekódujme každý obdržený vektor y do kódového slova Cy, které má minimální Hammingovu vzdálenost od y: pokud je vícero takových slov, vybereme Cy libovolně. P(y obdrženo|cy odesláno). (4.11) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pro binární symetrický kanál je přirozeným dekódovacím pravidlem pravidlo minimální vzdálenosti, totiž: dekódujme každý obdržený vektor y do kódového slova Cy, které má minimální Hammingovu vzdálenost od y: pokud je vícero takových slov, vybereme Cy libovolně. P(y obdrženo|cy odesláno). (4.11) Následující snadný výsledek nám tvrdí: Věta 4.2 Pro binární symetrický kanál s pravděpodobností chyby p<\ je dekódovací pravidlo minimální vzdálenosti ekvivalentní k pravidlu maximální pravděpodobnosti. i Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Důkaz Věty 4.2 Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pro všechny vektory x a y z Vn s vlastností oř(x, y) = d platí P(y bylo obdrženo|x bylo odesláno) = p°q d „n-d Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Důkaz Věty 4.2 Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pro všechny vektory x a y z Vn s vlastností oř(x, y) = d platí P(y bylo obdrženo|x bylo odesláno) = p°q d„n-d Pokud p < \, tento výraz nabývá maxima, je-li d minimální. To ale zřejmě stačí k tomu, že pevné slovo y dekódujeme jako to kódové slovo, které má nejmenší vzdálenost od slova y. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Důkaz Věty 4.2 Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Pro všechny vektory x a y z Vn s vlastností oř(x, y) = d platí P(y bylo obdrženo|x bylo odesláno) = p°q d„n-d Pokud p < \, tento výraz nabývá maxima, je-li d minimální. To ale zřejmě stačí k tomu, že pevné slovo y dekódujeme jako to kódové slovo, které má nejmenší vzdálenost od slova y. Obráceně, vezmeme-li jako rozkódování pevného slova y kódové slovo minimální vzdálenosti, je výše uvedená pravděpodobnost maximální. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Dekódování Optimalizace Hammingova vzdálenost Cvičení 4.3 O Nechť kód sestává ze čtyř kódových slov c-i = 1000, c2 = 0110, c3 = 0001 a c4 = 1111. Pravděpodobnosti výskytu těchto kódových slov jsou dány jako P(d) = P(c2) = l P(c3) = P(c4) = l Používáte-li pro přenos binární symetrický kanál s pravděpodobnosti chyby ^ a obdržíte na výstup vektor 1001, jak by jste se rozhodoval při O použití pravidla ideálního pozorovatele, O použitím pravidla maximální pravděpodobnosti? i Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření • Základní pojmy • Binární symetrický kanál • r-té rozšíření m X _ .__"j. _ ■ O Kapacita kanálu Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Fl Jak už napovídá jméno, kapacita komunikačního kanálu je míra jeho schopnosti přenášet informaci. Formální definice je motivována níže uvedeným: Předpokládejme, že máme diskrétní kanál bez paměti se vstupní abecedou Z1 = {a-i,..., am}, výstupní abecedou $Z2 = ,..., bn} a maticí P kanálu p = [p7y] = p(by obdrženo a, odesláno). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Fl Jak už napovídá jméno, kapacita komunikačního kanálu je míra jeho schopnosti přenášet informaci. Formální definice je motivována níže uvedeným: Předpokládejme, že máme diskrétní kanál bez paměti se vstupní abecedou Z1 = {a-i,..., am}, výstupní abecedou $Z2 = ,..., bn} a maticí P kanálu p = [p7y] = p(by- obdrženo|a, odesláno). Přidáme-li k tomuto kanálu zdroj S bez paměti, který vysílá symboly a^,..., am s pravděpodobnostmi p-i,..., pm, pak výstup kanálu můžeme považovat za zdroj J bez paměti. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat lákladní pojmy Binární symetrický kanál r-té rozšíření Ten vysílá symboly £>i,..., bn s pravděpodobnostmi q^,..., qn kde q. = Y,T^ obdrženo|a, odesláno)P(a, odesláno) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Ten vysílá symboly ,..., bn s pravděpodobnostmi q1 ,..., qn, kde q. = YjT=-\ ^(by obdrženo|a, odesláno)P(a, odesláno) Informace o S podaná pomocí J, definovaná v kapitole 1, je rovna l{S\J) = H{S) - H{S\J) = H(S) + H{J) - H{S, J) a je to funkce, která závisí pouze na pravděpodobnostním rozdělení Pí,... ,pm, a matici kanálu P. Je proto přirozené definovat kapacitu C kanálu jako C = sup l{S\J), (5.1) kde supremum je bráno přes všechny zdroje bez paměti S, nebo, ještě přesněji, nad všemi možnými rozděleními pravděpodobností (p-i,..., pn). i Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Nejdříve si připomeňme, že C je dobře definováno v tom smyslu, že pouze hledáme supremum funkce ř(p), kde f je spojitá funkce na uzavřené a ohraničené podmnožině množiny Rm a dle základní věty analýzy má f maximum v nějakém bodě. Můžeme tedy 5.1 přepsat jako C = max l{S\J), (5.2) Dále si uvědomme, že C je kvantitativní veličina určená pouze maticí kanálu P. Můžeme ji zhruba považovat za konduktanci (vodivost) odporu v teorii elektrických obvodů. Její jednotky jsou pak jednotky informace nebo entropie, totiž "bity za sekundu" nebo "bity na symbol" v závislosti na kontextu. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Kapacita binárního symetrického kanálu Ukažme příklad, jak lze najít kapacitu kanálu. Věta 5.1 Kapacita binárního symetrického kanálu s pravděpodobností chyby přenosu p je určena vztahem C(p) = 1 +plogp + QlogQ; (5.3) kde q = 1 - p. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Důkaz. K usnadnění označení předpokládejme, že zdroj S emituje 0 s pravděpodobností a a 1 s pravděpodobností (3 = 1 — a. Pak výstup J má rozdělení 0 s pravděpodobností aq + (3p, 1 s pravděpodobností (3q + ap. Je tedy H(S, J) právě entropie rozdělení (aq, ap, (3q, (3q). Po jednoduché úpravě l{S\J) = p\ogp + q\ogq-(aq + (3p)\og(aq + (3p) -(ap + Pq) \og(ap + f3q) Derivujme dle a. Pak obdržíme, že l(S\ J) má maximum v případě, že a — t> a obdržíme pak 5.3. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Poznamenejme, že kapacita má očekávané vlastnosti - C(p) je monotónní funkce p, 0 < p < \, a C(0) = 1, C(1) = 0, což odpovídá intuici, že, pokud p = \, kanál se stane dokonalým rušičem, ale že, pokud p = 0, máme dokonalý přenos. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Poznamenejme, že kapacita má očekávané vlastnosti - C(p) je monotónní funkce p, 0 < p < \, a C(0) = 1, C(1) = 0, což odpovídá intuici, že, pokud p = \, kanál se stane dokonalým rušičem, ale že, pokud p = 0, máme dokonalý přenos. Zjištění kapacity obecných kanálů je netriviální záležitost. V případě, že kanál nemá nějakou speciální vlastnost nebo není odvozen z kanálu, jehož kapacita je známa, jediný způsob, jak můžeme vypočítat kapacitu, je vyřešení problému optimalizace s omezeními, a to zejména metodou Lagrangeových multiplikátorů. < a ► kapacitu r—tého rozšíření tak, že CM = supxH(X) - H(X|Y), (5.4) kde X = (X\,..., Xr) a Y = (Y-\,..., Yr) jsou vstupní a výstupní dvojice. Máme ale H(x) - H(X|Y) = H(Y) - H(Y|X). (5.5) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Důkaz Věty 5.2 Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Pokračování důkazu. Zároveň H(Y|X) = J]p(x)H(Y|X = x) Protože se jedná o kanál bez paměti, máme H(Y|X = x) = £ H(V/|X = x) = £ H(Y,\X, = x,) Zejména W(Y|X)=Exp(x)H(y/|X/ = x/) =E/EwH(V7|X/ = i;)-P(X/ = i;) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Základní pojmy Binární symetrický kanál r-té rozšíření Důkaz Věty 5.2 Pokračování důkazu. Tedy r H(v\x) = Y,H(Yi\Xi). (5.6) Obecně platí H(Y) e. Předpokládejme proto, že máme binární symetrický kanál s pravděpodobností chyby p a tudíž kapacitou C určenou C=C(p) = 1 +plogp + (1 -p)log(1 -p). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Dokažme následující verzi Shannonovy věty. Theorem 6.1 Shannonova věta o kódování se šumem Buď dán binární symetrický kanál kapacity C a libovolné R, 0 < R < C. Pak pro každou posloupnost (Mn : 1 < n < oc) přirozených čísel splňujících 1 < Mn < 2Rn (1 < n < oc), a všechna kladná e > 0, existuje posloupnost kódů (Cn : 1 < n < oc) a přirozené číslo N0(e) tak, že Cn má Mn kódových slov délky n a maximální pravděpodobnost chyby ě{Cn) < e pro všechna n > N0(e). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Jakým způsobem funguje tato věta. Předpokládejme, že pravděpodobnost chyby takovéhoto kanálu je taková, že kapacita kanálu C(p) = 0.8. Pak, je-li naše zpráva řetězec nul a jedniček, víme, že pro dostatečně velké n, položíme-li R = 0.75, existuje množina 2a75n kódových slov délky n, která mají pravděpodobnost chyby menší než libovolně předem předepsaná hranice. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Jakým způsobem funguje tato věta. Předpokládejme, že pravděpodobnost chyby takovéhoto kanálu je taková, že kapacita kanálu C(p) = 0.8. Pak, je-li naše zpráva řetězec nul a jedniček, víme, že pro dostatečně velké n, položíme-li R = 0.75, existuje množina 2a75n kódových slov délky n, která mají pravděpodobnost chyby menší než libovolně předem předepsaná hranice. Tudíž, abychom zakódovali zprávu ze zdroje, postup je následující: (a) Rozdělte zprávu do bloků délky m, přičemž m je takové, že 3\%]=m>N0(e). (b) Zakódujte každý z těchto m-bloků do kódu Cn tak, že použijete kódové slovo délky ^ pro každý m-blok. (b) Přeneste nově zakódovanou posloupnost kanálem. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Čeho jsme dosáhli? Podstatné redukce pravděpodobnosti chyby. Na čí náklady? Komplexnosti zakódování a menší míry přenosu: zároveň však bohužel doposud neznámé zakódování. Síla Shannonovy věty spočívá v tom, že existují takovéto kódy. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Čeho jsme dosáhli? Podstatné redukce pravděpodobnosti chyby. Na čí náklady? Komplexnosti zakódování a menší míry přenosu: zároveň však bohužel doposud neznámé zakódování. Síla Shannonovy věty spočívá v tom, že existují takovéto kódy. MA Důkaz Shannonovy věty, který chceme provést níže, závisí na dvou nerovnostech - z nich první je velmi dobře známa - její důkaz lze najít v každém elementárním textu z teorie pravděpodobnosti. Čebyševova nerovnost Je-li X libovolná náhodná proměnná tak, že má konečnou variaci (odchylku) var(X) = D(X), pak pro každé a > 0 máme P(\X-E(X)\ >a)< D{X)/a2. (6.1) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Druhá nerovnost je méně známá a má rovněž pravděpodobnostní interpretaci; lze ji vyslovit následovně. Omezená nerovnost Pro všechna A, 0 < A < \, platí £ (nk)<2nh(x), k=0 V 7 kde h(A) = -[A log A + (1 - A)log(1 - A)]. Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Důkaz Omezené nerovnosti Kapacita jako hranice Zpracování dat Položme m = [Xn\. Platí < 1. Tedy pro 0 < k < m < Xn máme A Xn 1 - A < A m 1 - A < A 1 - A < 1 Pak můžeme psát 1=[A + (1-A)]" > Em k= n o A*(1-A) = (1-A)"£?= 0 n k n-k X 1-A > AAn(1_A)n(1-A)Eľ=o^ 10 0,0- Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Důkaz Omezené nerovnosti Pokračování. Tudíž J2(nk) < AA"(1 -A)"(1"A)=2"h(A\ k=0 ^ ' logaritmujeme-li při základu 2 a pak znovu umocníme. I Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Důkaz věty o kódování se šumem Kapacita jako hranice Zpracování dat Nejprve popišme hrubý směr důkazu. Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Důkaz věty o kódování se šumem Kapacita jako hranice Zpracování dat Nejprve popišme hrubý směr důkazu. Zvolme si pevné přirozené číslo n, a pro daný okamžik, pracujme s binárními kódy ve Vn. Předpokládejme, že se pokoušíme najít kód s M kódovými slovy c, e Vn. Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Důkaz věty o kódování se šumem Kapacita jako hranice Zpracování dat Nejprve popišme hrubý směr důkazu. Zvolme si pevné přirozené číslo n, a pro daný okamžik, pracujme s binárními kódy ve Vn. Předpokládejme, že se pokoušíme najít kód s M kódovými slovy c, e Vn. Vybereme ta kódová slova c, trochu bláznivou metodou vybráním vektorů z Vn náhodně a nezávisle na /, (1 < / < M). Tomuto kódování říkáme náhodné kódování. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Důkaz věty o kódování se šumem Důkaz Věty 6.1 Nejprve popišme hrubý směr důkazu. Zvolme si pevné přirozené číslo n, a pro daný okamžik, pracujme s binárními kódy ve Vn. Předpokládejme, že se pokoušíme najít kód s M kódovými slovy c, e Vn. Vybereme ta kódová slova c, trochu bláznivou metodou vybráním vektorů z Vn náhodně a nezávisle na /, (1 < / < M). Tomuto kódování říkáme náhodné kódování. Budeme kódovat následujícím způsobem: zvolme r > 0 a nechť Sr(y) definuje r-sféruse středem y, tj. Sr(y) = {z:zg Vn,oř(y,z) r (b) oř(c, Y) < r a oř(ď, Y) < r pro nějaké jiné kódové slovo c'. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Označme po řadě Aa B události popsané (a) a (b). Pak E = A U B a tudíž P(E) = P{A U6)< P(A) + P(B). Uvažme událost B. Ta nastane, pokud platí zároveň (i) Ne více než r chyb nastalo při přenosu, (ii) jedno z kódových slov různých od c je ve vzdálenosti nejvýše r od obdrženého vektoru Y. I Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Pokračování důkazu věty o kódování se šumem Kapacita jako hranice Zpracování dat Označíme-li po řadě tyto události B| a B2, máme pak, protože B=B\n B2, P(B) < P(B2). (6.3) Uvažme nyní B2\ protože kódová slova jsou vybrána náhodně, pravděpodobnost, že c, má vzdálenost menší nebo rovnu r od Y je Nr{rí)/2n, kde Nr(") = £ ( £ ) <6-4) k=0 V J je počet vektorů z Vm které leží v Sr(y). I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Tudíž pravděpodobnost, že alespoň jedno ze zbývajících M - 1 kódových slov (různých od c) má vzdálenost menší nebo rovnu r od obdrženého slova Y splňuje (6.5) /c=0 Položme tudíž, pro všechna e > 0 r = [np + ne jakožto maximální celé číslo ne větší než np + ne. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Obdržíme pak z 6.3, 6.4, 6.5 a omezené nerovnosti, že (6 Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Obdržíme pak z 6.3, 6.4, 6.5 a omezené nerovnosti, že (6.6) Věnujme se nyní druhému typu chyb způsobenému jevem A Poznamenejme, že, je-li U (náhodný) počet chybných symbolů vzniklých při přenosu kódového slova c, pak máme P(A) = P(U> r) a U je náhodná proměnná s binomiálním rozdělením s parametry n a p. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Pokračování důkazu věty o kódování se šumem — Důkaz Věty 6.1. _ Tudíž P(A) = P{U > np + ns) < P(\U- np\ > ne) < D(U)/rfe2, dle Cebyševovy nerovnosti. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Pokračování důkazu věty o kódování se šumem — Důkaz Věty 6.1. _ Tudíž P(A) = P{U > np + ne) < P(\U - np\ > ne) dle Cebyševovy nerovnosti. Protože U je náhodná proměnná s binomiálním rozdělením, máme D(U) = npq a tedy úplná pravděpodobnost chyby je p(E) < W + M2-n[1-/7(p+s)] ne2 pro dostatečně velká n. I Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Pokračování důkazu věty o kódování se šumem Kapacita jako hranice Zpracování dat Protože kapacita C(p + e) = 1 - h(p + e), máme pak P(E)<^ + M2-nC^+£). ne* Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Pokračování důkazu věty o kódování se šumem Kapacita jako hranice Zpracování dat Protože kapacita C(p + e) = 1 - h{p + s), máme pak P(E) < EU* + M2-nC{p+e) ne2 Protože e > 0, lze pravděpodobnost chyby zvolit libovolně malou pro dostatečně velké n, za předpokladu, že M jakožto funkce n, neroste rychleji než 2nC(p\ Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Pokračování důkazu věty o kódování se šumem Kapacita jako hranice Zpracování dat Protože kapacita C(p + e) = 1 - h(p + e), máme pak P(E) < EU* + M2-nC{p+e) ne2 Protože e > 0, lze pravděpodobnost chyby zvolit libovolně malou pro dostatečně velké n, za předpokladu, že M jakožto funkce n, neroste rychleji než 2nC(p\ Dokázali jsme tedy větu o kódování se šumem až na to, že jsme omezili průměrnou pravděpodobnost chyby a ne maximální pravděpodobnost chyby. K dokončení důkazu potřebujeme dokázat, že existují kódy Cn s Mn kódovými slovy, kde Mn < 2Rn a mající maximální pravděpodobnost chyby < e. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Pokračování důkazu věty o kódování se šumem — Důkaz Věty 6.1. _ Položme proto e1 = \e a M'n = 2Mn. Poznamenejme, že protože Mn < 2Rn a R < C, musí existovat R' tak, že R < R' < C, a N'0 tak, že pro všechna n>N'0 platí M'n < 2nRr a tudíž existuje posloupnost kódů C'n tak, že C'n má M'n kódových slov a průměrnou pravděpodobnost chyby < e' pro n> A/q. Jsou-li x-i,..., xM/ kódová slova z C'm znamená to, že - V P(£|X/) = V P(£|x/) • P(x/) = P(£) < ^ n /=1 /=1 Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Tedy alespoň polovina těchto kódových slov x, musí splňovat P(E|X/) < 2e' = e. (6.7) Buď Cn kód sestávající z Mn kódových slov splňujících 6.7; pak máme náš požadovaný kód s maximální pravděpodobností < e. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta ani se šumem Důkaz Věty 6.1. Tedy alespoň polovina těchto kódových slov x, musí splňovat P(E|X/) < 2e' = e. (6.7) Buď Cn kód sestávající z Mn kódových slov splňujících 6.7; pak máme náš požadovaný kód s maximální pravděpodobností < e. I Shannonovu větu lze rozšířit i pro obecné kanály bez paměti s libovolnou vstupní a výstupní abecedou. Hlavní myšlenka důkazu se nemění, totiž (a) zakódujme zprávy náhodně, (a) dekódujme procedurou maximální pravděpodobnosti. _ Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta I Zesílení věty o kódování se šumem Technické obtíže jsou způsobeny zejména obecným tvarem kapacity kanálu, pokud se nejedná o symetrický kanál. Případný zájemce může najít úplný důkaz (ve skutečnosti dva) pro tuto obecnou situaci v článku Ashe (1965) nebo Gallagera (1968). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta I Zesílení věty o kódování se šumem Technické obtíže jsou způsobeny zejména obecným tvarem kapacity kanálu, pokud se nejedná o symetrický kanál. Případný zájemce může najít úplný důkaz (ve skutečnosti dva) pro tuto obecnou situaci v článku Ashe (1965) nebo Gallagera (1968). Měli bychom se též zmínit o důležitosti zlepšení hranic pravděpodobnosti vzniku chyby. V našem důkazu nahoře nás pouze zajímalo to, že pravděpodobnost nastání chyby lze dosáhnout libovolně malou. K tomuto problému existuje bohatá a dostatečně technická literatura. Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat hannonova věta Například následující silnější výsledek uvedený bez důkazu přináleží Shannonovi (1957). Věta 6.2 Buď dán diskrétní kanál bez paměti kapacity C a libovolné R, 0 < R < C. Pak existuje posloupnost kódů (Cn ■ 1 < n < oo) tak, že: (a) Cn má [2Rn\ kódových slov délky n (b) maximální pravděpodobnost chyby ě(Cn) kódování Cn splňuje ě{Cn) < Ae~Bn, přičemž A a B závisí pouze na kanálu a na R. Jinak řečeno, neexistují pouze dobré kódy, ale navíc existují kódy, jejichž pravděpodobnost chyby klesá egpoipnciálně^ t Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Shannonova věta Věta o kódování se šumem - Cvičení Cvičení 6.3 O Binární symetrický kanál mající pravděpodobnost chyby přenosu p = 0.05 může přenést 800 binárních číslic za sekundu. Kolik bitů může přenést bez chyby za sekundu? O Binární symetrický kanál s fyzikální kapacitou přenosu 800 číslic za sekundu může přenést 500 číslic za sekundu s libovolně malou pravděpodobností chyby. Co nám to vypovídá o pravděpodobnosti chyby tohoto kanálu? Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Kapacita kanálu I I L«l I III \Cc*t k"\ Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Kapacita jako hranice spolehlivé komunikace Fl Předpokládejme, že máme diskrétní kanál bez paměti o kapacitě C bitů. Předpokládejme, že tento kanál má mechanickou rychlost jednoho bitu za sekundu. Dokážeme nyní obrácení Shannonovy věty tím, že ukážeme nemožnost přenosu přesné informace rychlostí vyšší nebo rovné než je C bitů za sekundu. Přesněji, dokážeme následující základní výsledek. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Kapacita jako hranice spolehlivé komunikace Věta 7.1 Pro kanál bez paměti o kapacitě C a pro každé R > C neexistuje posloupnost kódů (Cn ■ 1 < n < oo) tak, že: O Cn má 2Rn kódových slov délky n, O pravděpodobnost chyby e(Cn) kódováníCn konverguje k nule pro n —ř oc. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Kapacita jako hranice spolehlivé komunikace Věta 7.1 Pro kanál bez paměti o kapacitě C a pro každé R > C neexistuje posloupnost kódů (Cn ■ 1 < n < oo) tak, že: O Cn má 2Rn kódových slov délky n, O pravděpodobnost chyby e(Cn) kódováníCn konverguje k nule pro n —ř oc. Ve skutečnosti Wolfowitz v roce 1961 dokázal mnohem silnější výsledek-totiž, za stejných podmínek, maximální pravděpodobnost chyby konverguje k 1 pro n -> oc. My však ukážeme slabší verzi, abychom dokázali, že Shannonova věta je nejlepší možná. Pro důkaz věty potřebujeme následující Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Kapacita jako hranice spolehlivé komunikace Lemma 7.2 Buď U, V, W náhodné vektory. Pak platí H(U|V) < H(U|V,W) + H(W) Důkaz. Máme dle základní identity, že H(U|V) = < H(U,V)-H(V) W(U,V,W) - H(W|U,V) - W(V) H(U,W|V), protože entropie je nezáporná. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat I Nemožnost přenosu Kapacita jako hranice spolehlivé komunikace Pokračování důkazu Lemmatu 7.2. Ale zároveň I H(U,W|V) = H(U,V,W)-H(V,W) + H(V,W)-H(V) I = H(U|V,W) + H(W|V) I < H(U|V,W) + H(W), I což se mělo dokázat. I_I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Fanova nerovnost Lemma 7.3 Fanova nerovnost Buď C kód s M kódovými slovy {c-i,..., cM} pro daný kanál bez paměti. Buď X náhodný vektor nabývající hodnoty v množině kódových slov. Nechť Y obsahuje náhodný vektorový výstup, v případě, že X je přeneseno kanálem a dekódováno. Pak, je-li pe pravděpodobnost chyby (totiž pE = P(X ^ Y)), máme H(X|Y) < H(pE, qE) + pE log (M - 1), (7.1) kde Qe = 1 - pE. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Fanova nerovnost Důkaz Lemmatu 7.3. Definujme novou náhodnou proměnnou Z jakožto Z = 0 pokudX = Y 1 pokud X ^ Y. Je tedy speciálně entropie náhodné proměnné Z rovna W(Pe, Qe)- Uvažme nyní uspořádanou dvojici (Y,Z). Zřejmě pak H(X|(Y,Z) = (y,0)) = 0. Zároveň, pokud (Y, Z) = (y, 1), je náhodná proměnná X rozložena mezi (M - 1) kódovými slovy, která nejsou rovna y. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Fanova nerovnost Pokračování důkazu Lemmatu 7.3. Zejména tedy H(X|(Y,Z) = (y,1)) 0, máme H(X) = n{C + e). Totiž \Cn\ = 2Rn a vždy jde najít n-rozměrný náhodný vektor X s příslušným rovnoměrným rozdělením pravdědobnosti. Protože kapacita kanálu je C, máme pak pro kódová slova délky n, že odpovídající kapacita rozšíření bez paměti je nC a tedy, označíme-li Y náhodný vektor výstupu odpovídající vstupnímu náhodnému vektoru X, máme nerovnost H(X) - H(X|Y) < nC, takže ne = n(C + e)- nC < H(X|Y). (3 ~ = t OOvO Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Nemožnost přenosu Důkaz Věty 7.1 - pokračování Aplikujeme-li Fanovu nerovnost, pak z toho, že máme dle předpokladu 2n(c+£) kódových slov, je ne < H(X|Y) < H(pE, qE)+pE log (M - 1) < H(pE, qE)+pEn(C+e) tj- ne - H(pE, qE) , n n(C + e) ~Pe- Necháme-li n konvergovat k nekonečnu, pak zcela jistě pE nekonverguje k nule. Tedy takováto posloupnost kódů Cn nemůže existovat. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Věta o Kódování se šumem l l l ■ r l "l Q Nerovnost při zpracování ' dat • Markovův řetězec o Nerovnost Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Nerovnost při zpracování dat může být použita k prokázání, že žádná chytrá manipulace s daty nemůže zlepšit závěry, které lze získat z dat. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Nerovnost při zpracování dat může být použita k prokázání, že žádná chytrá manipulace s daty nemůže zlepšit závěry, které lze získat z dat. Řekneme, že náhodné proměnné X, Y a Z tvoří Markovův řetězec v tomto pořadí (označený X Y Z), pokud podmíněné rozdělení Z závisí pouze na Y a je podmíněně nezávislé na X. Přesněji, X,Y a Z tvoří Markovův řetězec X Y Z, pokud lze zapsat sdruženou pravděpodobnostní funkci jakožto p(x,y,z) =p(x)p(y|x)p(z|y). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.1 Q X Y Z právě tehdy, když X a Z jsou podmínečně nezávislé za podmínky Y. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.1 Q X Y Z právě tehdy, když X a Z jsou podmínečně nezávislé za podmínky Y. Q X ^ Y Z právě tehdy, když Z ^ Y^X. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.1 Q> X ->■ Y ->■ Z právě tehdy, když X a Z jsou podmínečně nezávislé za podmínky Y. O X^Y^Z právě tehdy, když Z -? Y ^ X. Q Pokud Z = f(Y), pakX Y -> Z. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Lemma 8.1 Q X -> Y -> Z právě tehdy, když X a Z jsou podmínečně nezávislé za podmínky Y. O X^Y^Z právě tehdy, když Z -? Y ^ X. Q Pokud Z = f(Y), pakX Y -> Z. Důkaz. (i) Nechť X ->• Y Z. Pak , p(x,y,z) p(x,y)p(z\y) p(x,z\y) = = ; . = p(x\y)p(z\y) P(y) p(y) Obráceně máme p(x,y) = p(x)p(y\x) a p(x,y,z) = p(x,z|y)p(y) = p(x\y)p(z\y)p{y) = p{x,y)p{z\y). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Důkaz. (ii) Plyne bezprostředně z (i), protože máme p(z,x\y)=p(z\y)p(x\y). (iii) Je zřejmé, protože p(z\y) = 1 pokud z = f{y) 0 jinak. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Důkaz. (ii) Plyne bezprostředně z (i), protože máme p(z,x\y)=p(z\y)p(x\y). (iii) Je zřejmé, protože p(z\y) = 1 pokud z = f{y) 0 jinak. Nyní dokážeme důležitou a užitečnou větu, která demonstruje, že žádné zpracování Y, deterministické nebo náhodné, nemůže zvýšit informaci, kterou Y obsahuje o X. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Data processing inequality Vg, H{ u) > H( g( u) ) Unfolded >h >h >h *h >h >h =-h - 1 ^0 o, O Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.2 Buď U, V, W náhodné proměnné. Pak Q l(U\V) = l(V\U) = H(U, V) - H{U\V) - H{V\U), Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Lemma 8.2 Buď U, V, W náhodné proměnné. Pak Q l(U\V) = l(V\U) = H(U, V) - H{U\V) - H{V\U), Q H(U, V\W) = H(V\W) + H(U\ V, W). Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Lemma 8.2 Buď U, V, W náhodné proměnné. Pak Q l(U\V) = l(V\U) = H(U, V) - H{U\V) - H{V\U), Q H(U, V\W) = H(V\W) + H(U\ V, W). Důkaz. H{U, V) - H{U\V) - H{V\U) = = H(U, V) - [H(U, V) - H(V)] - [H(U, V) - H(U)] = H(U) + H (V) - H(U, V) = l(U\V) = l(V\U), H(V\W) + H{U\V, W) = = [H(V, W) - H(W)] + [H(U, V, W) - H{V, W)\ = H(U, V, W) - H(W) = H{U, V\W). Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.3 Buď X, Y, Z náhodné proměnné. Pak následující podmínky jsou ekvivalentní: Q X -> Y -> Z, Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.3 Buď X, Y, Z náhodné proměnné. Pak následující podmínky jsou ekvivalentní: Q X^Y^Z, O H(X,Z\Y = y) = H{X\Y = y) + H(Z\ Y = y), pokud P(Y = y)>0, Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Lemma 8.3 Buď X, Y, Z náhodné proměnné. Pak následující podmínky jsou ekvivalentní: O H(X,Z\Y = y) = H{X\Y = y) + H(Z\ Y = y), pokud P(Y = y)>0, O H(X,Z\Y) = H(X\Y) + H(Z\Y), Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Lemma 8.3 Buď X, Y, Z náhodné proměnné. Pak následující podmínky jsou ekvivalentní: Q X^Y^Z, O H(X,Z\Y = y) = H{X\Y = y) + H(Z\ Y = y), pokud P(Y = y)>0, O H(X,Z\Y) = H(X\Y) + H(Z\Y), # H(X\Y,Z) = H{X\Y). Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost Důkaz. Protože H(X, Z\ Y) = Ep(y=y)>o P(Y = VMX, A Y = /)■ H(X\ Y) = EPiY=y)>o P(Y = Y)H{X\ Y = y)a H(Z\ Y) = Ep(y=y)>o P(Y = y)H(Z\ Y = y), a zároveň H(X,Z\Y = y)< H(X\Y = y) + H(Z\Y = y) pro P(V = y) > 0, je nutně podmínka (ii) ekvivalentní s (iii). Dále H(X, Z\ Y) = H(X\ Y) + H{Z\ Y) právě tehdy, když H(X, Y,Z) -H(Y)= [H(X, Y) - H(Y)j + [h(Z, Y) - H(Y) právě tehdy, když H(X, Y,Z) - H(Y,Z) = H(X, Y) - H(Y) právě tehdy, když H(X\ Y, Z) = H(X\ Y). Tedy podmínka (iv) je ekvivalentní s (iii). I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Nechť tedy platí (i) a P{Y = y) > 0. Pak jsou náhodné proměnné X\Y = y a Z\Y = y s pravděpodobnostními rozděleními p(x|y) a p(z\y) nezávislé a náhodný vektor (X| Y = y, Z| Y = y) můžeme ztotožnit s náhodným vektorem (X,Z\Y = y) majícím rozděleníp(x|y)p(z|y). Tedy nutně H(X, Z| V = y) = H(X| Y = y) + H(Z| V = y). Obráceně, nechť platí H(X\Y = y,Z\Y = y) = H{X,Z\Y = y) = H{X\Y = y) + H(Z\Y = y) Pak jsou náhodné proměnné X|y = yaZ|V = y nezávislé a tedy p(z, x|y) = p(z\y)p(x\y), t\.,X^Y^Z. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Věta 8.4 (Nerovnost pri zpracováni dat) Pokud X V ->■ Z, pak l(X\Y)>l(X\Z). Důkaz. H(X£) H(X\Z) l(X\Z) = H(X, Y, Z) - H( Y\X, Z) - | H(X, Y\Z) - H{ Y\X, Z) - H(Y,Z\X) - H(Y\X,Z) Ls-v-' H(Z\X) = H(X, Y, Z) + H( Y\X, Z) - H(X, Y\Z) - H{ Y, Z\X) Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat arkovův řetězec Nerovnost l(X\z) = h(X, Y, Z) + h( Y\X, Z) - h(X, Y\z) - h( Y, z\X) = h{X, Y, Z) + h{ Y\X, Z) - \h(X\ Y, Z) + h{ Y\z) h{z\Y,X) + H{Y\X) = H{X, Y, Z) + H{ Y\X, Z) - H(X\ Y) + H( ^|Z) h{z\Y) + H{Y\X) H(X, Y) + H(X\ Y)\ + H{ Y\X, Z) h(X\ Y) + H( Y\z) + H(Z| Y) + h( Y\X) H(X, Y) - H(X\ Y) - H(Y\X) = l(X\Y) + H{Y\X,Z)- H{Y\Z) + H(Y\X,Z)-H(Y\Z) Tedy l(X\Z) < l(X\Y). <0 Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Důsledek 8.5 Pokud X Y -> Z, pak Q l{Z\X) < l{Y\X), O l{X\Z) < l{Y\Z), O je-li g reálná funkce, pak l(g{Y)\X) < l(Y\X). Důkaz. (i) je reformulace Věty 8.4, (ii) obdržíme z toho, že máme Z Y X a dosazením do (i). Poslední část plyne z toho, že X -> Y -> g( Y je Markovův řetězec a Věty 8.4. I Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Na výklad věty lze nahlížet následujícím způsobem. Předpokládejme, že nejprve se X transformuje na Y procesem A. To může být například přenos dat přes kanál, který zkresluje signály (např. internetová komunikace nebo zápis a čtení CD, DVD, nebo flash paměti). Získáme tak mnoho informací o X pozorováním Y. Dále je běžné provádět následné zpracování, které v tomto modelu představuje proces B. Tvrzení věty potvrzuje, že informace o X zachycením Z nemohou překročit informace o X zachycením Y. Jinými slovy, informaci o X nelze zvětšit postprocessingem, může jen klesnout. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost V praxi je však postprocessing často používán k transformaci informací do jiné reprezentace, kde jsou informace je snadněji přístupné pro interpretaci. Například je snazší pochopit obraz při prohlížení na obrazovce, než je tomu z přijatých dat. Podobně může proces A představovat předzpracování a proces B přenos. Potom věta potvrzuje, že se informace nemohou zvyšovat předzpracováním. Přesto je v praxi běžné používat předzpracování v komunikačních systémech pro transformaci dat do vhodných reprezentací. Když to shrneme, věta tvrdí, že informace se nemohou zvětšovat ani předzpracováním ani následným zpracováním. Informace se mohou během zpracování pouze snižovat Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Problémy 1 O V binárním symetrickém kanálu s pravděpodobností chyby e > 0, kódování sestává ze dvou kódových slov 000 a 111. Zjistěte při použití pravidla maximální pravděpodobnosti pravděpodobnost chyby O Trhlinová chyba (burst error) délky k sestává z posloupnosti k symbolů, které byly všechny přeneseny nesprávně. Najděte očekávaný počet trhlinových chyb délky k, pokud je zpráva délky N přenesena binárním symetrickým kanálem s pravděpodobností chyby p. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Problémy 1 O Nechť kód pro přenos binárním symetrickým kanálem, který má pravděpodobnost chyby e > 0, sestává ze všech pětic nad množinou {0,1}, které obsahují právě dvě jedničky Jaká je pravděpodobnost, že kódové slovo 11000 se dekóduje na slovo 10001, pokud aplikujeme pravidlo minimální vzdálenosti? O Mějme N binárních symetrických kanálů, každý s pravděpodobností chyby p, spojených do série. Ukažte, že celková kapacita tohoto nově vzniklého kanálu je určena vztahem kdepN = 1[1 - (q-p)N], Q/v = 1 - Pn- J Komunikační systém Diskrétní kanál bez paměti Dekódovací pravidla Kapacita kanálu Spojení zdroje s kanálem Kódování se šumem Problémy k řešení Problémy 1 Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Q Uvažme dva diskrétní kanály bez paměti o kapacitách C\ a C2 tak, že oba mají vstupní abecedu Z1 a výstupní abecedu Z2. Součinem kanálů je kanál, jehož vstupní abeceda je 5^2) a výstupní abeceda Y.f\ přičemž kanálové pravděpodobnosti jsou určeny vztahem kde Pi(yj\Xj) je pravděpodobnost, že jsme obdželi řetězec y\, pokud jsme odeslali řetězec x, prostřednictvím i-tého kanálu. Dokažte, že kapacita C součinu kanálů je určena vztahem (S han non 1957) C = Ci + C?. Komunikační systém Diskrétní kanál bez paměti Spojení zdroje s kanálem Dekódovací pravidla Kapacita kanálu Kódování se šumem Kapacita jako hranice Zpracování dat Markovův řetězec Nerovnost Problémy 1 Q Zdroj bez paměti S je spojen ke kanálu C\ o kapacitě C-i a výsledný výstup S-i je vstup ke kanálu C2 o kapacitě C2 (viz níže uvedený diagram). Kanál Kanál Výstup S2 c2 Obrázek 4: Blokový diagram sdělovacího systému Příkladu 6. Ukažte, že platí /(5|52)