Kódování Jan Paseka 22. května 2009 2 2 Předmluva Teorie kódování je interdisciplinární teorie, která v sobě spojuje metody a postupy informatiky, matematiky a spojovací techniky. Teorie kódování přitom stále více a více nachází bezprostřední aplikaci v praxi vlivem nových technologických změn. To, co je na teorii kódování tak strhující, je z jedné strany těsná souvislost teorie s praxí a ze strany druhé pak mnohostranost používaných matematických metod. Úlohou teorie kódování je tvorba postupů a metod, které nám zajistí bezpečný přenos zpráv komunikačním systémem. Z důvodů technické realizovatelnosti se zprávy převedou nejprve do řady znaků nad nějakou konečnou abecedou (nejlépe nad konečným tělesem). Tato řada znaků se pak rozloží do bloků pokud možno stejné délky k. Kódovací zařízení nám pak utvoří z každého bloku délky k blok délky n,kde n k. Redundance získaná v případě kdy n > k slouží později k rozpoznání a případné opravě pokud možno co nejvíce přenosových chyb. Přenos bloků délky n pomocí spojovacího systému, které reprezentují kódované zprávy a které se jako celek označují blokové kódy délky n, si lze představit buď prostorově (přes satelit, telefonem, televizí, rádiem atd.) nebo také v čase (CD, gramodeska, magnetofonová páska atd.). Podíl k/n se nazývá míra informace blokového kódu a reprezentuje množství energie potřebné k přenosu kódovaných zpráv. V rušeném spojovém kanálu se mohou při přenosu kódovaných zpráv vyskytnout chyby dvojího typu. Nejprve je myslitelné, že některé z vysílaných zpráv nedojdou vůbec k příjemci nebo že je příjemce obdrží neúplné. Druhou možností je, že se mohou vyskytnout rovněž přenosové chyby, tj. vyslaný znak 0 se např. přijme jako 1; v teorii kódování se zabýváme zejména druhým případem. Pro opravu eventuálně se vyskytujících se přenosových chyb jsou rozhodující dvě veličiny: * míra opravitelnosti chyb, která nám udává v každé kódované zprávě podíl opravitelných chyb, a * komplexita dekóderu, který má za úlohu pro přijatou kódovanou zprávu zjistit vyslanou zprávu. Hlavním cílem teorie kódování je tvorba kódu s pokud možno co největší mírou informace a s co možná největší mírou opravitelnosti chyb při současně co možná nejmenší komplexitě dekódéru. 3 4 Shannonova věta o kapacitě kanálu nám zaručuje existenci blokových kódů s mírou informace libovolně blízce pod kapacitou kanálu, tzn. s mírou informace, která je tak vysoká jak nám to používaný kanál vůbec dovolí a s libovolně velkou mírou opravitelnosti chyb. Nekonstruktivní charakter této skutečnosti byl zrodem teorie kódování. V mnoha případech je však časová náročnost pro dekódování kódu tak velká, že neúplné využití kapacity kanálu má mnohem menší důležitost než příliš komplikovaný dekódovací postup. Z tohoto důvodu se v teorii kódování zkoumají zejména kódy s relativně jednoduchým realizovatelným dekódovacím algoritmem. Pro určení vlastností opravujících se chyb daného kódu se ukázala důležitá dodatečná znalost jeho struktury. Proto se v teorii kódování zkoumají blokové kódy opatřené dodatečnou algebraickou strukturou, u kterých lze doufat, že budou mít v praxi použitelné teoretické vlastnosti. Lineární kódy reprezentují jistou třídu blokových kódů a jsou opatřeny dodatečnou algebraickou strukturou ­ strukturou vektorového prostoru. Pak lineární kód nad konečným tělesem K je reprezentován jako k-rozměrný podprostor n-rozměrného vektorového prostoru nad K. Strukturu lineárních kódů lze pak analyzovat prostředky a metodami lineární algebry. K nejznámějším příkladům praktického použití lineárních kódů patří * binární Reed-Mullerovy kódy ­ vesmírná sonda "Mariner" použila binární Reed-Mullerův kód prvního řádu délky 32 pro přenos datového materiálu fotodokumentace planety Mars, a rovněž * Reed-Solomonovy kódy ­ např. se používají pro ukládání opticky kódovaných zvukových signálů na CD dva lineární kódy, které byly odvozeny zkrácením Reed-Solomonova kódu délky 255 nad tělesem GF(28 ). Tento učební text je založen na monografii "Codes and Cryptography" D. Welshe. Zároveň využívá texty českých autorů jako je např. "Kódování" Jiřího Adámka. Text je zpřístupněn všem studentům (a uživatelům INTERNETu) pomocí anonymního FTP přístupu na adrese ftp://www.math.muni.cz/pub/math/people/Paseka/lectures/. 4 Obsah 1 Entropie = neurčitost = nejistota = informace 7 1 Nejistota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Entropie a její vlastnosti . . . . . . . . . . . . . . . . . . . . . . . 11 3 Podmíněná entropie . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Informace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5 Závěr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 Věta o kódování bez šumu pro zdroje bez paměti 23 1 Zdroje bez paměti . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2 Prefixové a jednoznačně dekódovatelné kódy . . . . . . . . . . . . 24 3 Kraftova a McMillanova nerovnosti . . . . . . . . . . . . . . . . . 25 4 Věta o kódování bez šumu pro zdroje bez paměti . . . . . . . . . 28 5 Konstruování kompaktních kódování . . . . . . . . . . . . . . . . 30 3 Komunikace kanály se šumem 37 1 Komunikační systém . . . . . . . . . . . . . . . . . . . . . . . . . 37 2 Diskrétní kanál bez paměti . . . . . . . . . . . . . . . . . . . . . . 38 3 Spojení zdroje s kanálem . . . . . . . . . . . . . . . . . . . . . . . 41 4 Kódování a dekódovací pravidla . . . . . . . . . . . . . . . . . . . 43 5 Kapacita kanálu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Věta o kódování se šumem . . . . . . . . . . . . . . . . . . . . . . 49 7 Kapacita jako hranice spolehlivé komunikace . . . . . . . . . . . . 55 4 Kódy opravující chyby 59 1 Kódování a odhady . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2 Ekvivalence kódů a konstrukce nových kódů . . . . . . . . . . . . 65 3 Hlavní problém teorie kódování . . . . . . . . . . . . . . . . . . . 69 4 Dolní a horní hranice Aq(n, d); perfektní kódy . . . . . . . . . . . 71 5 Lineární kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6 Použití lineárních kódů . . . . . . . . . . . . . . . . . . . . . . . . 76 7 Pravidlo minimální vzdálenosti pro lineární kódy . . . . . . . . . 78 8 Binární Hammingovy kódy . . . . . . . . . . . . . . . . . . . . . . 82 9 Cyklické kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5 6 OBSAH 10 Marinerův kód a Reed-Mullerovy kódy . . . . . . . . . . . . . . . 87 10.1 Hadamardovy kódy . . . . . . . . . . . . . . . . . . . . . . 87 10.2 Reed-Mullerovo kódování . . . . . . . . . . . . . . . . . . . 89 A Náhodné jevy a náhodné veličiny 93 1 Měřitelný prostor a vztahy mezi náhodnými jevy . . . . . . . . . 93 2 Pravděpodobnostní prostor . . . . . . . . . . . . . . . . . . . . . . 94 3 Klasická pravděpodobnost . . . . . . . . . . . . . . . . . . . . . . 94 4 Podmíněná pravděpodobnost . . . . . . . . . . . . . . . . . . . . . 94 5 Stochasticky nezávislé náhodné jevy . . . . . . . . . . . . . . . . . 96 6 Borelovské množiny a náhodné veličiny . . . . . . . . . . . . . . . 96 7 Náhodné vektory . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8 Střední hodnota, rozptyl, kovariance a koeficient korelace náhodných veličin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 9 Cauchy-Schwarz-Buňakovského nerovnost, Markovova a Čebyševova nerovnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6 Kapitola 1 Entropie = neurčitost = nejistota = informace 1 Nejistota Uvažme následující tvrzení. A Výsledek běhu mezi dvěma si rovnými závodníky je méně nejistý než výsledek běhu mezi šesti si rovnými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. C Výsledek vrhu ideální kostkou je více nejistý než výsledek vrhu falešnou kostkou. Zřejmě s výše uvedenými tvrzeními lze okamžitě souhlasit. Obtížné však bude definovat, co je to vlastně nejistota. Podívejme se na dvě různé náhodné veličiny X a Y . Nechť P(X = 0) = p, P(X = 1) = 1 - p, a P(Y = 100) = p, P(Y = 200) = 1 - p, přičmž 0 < p < 1. Zřejmě by nám definice nejistoty měla zajistit, že X a Y jsou stejně nejisté. Tedy nejistota X a tedy i Y by měla být funkcí pouze pravděpodobnosti p. Tato vlastnost nejistoty musí být rozšiřitelná i na náhodné proměnné, které nabývají více než dvou hodnot. Tedy: Nejistota náhodné proměnné Z, která nabývá hodnoty ai s pravděpodobností pi, (1 i n), je funkcí pouze pravděpodobností p1, . . . , pn. Proto značíme takovouto funkci jako H(p1, . . . , pn), přičemž předpokládáme splnění následujících přirozených podmínek: 7 8 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE (A1) H(p1, . . . , pn) je maximální, když p1 = p2 = . . . = pn = 1/n. (A2) Pro každou permutaci na {1, . . . , n} platí H(p1, . . . , pn) = H(p(1), . . . , p(n)). Tedy H je symetrická funkce svých argumentů tj. její výsledek nezávisí na pořadí. (A3) H(p1, . . . , pn) 0 a rovnost nastává právě tehdy, když pi = 1 pro nějaké i. Nejistota má tedy vždy nezápornou hodnotu a je nulová právě tehdy, když je jakákoliv náhoda vyloučena. (A4) H(p1, . . . , pn, 0) = H(p1, . . . , pn). Nejistota vrhu šestibokou ideální kostkou je tatáž jako nejistota vrhu sedmibokou kostkou, u které je nemožné, aby padla 7, ale ostatní případy jsou si rovnocenné. (A5) H(1/n, . . . , 1/n) H(1/n + 1, . . . , 1/n + 1). Výsledek běhu mezi dvěma závodníky je méně nejistý než výsledek běhu mezi více závodníky. (A6) H(p1, . . . , pn) je spojitá funkce svých parametrů. Malé změny na vstupu dají malé změny na výstupu. (A7) Jsou-li m, n N, pak H(1/m n, . . . , 1/m n) = H(1/m, . . . , 1/m) + H(1/n, . . . , 1/n). Tato podmínka říká, že nejistota vrhu m n-stranné kostky je obsažena ve vrhu m-stranné kostky následovaná vrhem n-stranné kostky, a je rovna součtu individuálních nejistot. (A8) Nechť p = p1 + . . . + pm a q = q1 + . . . + qn, pi, qj jsou neznámé. Jsou-li p a q kladná čísla, p + q = 1, pak platí H(p1, ..., pm, q1, . . . , qn) = H(p, q)+pH(p1/p, . . . , pm/p)+qH(q1/q, . . . , qn/q). Představme si, že máme n + m uchazečů na místo v konkurzu - z toho je m mužů a n žen, s pravděpodobnostmí pi, qj vítězství v konkurzu. Pak nejistota výsledku konkurzu je nejistota, že vyhraje muž nebo žena plus vážený součet, nejistot výhry mezi muži a ženami. 8 1. NEJISTOTA 9 Věta 1.1 Buď H(p1, . . . , pn) funkce definovaná pro každé přirozené číslo n a pro všechny hodnoty p1, . . . , pn tak, že pi 0 a n i=1 pi = 1. Pokud H splňuje axiómy (A1)-(A8), pak platí H(p1, p2, . . . , pn) = - k pk log pk, (1.1) kde je libovolná kladná konstanta a sumuje se přes všechna k taková,že pk > 0. Důkaz. Nechť H splňuje axiómy (A1)-(A8). Definujme (1) g(n) = H(1/n, . . . , 1/n) pro n N. Z (A7) pak g(nk ) = g(n) + g(nk-1 ) a tedy (2) g(nk ) = k g(n). Buď dále r, s N - {1}, n N a m = m(n, r, s) N tak, že (3) rm sn rm+1 ; pak dle (2) a monotonie g (dle (A5)) máme g(rm ) g(sn ) g(rm+1 ), tedy m g(r) n g(s) (m + 1) g(r). Z (3) pak máme m ln(r) n ln(s) (m + 1) ln(r) a tedy g(s) g(r) - ln(s) ln(r) 1 n . Protože n bylo libovolné přirozené číslo, je g(s) ln(s) = g(r) ln(r) = , kde je nějaká (kladná) konstanta. Tedy 9 10 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE (5) g(s) = ln(s), tj. H( 1 s , . . . , 1 s ) = - ln( 1 s ). Buď 0 < p < 1 racionální, p = t/n, t, n N. Položme q = (n - t)/n. Z (A8) pak g(n) = H( 1 n , . . . , 1 n ) = H( t n , n - t n ) + t n g(t) + n - t n g(n - t). Z (5) pak jednoduchou úpravou H( t n , n - t n ) = - ( t n ) ln t n - ( n - t n ) ln n - t n . Zejména pak (6) H(p, 1 - p) = - p ln p - (1 - p) ln(1 - p), a to pro každé racionální číslo p mezi 0 a 1. Ze spojitosti H platí (6) pro všechna 0 < p < 1. Dokažme, že pro každé N N platí (7) H(p1, . . . , pN ) = - N i=1 pi ln pi, přičemž pi > 0 a p1 + . . . + pN = 1, a to indukcí podle N. Z (6) víme, že (7) platí pro N = 2. Předpokládejme, že (7) platí pro N a uvažujme H(p1, . . . , pN+1). Položme p = p1 + . . . + pN , q = pN+1, a použijme (A8). Máme pak H(p1, . . . , pN+1) = H(p, q) + p H( p1 p , . . . , pN p ) + q H(1) = - p ln p - q ln q + p (-) N i=1 pi p ln pi p , z indukčního předpokladu. Upravíme-li poslední rovnost na tvar H(p1, . . . , pN+1) = - p ln p - pN+1 ln pN+1 - N i=1 pi (ln pi - ln p), a vzpomeneme-li si, že N i=1 pi = p, obdržíme hledanou rovnost H(p1, . . . , pN+1) = - N+1 i=1 pi ln pi. 10 2. ENTROPIE A JEJÍ VLASTNOSTI 11 Na základě výše uvedené věty pak definujeme Definice. Buď X náhodná proměnná s konečným oborem hodnot s odpovídajícími pravděpodobnostmi p1, p2, . . . , pn. Pak definujeme nejistotu neboli entropii náhodné veličiny X jako H(X) = - k pk log2 pk, (1.2) kde suma se bere pouze přes ta k, pro která je pk > 0. Poznámka 1.2 Nadále budeme vždy (bez újmy na obecnosti) předpokládat, že pro všechny členy pravé strany (1.2) jsou pravděpodobnosti pk nenulové. Poznámka 1.3 Podmínky (A1)-(A8) odpovídají axiomům pro entropii navrženým Shannonem. Cvičení 1.4 1. Který dostih má větší entropii: handikap, ve kterém je sedm žokejů, tři z nich vyhrají s pravděpodobností 1 6 a čtyři z nich s pravděpodobností 1 8 nebo dostih, v němž musí být vítěz prodán za předem stanovenou cenu a ve kterém je 8 žokejů s dvěma koni s pravděpodobností výhry 1 4 a šest koní s pravděpodobností výhry 1 12 ? 2. Ověřte, že výše definovaná funkce entropie splňuje podmínky (A1)-(A8). 2 Entropie a její vlastnosti Řekli jsme, že pro náhodnou proměnnou X s konečným oborem hodnot a s pravděpodobnostmi p1, . . . , pn tak, že pi = 1 a pi > 0 (1 i n), definujeme entropii X jako H(X) = - n k=1 pk log2 pk. Analogicky pak pro náhodný vektor X, který nabývá pouze konečně mnoha hodnot u1, . . . , um, defimujeme jeho entropii náhodného velktoru jako H(X) = - m k=1 p(uk) log2 p(uk). (1.3) 11 12 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE Je-li například X 2-dimenzionální náhodný vektor, X = (U, V ) s pij = P(U = ai, V = bj), budeme často psát H(X) = H(U, V ) = - pij log2 pij. Zcela obecně, jsou-li X1, . . . , Xm náhodné proměnné tak, že každá z nich nabývá pouze konečně mnoha hodnot, lze pak považovat X = (X1, . . . , Xm) za náhodný vektor a definovat souhrnou entropii X1, . . . , Xm jako H(X1, . . . , Xm) = H(X) = - (x1,...,xm) p(x1, . . . , xm) log2 p(x1, . . . , xm), (1.4) kde p(x1, . . . , xm) = P(X1 = x1, X2 = x2, . . . , Xm = xm). Snadno se ověří, že: H(X) = 0 právě tehdy, když X je konstantní. (1.5) Horní hranice pro H je určena následující větou: Věta 2.1 Pro každé přirozené číslo n máme H(p1, . . . , pn) log2 n, přičemž rovnost nastává právě tehdy, když p1 = p2 = . . . = pn = n-1 . Důkaz. Zřejmě log2 x = log2 e loge x. Protože logaritmus je konvexní funkce tj. leží celá pod tečnou, máme loge x x - 1, přičemž rovnost nastává právě tehdy, když x = 1. Tedy, je-li (q1, . . . , qn) libovolné pravděpodobnostní rozdělení, pak máme loge(qk/pk) (qk/pk) - 1, s rovností právě tehdy, když qk = pk. Tudíž, pi loge(qi/pi) qk - pk = 0, a z toho pak pi log2 qi pi log2 pi. Položíme-li qi = 1/n, obdržíme dosazením H(p1, . . . , pn) = - pi log2 pi log2 n, což se mělo dokázat. Zbytek tvrzení o rovnosti plyne bezprostředně z důkazu. 12 2. ENTROPIE A JEJÍ VLASTNOSTI 13 Poznamenejme, že jsme dokázali velmi užitečnou nerovnost a to: Lemma 2.2 Je-li (pi : 1 i n) dané pravděpodobnostní rozdělení, pak minimum funkce G(q1, . . . , qn) = - pi log2 qi přes všechna pravděpodobnostní rozdělení (q1, . . . , qn) nastává, pokud qk = pk (1 k n). Věta 2.3 Jsou-li X a Y náhodné proměnné s konečným oborem hodnot, platí pak H(X, Y ) H(X) + H(Y ), přičemž rovnost nastává tehdy a jen tehdy, když X a Y jsou nezávislé. Důkaz. Předpokládejme, že ri = P(X = ai) (1 i m), sj = P(Y = bj) (1 j n), tij = P(X = ai, Y = bj) (1 i m, 1 j n). Pak H(X) + H(Y ) = - i ri log2 ri + j sj log2 sj = - i,j tij log2 ri + j,i tij log2 sj , protože j tij = ri, i tij = sj. Odtud pak H(X) + H(Y ) = - i,j tij log2(ri sj) - i,j tij log2(tij) = H(X, Y ) dle předchozího lemmatu. Rovnost nastane právě tehdy, když ri sj = tij. Ale to je právě podmínka nezávislosti X a Y. 13 14 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE Jednoduchým rozšířením této metody lze dokázat: H(X1, . . . , Xn) H(X1) + . . . + H(Xn), (1.6) přičemž rovnost nastává právě tehdy, když X1, . . . , Xn jsou navzájem nezávislé; H(U, V) H(U) + H(V) (1.7) pro každou dvojici náhodných vektorů U, V, přičemž rovnost nastává právě tehdy, když U a V jsou nezávislé náhodné vektory. Důkazy (jež lze dokázat přesně stejným způsobem jako větu 1.2 z předchozího lemmatu) jsou ponechány čtenáři. Cvičení 2.4 1. Dvě ideální kostky jsou vrženy; X označuje hodnotu získanou první kostkou, Y hodnotu získanou druhou kostkou. Dokažte, že H(X, Y ) = H(X)+H(Y ). Dokažte, že je-li Z = X + Y , pak H(Z) < H(X, Y ). 2. Dokažte, že pro každou náhodnou proměnnou X, H(X, X2 ) = H(X). 3. Dokažte, že pro každou posloupnost náhodných proměnných (Xi : 1 i < ), H(X1, . . . , Xn) H(X1, . . . , Xn+1). 3 Podmíněná entropie Předpokládejme, že X je náhodná proměnná na pravděpodobnostním prostoru a A je událost z . Nabývá-li X konečné množiny hodnot {ai : 1 i m}, je přirozené definovat podmíněnou entropii náhodné proměnné X určenou událostí A jako H(X|A) = - m k=1 P(X = ak|A)logP(X = ak|A). Úplně stejně, je-li Y jiná náhodná proměnná nabývající hodnot bk (1 k m), definujeme podmíněnou entropii náhodné proměnné X určenou náhodnou proměnnou Y jako H(X|Y ) = j H(X|Y = bj)P(Y = bj). 14 3. PODMÍNĚNÁ ENTROPIE 15 Považujeme H(X|Y ) za entropii náhodné proměnné X určenou jistou hodnotou Y zprůměrovanou přes všechny hodnoty, jichž může Y nabývat. Zcela triviální důsledky definic jsou: H(X|X) = 0, (1.8) H(X|Y ) = H(X) jsou-li X a Y nezávislé. (1.9) Příklad 3.1 Buď X náhodná proměnná získaná vrháním ideální kostky. Buď dále Y jiná náhodná proměnná určená tímtéž experimentem, přičemž Y se rovná 1, je-li vržená hodnota lichá a 0 v ostatních případech. Protože kostka je ideální, H(X) = log6, H(Y ) = log2, a H(X|Y ) = log3. Jsou-li U a V náhodné vektory, přirozeně rozšíříme definici podmíněné entropie následovně H(U|V) = j H(U|V = vj)P(V = vj), (1.10) přičemž se sčítá, jako obvykle, přes (konečný) obor hodnot vj tak, že odpovídající pravděpodobnost je kladná. Jako první příklad, jakým způsobem entropie H(U|V) měří nejistotu o U obsaženou ve V, dokážeme: H(U|V) = 0 právě tehdy, když U = g(V) pro nějakou funkci g. (1.11) Důkaz. Pravá strana z definice podmíněné entropie je součet konečného počtu nezáporných veličin. Tudíž, aby byla nulová, potřebujeme H(U|V = vj) = 0 pro všechna j. Ale opět každá z těchto nezáporných veličin je nulová právě tehdy, když U je jednoznačně určená V. Poněkud více nám dává následující výsledek, který matematicky vyjadřuje ideu, že naše definice podmíněné entropie X při daném Y korektně měří zbývající nejistotu. Věta 3.2 Pro každou dvojici náhodných proměnných X a Y , které nabývají pouze konečné množiny hodnot, platí H(X, Y ) = H(Y ) + H(X|Y ). 15 16 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE Důkaz. Bez ztráty na obecnosti lze předpokládat, že X a Y nabývají pouze celočíselných hodnot a, kde to bude nutné, že pij = P(X = i, Y = j). Nyní H(X, Y ) = i j P(X = i, Y = j)logP(X = i, Y = j) = i j P(X = i, Y = j)logP(X = i|Y = j)P(Y = j) = i j pijlogP(X = i|Y = j) i j pijlogP(Y = j) = i j P(X = i|Y = j)P(Y = j)logP(X = i|Y = j) + H(Y ) = - j P(Y = j) i P(X = i|Y = j)logP(X = i|Y = j) + H(Y ) = j P(Y = j)H(X|Y = j) + H(Y ) = H(X|Y ) + H(Y ), což bylo třeba dokázat Věta 3.3 Jsou-li U a V náhodné vektory, které nabývají pouze konečné množiny hodnot, platí H(U, V) = H(V) + H(U|V). Důkaz. Procházíme důkazem předchozí věty, ale namísto X a Y nabývajích pouze celočíselných hodnot i a j máme U a V nabývajích hodnot ui a vj, kde ui a vj jsou zadané vektory. Následující výsledek je bezprostřední důsledek. D usledek 3.4 Pro každou dvojici X a Y náhodných vektorů je H(X|Y) H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. Důkaz. H(X|Y) = H(X, Y) - H(Y). Ale H(X, Y) H(X)+H(Y), s rovností právě tehdy, když X a Y jsou nezávislé. Cvičení 3.5 1. Ukažte, že pro každou náhodnou proměnnou X platí H(X2 |X) = 0, ale uveďte příklad, že H(X|X2 ) není vždy nulová. 2. Náhodná proměnná X nabývá celočíselných hodnot 1, . . . , 2N se stejnou pravděpodobností. Náhodná proměnná Y je definovaná Y = 0, je-li X sudá, ale Y = 1, je-li X lichá. Ukažte, že H(X|Y ) = H(X) - 1, ale že H(Y |X) = 0. 16 4. INFORMACE 17 4 Informace Zdá se, že R.V.L. Hartley byl v r. 1928 první, kdo se pokusil přiřadit kvantitativní míru k pojmu informace. Racionální příčinu za tímto pokusem můžeme částečně popsat následovně. Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru spojené jistým experimentem a předpokládejme, že funkce I je naše míra informace. Mají-li E1 a E2 pravděpodobnosti p1 a p2, pak můžeme argumentovat tím, že každá přirozená míra obsahu informace by měla splňovat I(p1p2) = I(p1) + I(p2) na základě toho, že, pro dvě nezávislé realizace experimentu, informace, pro kterou výsledky těchto experimentů dopadnou jako E1 následováno E2, by měla být součtem informací získaných provedením těchto experimentů zvlášť. Připustíme-li, že výše uvedená rovnost má jistou platnost, a přejeme-li si mít naši míru nezápornou a spojitou v p, což jsou oba přirozené předpoklady, zbývá nám s malou alternativou definovat informaci I události E kladné pravděpodobnosti jako I(E) = -log2P(E), přičemž jsme vybrali 2 jako základ našich logaritmů, abychom zachovali soulad s moderní konvencí. (Hartley původně použil logaritmy o základu 10.) Platí totiž následující tvrzení Věta 4.1 Funkce I(p), definovaná pro všechna 0 < p 1, splňuje podmínky I(p) 0, pro všechna 0 < p 1, I(p q) = I(p) + I(q) pro všechny 0 < p, q 1 takové, že p a q jsou pravděpodobnosti navzájem nezávislých jevů, a podmínku spojitosti vzhledem k p právě tehdy, když je tvaru I(p) = -log2p, kde je kladná konstanta. Důkaz. Ponecháme za cvičení ukázat, že každá funkce výše uvedeného tvaru splňuje všechny tři podmínky. Abychom dokázali obrácené tvrzení, připomeňme, že z vlastnosti I(p q) = I(p) + I(q) máme I(pn ) = nI(p) pro všechna kladná přirozená čísla n. Speciálně tedy platí I(p 1 n ) = 1 n I(p). Odtud pak máme I(p n m ) = nI(p 1 m ) = n m I(p), 17 18 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE tj. platí I(pq ) = qI(p) pro všechna kladná racionální čísla q. Ze spojitosti umocňování a funkce I máme, že pro všechna kladná reálná čísla r musí platit I(pr ) = rI(p). Buď nyní p libovolné, pevně zvolené číslo, 0 < p < 1. Protože každé číslo q, 0 < q < 1 lze psát ve tvaru q = plogpq , máme pak I(q) = I(plogpq ) = I(p)logpq = I(p) log2q log2p = -log2q, pro vhodnou kladnou konstantu = - I(p) log2p . Ze spojitosti funkce I plyne I(1) = 0. Příklad 4.2 Předpokládejme, že máme zdroj, který emituje řetězec binárních číslic 0 a 1, každou se stejnou pravděpodobností a nezávisle pro po sobě jdoucích číslicích. Buď E událost, že prvních n číslic jsou střídavě nuly a jedničky. Pak evidentně I(E) = -log2 1 2n = n a totéž platí pro každou předepsanou posloupnost číslic délky n. Tedy "informačně-teoretická" jednotka informace, totiž bit, odpovídá přirozeně využití slova "bit", které znamená binární číslo v současné počítačové ter- minologii. Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Předpokládejme, že U je náhodný vektor, který nabývá hodnoty u1, . . . , um, s pravděpodobnostmi p1, . . . , pm. Pak každá z elementárních událostí U = uk (1 k m) obsahuje sdruženou informaci rovnou -log2pk a poznamenejme, že entropie vektoru U je určena vztahem H(U) = - pklog2pk = pkI(U = uk), tedy H(U) má přirozenou interpretaci jako střední hodnota informace sdružené s elementárními událostmi určenými U. Obecněji, jsou-li U a V dva náhodné vektory, definujeme informaci o U poskytnutou V jako číslo I(U|V) = H(U) - H(U|V). Jinak řečeno, I(U|V) vyjadřuje množství nejistoty o U odstraněné V. Zřejmě platí, že I(U|U) = H(U), I(U|V) = 0 právě tehdy, když U a V jsou nezávislé. 18 5. ZÁVĚR 19 Důkaz. Výsledek plyne bezprostředně z dřívější poznámky, že H(U) = H(U|V) právě tehdy, když U a V jsou nezávislé. Poněkud udivující symetrie v I je následující výsledek, který zřejmě nemá intuitivní vysvětlení. I(U|V) = H(U) - H(U|V) = H(U) - [H(U, V) - H(V)] = H(U) + H(V) - H(U, V) = I(V|U). Cvičení 4.3 1. Co má větší informační obsah: posloupnost deseti písmen nad abecedou o 26 písmenech nebo posloupnost 26 číslic z množiny {0, 1, . . . , 9}? [ Předpokládejte, že všechny posloupnosti mají stejnou pravděpodobnost.] 2. Ideální kostka je vržena. Ukažte, že informace o hodnotě kostky daná znalostí, že se jedná o nesložené číslo, má velikost log2 3 2 . 5 Závěr Shrneme-li předchozí odstavce, ukázali jsme, že nejistota a informace jsou tytéž veličiny a odstranění nejistoty je rovno podání informace. Obě veličiny jsou měřitelné matematickým pojmem entropie, který je jednoznačně definován (až na multiplikativní konstantu) veličinou H = - pi log pi. Konvence si žádá, aby logaritmy byly brány o základu 2, v kterémžto případě je jednotka entropie bit. Problémy 1.1 1. Diskžokej má slovník o kapacitě 10 000 slov a pronáší 1000 slov náhodně (opakování je dovoleno). Ukažte, že informační obsah jeho 1000 slov je mnohonásobně menší než obrazovky televizního přijímače o 500 řádcích a 600 sloupcích, přičemž každý pixel nabývá jednu z 16 úrovní jasu. 2. Jsou-li X a Y diskrétní náhodné proměnné, které nabývají pouze konečného počtu hodnot, ukažte, že H(X + Y |X) = H(Y |X). Ukažte, že H(g(X, Y )|X) = H(Y |X) neplatí obecně pro g : R2 R. 19 20 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE 3. Je-li (Xi : 1 i < ) posloupnost náhodných proměnných a Y je nějaká jiná náhodná proměnná, dokažte, že H(X1, . . . , Xn|Y ) H(X1, . . . , Xn+1|Y ) pro každé přirozené číslo n. 4. Statistický přehled ženatých dvojic ukazuje, že 70% mužů mělo tmavé vlasy, 25% žen bylo blondýnek a že 80% blondýnek si bere tmavovlasé muže. Kolik informace o barvě mužových vlasů je sděleno barvou vlasů jeho ženy? 5. Jsou-li X, Y, Z náhodné vektory, přičemž každý z nich nabývá pouze konečně mnoha hodnot, dokažte, že H(Y|X) + H(Z|X) H(Y, Z|X). 6. Dokažte, že pro každý náhodný vektor Y a pro každou množinu náhodných proměnných X1, . . . , Xn+1 platí H(Y|X1, . . . , Xn) H(Y|X1, . . . , Xn+1). 7. Jsou-li X a Y dvě náhodné proměnné a f a g jsou libovolné dvě funkce, dokažte, že H(f(X), g(Y )) H(X, Y ). 8. Náhodná proměnná X má binomiální rozdělení s parametry n a p a platí, pro 0 k n, P(X = k) = (n k ) pk qn-k , kde 0 < p < 1 a q = 1 - p. Dokažte, že H(X) -n(plogp + qlogq). 9. Náhodná veličina X má geometrické rozložení a nabývá celočíselných hodnot k = 0, 1, 2, . . . s pravděpodobnostmi pk = P(X = k) = pqk , kde 0 < p a p+q = 1. Ukažte, že rozšíříme-li pojem entropie a definujeme-li H(X) = - k=0 pk log pk, kdykoliv pravá strana konverguje, pak zejména H(X) = -(plogp + qlogq)/p. 20 5. ZÁVĚR 21 10. Nazvěme dvě náhodné proměnné X a Y ekvivalentní, jestliže H(X|Y ) = 0 a H(Y |X) = 0. Dokažte, že jsou-li X a Y ekvivalentní a Z a Y jsou ekvivalentní, jsou i Z a X jsou ekvivalentní. 11. Definujme vzdálenost mezi dvěma náhodnými proměnnými X a Y jako d(X, Y ) = H(X|Y ) + H(Y |X). Dokažte, že pro všechny tři náhodné proměnné X, Y, Z platí d(X, Y ) + d(Y, Z) d(X, Z). 12. Předpokládejte, že X je náhodná proměnná nabývající hodnot v1, . . . , vn. Ukažte, že je-li E(X) = a X je náhodná proměnná s maximální entropií vzhledem k těmto omezením, pak pj = P(X = vj) = Ae-vj , kde A a jsou konstanty určené vztahy E(X) = a pj = 1. Poznámka: hořejší příklad je ilustrací principu maximální entropie: jedná se o rozšíření Laplaceova principu nedostatečné příčiny; tento je často užíván ve statistické mechanice, vytváření obrazů a podobně jako je princip pro vybrání a priori distribuce vzhledem k různým omezením. Viz např. Guiasu a Shenitzer (1985). Řešené problémy 1.1 6. Máme ukázat, že H(X|Y, Z) H(X|Y). Ta ale platí právě tehdy, když H(X, Y, Z)-H(Y, Z) H(X|Y) H(X, Z|Y)H(Z|Y) H(X|Y) H(X, Z|Y) H(X|Y) + H(Z|Y). Stačí tedy ověřit, že H(X, Z|Y) = j H(X, Z|Y = bj)P(Y = bj) j H(X|Y = bj)P(Y = bj) + j H(Z|Y = bj)P(Y = bj) = H(X|Y) + H(Z|Y). Definujme náhodný vektor (X , Z ) předpisem P ((X , Z ) = (ai, cl)) = P ((X, Y, Z) = (ai, bj, cl)) P(Y = bj) . Pak náhodné vektory X a Z jsou definované předpisy P (X = ai) = P ((X, Y) = (ai, bj)) P(Y = bj) a P (Z = cl) = P ((Y, Z) = (bj, cl)) P(Y = bj) . 21 22 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE Pak nutně H(X , Z ) H(X )+H(Z ), což nám sumací přes j dává H(X, Z|Y) H(X|Y) + H(Z|Y). 11. Máme ukázat, že d(X, Y ) + d(Y, Z) d(X, Z). Platí: d(X, Y ) + d(Y, Z) = H(X|Y ) + H(Y |X) + H(Y |Z) + H(Z|Y ) = H(X) - H(Y ) + 2H(Y |X) + H(Y ) + H(Z) + 2H(Z|Y ) = H(X|Z) - H(Z|X) + 2H(Y |X) + 2H(Z|Y ) d(X, Z) = H(X|Z) + H(Z|X). To je ale ekvivalentní s nerovností H(Z|X) H(Z|Y ) + H(Y |X). Jejím rozepsáním obdržíme H(Z, X) - H(X) H(Z, Y ) - H(Y ) + H(Y, X) H(X), a tedy H(Z, X) H(Z, Y ) - H(Y ) + H(Y, X) = H(Y, Z) + H(X|Y ), Máme pak H(Z, X) H(Z, Y, X) = H(X|Y, Z) + H(Y, Z) H(X|Y ) + H(Y, Z). 22 Kapitola 2 Věta o kódování bez šumu pro zdroje bez paměti 1 Zdroje bez paměti V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Stručný oxfordský slovník definuje zdroj jako pramen, vrchol zřídla, ze kterého proudí výstupy. Ve své plné obecnosti, je to přesně to, co uvažujeme v teorii informace, ačkoliv typicky považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Tento náhodný mechanismus může být poměrně dost komplikovaný, ale my se budeme pro okamžik soustředit na následující opravdu speciální a jednoduchý příklad. Značí-li Xi i-tý symbol vytvořený zdrojem, dohodneme se pak, že, pro každý symbol aj, pravděpodobnost P(Xi = aj) = pj je nezávislá na i a tedy je nezávislá na všech minulých nebo v budoucnosti vyslaných symbolech. Jinak řečeno, X1, X2, . . . je právě posloupnost identicky distribuovaných, nezávislých náhodných veličin. Takovýto zdroj nazveme zdrojem s nulovou pamětí nebo zdrojem bez paměti a jeho entropie H je definována jako H = - pjlogpj kde sčítáme přes množinu j takových, že pj > 0. Cvičení 1.1 1. Je-li S zdroj bez paměti s abecedou , rozšíření řádu n S je zdroj bez paměti S(n) s abecedou (n) skládající se ze všech řetězců délky n symbolů ze tak, že pravděpodobnost každého řetězce je určena pravděpodobností, že je to řetězec prvních n symbolů vyslaných S. Dokažte, že S(n) má entropii 23 24 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI H(S(n) ) = nH(S). 2 Prefixové a jednoznačně dekódovatelné kódy Hlavní problém řešený v této kapitole je následující. Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w1, . . . , wn} s pravděpodobnostmi {p1, . . . , pn}. Z pedagogických důvodů budeme prvky W nazývat zdrojová slova a ptát se na následující otázku. Je-li abeceda D symbolů, jak můžeme zakódovat zdrojová slova wi pomocí symbolů z , abychom dostali co možná nejekonomičtější zakódování? Příklad 2.1 Předpokládejme, že zdroj S vysílá čtyři zdrojová slova a, b, c, d s pravděpodobnostmi pa = 0.9, pb = 0.05, pc = pd = 0.025. Srovnáme-li pak zakódování a ; 0, b ; 111, c ; 110, d ; 101, a a ; 00, b ; 01, c ; 10, d ; 11, je evidentně průměrná délka zakódovaného zdroje 1.2 v prvním kódu a 2 v druhém kódu. Formálněji, kódování nebo kód je zobrazení f z {w1, . . . , wn} do , kde označuje soubor konečných řetězců symbolů z . Zpráva je každý konečný řetězec zdrojových slov a, je-li m = wi1 . . . wik a je-li f kódování, pak rozšíření f k W je definováno obvyklým způsobem pomocí zřetězení f(m) = f(wi1 ) . . . f(wik ). Kódování f je jednoznačně dekódovatelné, jestliže každý konečný řetězec z je obraz nejvýše jedné zprávy. Řetězce f(wi) se nazývají kódová slova a přirozená čísla |f(wi)| jsou slovní délky kódování f. Průměrná délka f kódování f je definovaná jako f = m i=1 pi|f(wi)|. 24 3. KRAFTOVA A MCMILLANOVA NEROVNOSTI 25 Kódování f se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé wi a wj tak, že f(wi) je prefix f(wj). Zde používáme, jak lze očekávat, prefix v obvyklém smyslu, že pokud x, y , pak x je prefix y, jestliže existuje z tak, že xz = y. Prefixová kódování jsou jednoznačně dekódovatelná. Skutečně, mají silnější vlastnost, že prefixový kód může být dekódován `on line' bez pohledu do budouc- nosti. Příklad 2.2 Předpokládejme, že = {0, 1} a máme čtyři zdrojová slova w1, .., w4. Prefixové kódování je f(w1) = 0, f(w2) = 10, f(w3) = 110, f(w4) = 1110. Například zprávu 01101001010010 lze dekódovat jako w1w3w2w1w2w2w1w2. (Toto je příklad toho, co je známo jako čárkové kódování, protože evidentně používáme nulu, abychom signalizovali konec slova.) Ne každé jednoznačně dekódovatelné kódování je prefixové. Příklad 2.3 Předpokládejme, že W = {w1, w2}, = {0, 1} a kódování g je definováno jako g(w1) = 0, g(w2) = 01. Toto kódování není evidentně prefixové, ale lze snadno ověřit, že je jednoznačně dekódovatelné, pokud budeme postupovat zpět z konce zprávy. Je zřejmé, že jednoznačně dekódovatelná kódování jsou o mnoho obtížnější pojem, než prefixová kódování. Překvapivě ukážeme, že můžeme omezit pozornost na prefixová kódování v našem hledání jednoznačně dekódovatelných kódování, která mají minimální průměrnou délku. Poznámka 2.4 Ačkoliv jsme definovali kódování jako zobrazení, často ho identifikujeme se souborem C kódových slov. Cvičení 2.5 1. Ukažte, že pro každé přirozené číslo m existuje prefixové kódování nad {0, 1}, které má slova všech délek v množině {1, . . . , m}. 3 Kraftova a McMillanova nerovnosti V tomto odstavci dokážeme dvě základní nerovnosti, které ospravedlňují naši dřívější poznámku, že můžeme v podstatě zapomenout na pojem jednoznačné dekódovatelnosti a omezit pozornost na prefixová kódování. Nejdříve vyslovme nerovnosti. 25 26 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI KRAFTOVA NEROVNOST Je-li abeceda mohutnosti D a W obsahuje N slov, pak nutná a dostatečná podmínka, že existuje prefixové kódování f : W se slovními délkami l1, . . . , lN je, že platí N i=1 D-li 1. (2.1) McMILLANOVA NEROVNOST Je-li abeceda mohutnosti D a W obsahuje N slov, pak nutná a dostatečná podmínka, že existuje jednoznačně dekódovatelné kódování f : W se slovními délkami l1, . . . , lN je, že platí (2.1). Kombinací těchto dvou nerovností dostaneme: Věta 3.1 Jednoznačně dekódovatelné kódování s předepsanou délkou slov existuje právě tehdy, když existuje prefixový kód se stejnou délkou slov. DŮKAZ KRAFTOVY NEROVNOSTI Předpokládejme, že množina {l1, . . . , lN } splňuje N i=1 D-li 1. Přepišme nerovnost do tvaru l j=1 njD-j 1, kde nj je počet li rovných j, l = maxli a vynásobme ji Dl . Přepišme tuto nerovnost opět do tvaru nl Dl - n1Dl-1 - . . . - nl-1D. (2.2) Protože nj jsou všechna nezáporná, postupně dostaneme z (2.2) nerovnosti nl-1 Dl-1 - n1Dl-2 - . . . - nl-2D, nl-2 Dl-2 - n1Dl-3 - . . . - nl-3D, n3 D3 - n1D2 - . . . - n2D, (2.3) n2 D2 - n1D, n1 D. 26 3. KRAFTOVA A MCMILLANOVA NEROVNOSTI 27 Tyto nerovnosti jsou klíč ke konstrukci kódování s danou délkou slov. Nejdříve vyberme n1 slov délky 1, přičemž použijeme různá písmena z . Zbývá nám D - n1 nepoužitých symbolů a můžeme vytvořit (D - n1)D slov délky 2 přidáním písmena ke každému z těchto symbolů. Vyberme našich n2 délky 2 libovolně z těchto slov a zbývá nám pak D2 n1D - n2 prefixů délky 2. Tyto lze užít pro vytvoření (D2 -n1D-n2)D slov délky 3, ze kterých můžeme vybrat n3 libovolně atd. Pokračujeme-li tímto způsobem, pokaždé je zachována vlastnost, že žádné slovo není prefixem jiného. V každém případě zjistíme, že nerovnosti (2.3) nám dovolí provést tento výběr. Tedy skončíme s prefixovým kódováním s předepsanou délkami kódování. Dokázali jsme, že numerická podmínka (2.1) je dostatečná pro existenci prefixového kódování. Ačkoliv Kraft rovněž dokázal i nutnost podmínky (2.1), jedná se o bezprostřední důsledek McMillanovy nerovnosti, kterou v dalším dokážeme. Podaný důkaz je o mnoho jednodušší, než McMillanův původní důkaz a patří Karushovi (1961). DŮKAZ McMILLANOVY NEROVNOSTI Předpokládejme, že máme jednoznačně dekódovatelné kódování C s délkami slov l1, . . . , lN . Pokud l = maxli, pak, pro každé kladné celé číslo r, máme D-l1 + . . . + D-lN r = rl i=1 biD-i , (2.4) kde bi je nezáporné celé číslo. Ale celá čísla bi jsou právě počet možností, kolika způsoby lze řetězec délky i z symbolů abecedy utvořit konkatenací r slov z délek vybraných z množiny {l1, . . . , lN }. Jelikož je kódování C jednoznačně dekódovatelné, každý řetězec délky i tvořený z kódových slov musí odpovídat nejvýše jedné posloupnosti kódových slov. Musíme tedy mít bi Di (1 i rl). Dosadíme-li do (2.4), obdržíme D-l1 + . . . + D-lN r lr. Proto l j=1 njD-j l1/r r1/r , a protože r bylo libovolné kladné celé číslo, dostáváme limitním přechodem r na pravé straně McMillanovu nerovnost. 27 28 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI Cvičení 3.2 1. Jaký je maximální počet slov binárního prefixového kódování, ve kterém je maximální délka slova 7? 4 Věta o kódování bez šumu pro zdroje bez pa- měti Uvažujme nyní následující situaci. Mějme zdroj S bez paměti, který vysílá slova w1, . . . , wm s pravděpodobnostmi p1, . . . , pm, každé vyslané slovo je vybráno nezávisle na všech jiných slovech. Náš problém je: je-li dán takovýto zdroj společně s abecedou , najděte jednoznačně dekódovatelné kódování, jež má minimální průměrnou délku slov. Takovéto kódování nazýváme kompaktní. Heuristický přístup k tomuto problému by mohl být následující. Zdroj S má entropii H = - pilogpi. Maximální entropie v abecedě o D písmenech je logD. Tedy počet symbolů abecedy potřebný v průměru na zakódování slova ze zdroje by měl být asi H/logD. Tuto hrubou ideu nyní zprecizujeme. Věta 4.1 Má-li zdroj bez paměti entropii H, pak každé jednoznačně dekódovatelné kódování pro tento zdroj v abecedě o D symbolech musí mít délku alespoň H/logD. Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší nebo rovnu 1 + H/logD. Důkaz. Předpokládejme, že máme jednoznačně dekódovatelné kódování C s délkami slov l1, . . . , lN . Předpokládejme dále, že pravděpodobnosti emitovaných slov odpovídajících těmto délkám jsou p1, . . . , pN . Tedy H = - pilogpi a průměrná délka kódování C je dána l(C) = pili. Z Kraft­McMillanovy nerovnosti víme, že G = l j=1 njD-j 1. Definujme qi (1 i N) jako 28 4. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI 29 qi = D-li /G, tedy je (q1, . . . , qN ) pravděpodobnostní rozdělení. Aplikujme lemma 1.2.2 a obdržíme H = - pilogpi - pilogqi. Ale logqi = -lilogD - logG. Tedy H pili logD + pi logG. Ale G 1 z Kraft-McMillanovy nerovnosti a tedy, jak je požadováno, H l (C) logD. Abychom dokázali horní hranici, vybereme naše délky slov l1, . . . , lN podle pravidla, že pro všechna i je délka li minimální přirozené číslo splňující p-1 i Dli , tj D-li pi. (2.5) Ale, protože p1 + . . . + pN = 1, toto implikuje N i=1 D-li 1, tedy víme, že existuje jednoznačně dekódovatelné (ve skutečnosti prefixové) kódování s těmito slovními délkami. Ale, protože 2.5 je ekvivalentní s lilogD -logpi a li je minimální vzhledem k této vlastnosti, víme, že li < 1 - logpi/logD. Víme tedy, že l(C) = pili < 1 + H/logD. Cvičení 4.2 29 30 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI 1. Zakódujeme-li n stejně pravděpodobných slov nad binární abecedou, věta o kódování bez šumu tvrdí, že průměrná délka slova l(C) každého kompaktního jednoznačně dekódovatelného kódování splňuje log2n l(C), pro které hodnoty n platí rovnost? 2. Srovnejme hranice věty o kódování bez šumu s délkou kompaktního zakódování 2k - 1 stejně pravděpodobných slov nad {0, 1}. 5 Konstruování kompaktních kódování Předpokládejme, že máme dán zdroj S bez paměti ze slov w1, . . . , wN s pravděpodobnostmi p1, . . . , pN a že si přejeme najít kompaktní kódování C pro S nad abecedou . Z věty o kódování bez šumu víme, že průměrná délka musí splňovat ohraničení H/logD l(C) 1 + H/logD, (2.6) ale snadno se vidí, že dolní hranice lze dosáhnout pouze, když pi jsou jisté celočíselné mocniny D. Z Kraft-McMillanovy nerovnosti máme: Jestliže existuje kompaktní jednoznačně dekódovatelné kódování o průměrné délce l, pak existuje kompaktní prefixové kódování o průměrné délce l. Můžeme se tedy omezit na prefixová kódování. Nyní popíšeme metodu navrhnutou Huffmanem v roce 1952 pro konstruování kompaktníhu prefixového kódování pro výše uvedený zdroj S v případě, že je binární abeceda. Nejprve dokážeme některé vlastnosti kompaktního prefixového kódování C nad = {0, 1}. Budeme užívat l(w) k označení délky slova w v C. Lemma 5.1 Kompaktní kódování pro zdroj s právě dvěma slovy w1 a w2 je w1 0, w2 1. Důkaz. Zřejmé. Lemma 5.2 Je-li C prefixové a kompaktní kódování a pi > pj, pak l(wi) l(wj). Důkaz. Pokud tomu tak není, vytvořme nový kód C z C záměnou zakódování wi a wj. Pak průměrná délka je zmenšena a stále máme prefixové kódování. Lemma 5.3 Je-li C prefixové a kompaktní kódování, pak mezi všemi kódovými slovy v C maximální délky musí existovat alespoň dvě lišící se pouze v poslední číslici. 30 5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 31 Důkaz. Předpokládejme, že tomu tak není; pak můžeme odebrat poslední číslici z těchto všech kódových slov maximální délky a stále máme prefixové kódování, což je spor s kompaktností C. HUFFMANŮV KÓDOVACÍ ALGORITMUS Beze ztráty obecnosti můžeme předpokládat, že zdroj S má svůj systém zdrojových slov {w1, . . . , wN } uspořádaných tak, že pravděpodobnosti pi vyslání wi splňují p1 p2 . . . pN . Huffmanova procedura konstruuje rekurzivně posloupnost zdrojů S0, S1, . . . , SN-2 tak, že S0 = S a Sk je získáno z Sk-1 ztotožněním dvou nejméně pravděpodobných symbolů z Sk-1 s jediným symbolem z Sk. Pravděpodobnost, že symbol je vyslán z Sk je brána jako součet pravděpodobností jeho dvou vytvářejících symbolů v Sk-1. Tedy S1 je získán z S0 ztotožněním wN a wN-1 do jednoho symbolu wN-1 vyskytujícího se s pravděpodobností pN + pN-1. V každém stavu máme zdroj s o jeden méně symboly, až po N - 2 takových redukcích dospějeme k zdroji SN-2, který má pouze dva symboly. Přechod mezi Sj-1 a Sj lze nejlépe vidět na následujícím obrázku. Zakódování Pravděpodobnost Slovo Slovo Pravděpodobnost Zakódování 1 q1 v1 u1 q1 1 2 q2 v2 u2 q2 2 k-1 qk-1 vk-1 uk-1 qk-1 k-1 k+1 qk vk uk qt + qt+1 k k+2 qk+1 vk+1 uk+1 qk k+1 t qt-1 vt-1 (k, 0) qt vt ut qt-1 t (k, 1) qt+1 vt+1 Sj-1 Sj Je-li dáno zakódování 1, . . . , t zdroje Sj, Huffmanova procedura pro nalezení zakódování zdroje Sj-1 je následující velmi snadné pravidlo. Předpokládejme pravděpodobnosti q1 q2 . . . qt+1 slov z Sj-1 jsou takové, že slovo vytvořené z vt a vt+1 je slovo uk z Sj. Pak by Huffmanovo zakódování Sj-1 mělo být, jak je ukázáno v levém sloupci předchozí tabulky. Formálně, mělo by být zadáno pravidlem 31 32 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI vi i (1 i k - 1), vi i+1 (k i t - 1), vt (k, 0), vt+1 (k, 1). Zpětným zpracováním nastartujeme naši zakódovací proceduru zakódováním dvou slov z SN-2 s dvěma kódovými slovy 0 a 1; pak SN-3 bude mít tři kódová slova atd. a budeme pokračovat ve výše uvedené proceduře, až dosáhneme Huffmanova kódu pro S = S0. Budeme ilustrovat tuto metodu na skutečně malém příkladě. Příklad 5.4 Předpokládejme, že S je zdroj s pěti zdrojovými slovy a pravděpodobnostmi (viz níže). Pak vývoj Huffmanova zakódování lze považovat za procházení šipek dopředu a pak zakódování zpátky. W P C W P C W P C W P C w1 0.5 1 v1 0.5 1 u1 0.5 1 x1 0.5 0 w2 0.2 01 v2 0.2 01 u2 0.3 00 x2 0.5 1 w3 0.15 001 v3 0.15 000 u3 0.2 01 w4 0.1 0000 v4 0.15 001 w5 0.05 0001 W: slovo, P: pravděpodobnost C: kódování Výsledné zakódování w1 1, w2 01, w3 001, w4 0000, w5 0001 má průměrnou délku 1.95 na zdrojové slovo. Poznámka 5.5 Minimálně dvakrát v horním příkladu jsme schopni provést výběr, protože dvě slova mají stejné pravděpodobnosti. Pokud tento případ nastane, dostaneme různá zakódování. DŮKAZ, ŽE HUFFMANŮV ALGORITMUS JE KOREKTNÍ Z lemmatu 1 víme, že zakódování SN-2 dvěma symboly 0 a 1 je optimální. Důkaz bude tedy úplný, jestliže budeme schopni dokázat, že kompaktnost je zachovávána při přechodu ze zdroje Sj ke zdroji Sj-1. Předpokládejme tedy, že Sj je kompaktně zakódován a že l1, . . . , lt jsou délky slov 1, . . . , t, ale že Huffmanovo zakódování Cj-1 zdroje Sj-1 není kompaktní. Existuje tedy prefixové kompaktní kódování C zdroje Sj-1 tak, že l(C) < l(Cj-1). 32 5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 33 Dle lemmatu 3 můžeme přeuspořádat kódová slova kódování C maximální délky tak, že má-li C kódová slova v 1, . . . , v t+1 s délkami l 1, . . . , l t+1, pak l 1 l 2 . . . l t+1 a v t = (, 0), v t+1 = (, 1), kde je nějaké kódové slovo z . Nechť kódování C zdroje Sj sestává ze slov v 1, v 2, . . . , v k-1, , v k, . . . , v t-1; pak C je prefixové zakódování zdroje Sj a má průměrnou délku l(C ) = q1l 1 + . . . + qk-1l k-1 + (qt + qt+1)|| + qkl k + qk+1l k+1 + . . . +qt-1l t-1 = l(C) - (qt + qt+1). Ale zároveň l(Cj) = l(Cj-1) - (qt + qt+1). Tudíž, jestliže l(C) < l(Cj-1), pak l(C ) < l(Cj), což je spor s kompaktností Cj. HUFFMANOVA KÓDOVÁNÍ NAD NEBINÁRNÍMI ABECEDAMI Předpokládejme, že pracujeme namísto s binární abecedou {0, 1} s abecedou o r symbolech. Budeme postupovat stejným způsobem. Stejně jako v binárním případě, začněme s S = S0 (původní zdroj) a budeme konstruovat posloupnost zdrojů S0, S1, . . . , St až skončíme u zdroje St obsahujícím právě r symbolů. Tento zdroj má kompaktní zakódování (jednoduše máme bijekci mezi St a abecedou ). Musíme aplikovat následující dva body: 1. Jak budem konstruovat Sj+1 z Sj, ztotožníme ne 2, ale r nejméně pravděpodobných symbolů z Sj do jednoho symbolu z Sj+1. Tedy Sj+1 má o r - 1 symbolů méně než Sj. 2. Budeme potřebovat pro závěrečný zdroj St, abychom měli právě r symbolů. Abychom toho dosáhli, je nutno začít se zdrojem S s právě r + t(r - 1) symboly. Protože obecně je málo pravděpodobné, že S bude mít právě tento počet slov, uměle přidáme k S množinu S , která bude disjunktní s S, a slova v ní obsažená budou mít nulovou pravděpodobnost. Pak klademe S0 = SS a máme |S | = r + t(r - 1) - |S|. Cvičení 5.6 1. Jaká je průměrná délka slova kompaktního kódování nad {0, 1}, jestliže máme 5 stejně pravděpodobných zdrojových slov? 33 34 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI 2. Najděte kompaktní kódování nad {0, 1} pro zdroj vysílající slova w1, . . . , w6 s pravděpodobnostmi P(w1) = 1 3 , P(w2) = 1 4 , P(w3) = 1 6 , P(w4) = P(w5) = P(w6) = 1 12 a porovnejte jejich průměrnou délku s horní a dolní hranicí dle věty o kódování bez šumu pro zdroje bez paměti. 3. Najděte kompaktní kódování nad {0, 1, 2} pro zdroj z předchozího příkladu. Problémy 2.1 1. Ve hře na šachovnici má jeden z hráčů (A) uhádnout, kam jeho protivník umístil královnu. Hráči A je povoleno šest otázek, které musí být pravdivě zodpovězeny odpovědí ano/ne. Dokažte, že existuje strategie, při které může hráč A vždy vyhrát tuto hru, ale že nelze zajistit výhru, pokud má povoleno pouze pět otázek. 2. Je-li hra z předchozího příkladu hraná na šachovnici o rozměrech n × n, kolik otázek potřebuje hráč A, aby bezpečně vyhrál. 3. Najděte průměrnou délku optimálního (kompaktního) jednoznačně dekódovatelného binárního kódu pro zdroj bez paměti, který vysílá šest slov s prav- děpodobnostmi 0.25, 0.10, 0.15, 0.05, 0.20, 0.25. Analyzováním Huffmanova algoritmu ukažme, že zdroj bez paměti vysílá N slov a jestliže l1, . . . , lN jsou délky kódových slov optimálního kódování nad binární abecedou, pak l1 + . . . + lN 1 2 (N2 + N - 2). 4. Máte k dispozici rovnovážnou váhu a devět zdánlivě identických mincí. Bylo Vám sděleno, že jedna mince je různá od zbývajících stejných mincí. Máte za úkol najít, o kterou minci se jedná a zda je těžší nebo lehčí. Navrhněte strategii o nejvýše 3 váženích pro řešení tohoto problému. Abychom obecně vyřešili tentýž problém pro n mincí v k váženích, je nutno, aby platilo, že k log 3 log 2n. Dokažte. 5. V Huffmanově algoritmu pro binární abecedu aplikovaném na N zdrojových slov jsou délky slov pro konečné optimální zakódování l1, . . . , lN . Dokažte, že l1 + . . . + lN N log2 N. 6. Mějme dva hráče, hráče A a hráče B. Tito hráči hrají hru s náhodnou kostkou, která má n stran a nabývá hodnot 1, . . . , n s pravděpodobnostmi p1, p2, . . . , pn. Hráč B vrhá kostkou za závěsem a hráč A má zjistit hodnotu po vržení kostky co možná nejrychleji. Hráč A se může ptát hráče B a ten mu musí pravdivě odpovídat buď ano nebo ne. Ukažte, že průměrný počet otázek pro úspěšnou strategii hráče A musí být alespoň entropie H = - pjlogpj. 34 5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 35 7. Ukažte, že optimální zakódování zdroje s N stejně pravděpodobnými zdrojovými slovy v abecedě o D písmenech, je max{(Dr+1 - N - b)/(D - 1), N} slov délky r, kde b je určeno vztahem N + b = D + k(D - 1), 0 b < D - 1, a r je největší přirozené číslo tak, že Dr N + b. 8. Dokažte, že následující metoda nám dává jednoznačně dekódovatelný kód pro zdro S. Předpokládejme, že S má N zdrojových slov s1, s2, . . . , sN a pi je pravděpodobnost, že je vysláno slovo si, přičemž platí pi pi+1. Nechť navíc a1 = 0, a2 = p1, a3 = p1 + p2, . . . , aN = p1 + p2 + . . . + pN-1. Nechť mi (1 i N) je definováno jako nejmenší takové přirozené číslo mi splňující 2-mi pi. Je-li pak a j binární rozvoj čísla aj na mj desetinných míst, je kódování sj a j , 1 j N jednoznašně dekódovatelné pro zdroj S. Ukažte, že se nejedná o optimální zakódování, ale že průměrná délka ^l kódování splňuje H(S) ^l H(S) + 1. 9. Jsou-li l1, . . . , ln délky slov binárního Huffmanova kódování zdrojových slov majících pravděpodobnost p1, . . . , pn, pak redundance kódování je definována jako r = n k=1 pklk - H(p1, . . . , pn). Ukažte, že platí r pmax + log[2(log e)/e] = pmax + 0.086, kde pmax = maxipi. 35 36 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI 36 Kapitola 3 Komunikace kanály se šumem 1 Komunikační systém 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 3.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é podoby. 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. 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. Ovšem celý přenos informace od zdroje až po zpracování není tak jednoduchý, 37 38 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM jak znázorňuje (obr.3.1). Sestává z komplexnějšího sdělovacího systému; jednu takovou možnost nabízí (obr.3.2). 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 Demodulátor Obrázek 3.2: Konkrétní sdělovací systém. 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. 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. Demodulátor 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. 2 Diskrétní kanál bez paměti 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 1 a vysílá řetězce symbolů z výstupní abecedy 2. 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 1 = {a1, . . . , am}, výstupní abecedou 2 = {b1, . . . , bn} a maticí P kanálu P = p11 p12 . . . . . . p1n-1 p1n p21 p22 . . . . . . p2n-1 p2n ... ... . . . . . . ... ... pm-11 pm-12 . . . . . . pm-1n-1 pm-1n pm1 pm2 . . . . . . pmn-1 pmn . Způsob používání kanálu je následující: každá posloupnost (u1, u2, . . . , uN ) symbolů ze vstupní abecedy 1 na vstupu se převede na posloupnost (v1, v2, . . . , vN ) 38 2. DISKRÉTNÍ KANÁL BEZ PAMĚTI 39 téže délky symbolů z výstupní abecedy 2 na výstup tak, že P(vk = bj|uk = ai) = pij (1 i m, 1 j n), a to nezávisle pro každé k. Implicitně je ve výše uvedeném obsaženo, že pro každé i, 1 i m platí j pij = 1. Matice P s nezápornými hodnotami taková, že součet prvků v každém řádku je roven 1, se nazývá stochastická matice; v teorii náhodných procesů mluvíme o matici přechodu markovského řetězce. Je často užitečné reprezentovat kanál pomocí diagramu, jako je tomu např v násl. příkladu. Příklad 2.1 Binární vypouštěcí kanál má vstupní abecedu 1 = {0, 1}, výstupní abecedou 2 = {0, 1, } a maticí P kanálu P = 1 - 0 0 1 - . Diagram odpovídající tomuto kanálu má tvar * 0 0 ˇ 1 - * - 1 ˇ * 1. 1 - - 39 40 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM To odpovídá situaci, pro kterou má každý symbol pravděpodobnost , že se špatně přenese a to na . Ale jak 1 tak 0 nelze navzájem zaměnit. Příklad 2.2 Nejpoužívanější kanál v tomto modelu komunikace je binární symetrický kanál má vstupní abecedu 1 = {0, 1}, výstupní abecedou 1 = {0, 1} a maticí P kanálu P = 1 - p p p 1 - p . Diagram odpovídající tomuto kanálu má tvar 0 ˇ 1 - p- ˇ 0 1 ˇ 1 - p- p * 1. p Jinak řečeno, to odpovídá situaci, pro kterou má každý symbol x pravděpodobnost p, že se špatně přenese a to na 1 - x. Často budeme psát q = 1 - p bez dalšího komentáře. Rozšíření diskrétních kanálů bez paměti Uvažme diskrétní kanál bez paměti se vstupní abecedu 1, výstupní abecedou 2 a maticí P kanálu . r-té rozšíření tohoto kanálu je diskrétní kanál bez paměti se vstupní abecedu (r) 1 , výstupní abecedou (r) 2 a maticí P(r) kanálu , která je definována následovně: Souřadnice (i, j) matice P(r) odpovídající vstupu i = 12 . . . r s k 1, a výstupu j = 12 . . . r s k 2, je (P(r) )ij = p(1|1)p(2|2) . . . p(r|r), kde p(k|k) je pravděpodobnost, že v kanálu s maticí P je obdržen symbol k za předpokladu odeslání k. Příklad 2.3 Druhé rozšíření binárního symetrického kanálu s maticí P kanálu P = q p p q 40 3. SPOJENÍ ZDROJE S KANÁLEM 41 má tvar P2 = q2 qp pq p2 qp q2 p2 pq pq p2 q2 qp p2 pq qp q2 = qP pP pP qP . Alternativní způsob jak můžeme přemýšlet o r-té extenzi je, že kanál C považujeme za r kopií C operujících nezávisle a paralelně dle níže uvedeného. C1 C2 ... input 12 . . . r - ˇ 1 - 2 ... ˇ output 12 . . . r - 1 - 2 - ... Cr r - r Cvičení 2.4 1. Zpráva sestávající z N binárních číslic je přenesena binárním symetrickým kanálem mající pravděpodobnost chyby přenosu p. Ukažte, že očekávaný počet chyb je Np. 3 Spojení zdroje s kanálem Uvažme následující situaci: máme zdroj bez paměti S, který vysílá symboly (zdrojová slova) s1, . . . , sN s pravděpodobnostmi p1, . . . , pN . Zdroj je spojen s binárním symetrickým kanálem s pravděpodobností chyby následovně: 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 41 42 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM 000 s1 ? 100 s2 ? 010 s3 ? 001 s4 ? 110 s5 ? 101 s6 ? 011 s7 ? 111. s8 ? Zpráva je řetězec zdrojových slov si, 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? 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ě: 000000 s1 ? 100100 s2 ? 010010 s3 ? 001001 s4 ? 110110 s5 ? 101101 s6 ? 011011 s7 ? 111111. s8 ? Pokud dekódovací zařízení přijme 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. 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. 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 0000 s1 ? 1001 s2 ? 0101 s3 ? 0011 s4 ? 1100 s5 ? 1010 s6 ? 0110 s7 ? 1111. s8 ? 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. 42 4. KÓDOVÁNÍ A DEKÓDOVACÍ PRAVIDLA 43 4 Kódování a dekódovací pravidla Buď dán kanál bez paměti se vstupní abecedou 1 = {a1, . . . , am} a výstupní abecedou 2 = {b1, . . . , bk}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze 1. Prvky z C se nazývají kódová slova. Je-li dán kód délky n s kódovými slovy c1, c2, . . . , cN , dekódovací pravidlo je libovolný rozklad množiny možných obdržených posloupností do disjunktních množin R1, R2, . . . , 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 cj. 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 f : n 2 C {?}. Aplikaci dekódovacího pravidla nazýváme dekódování. Je-li y (obdržené) slovo v n 2 , 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) =?. 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. Příklad 4.1 Předpokládejme, že máme zdroj s právě dvěma zdrojovými slovy s1 a s2, který můžeme zakódovat pro přenos binárním symetrickým kanálem jako s1 000 = c1, s2 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 s1, pokud obsahuje více nul než jedniček. Méně citlivé pravidlo by mohlo být dekódovat zprávu jako s1, 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 jako s1! Naší snahou bude najít dekódovací pravidlo, které maximalizuje pravděpodobnost správného dekódování tj. pravděpodobnost, že x = f(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žijemeli například formuli úplné pravděpodobnosti, obdržíme následující dva vztahy: P(správné dekódování) = cC P(správné dekódování|c odesláno)P(c odesláno), (3.1) vztahujeme-li podmínku na množinu kódových slov resp. P(správné dekódování) = yn 2 P(správné dekódování|y obdrženo)P(y obdrženo), (3.2) 43 44 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM vztahujeme-li podmínku na množinu slov ze n 2 . Poznamenejme, že vztah (3.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 (3.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 ode- sláno. 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) = y,f(y)=c P(y obdrženo|c odesláno). (3.3) Provedeme-li substituci do (3.1), obdržíme P(správné dekódování) = cC,y,f(y)=c P(y obdrženo|c odesláno)P(c odesláno). (3.4) Tato dvojnásobná suma není však vždy zcela příhodná. Přitom vztah (3.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 odesláné slovo bylo f(y). Platí tedy P(správné dekódování|y obdrženo) = P(f(y)odesláno|y obdrženo) (3.5) a přitom se ve výše uvedeném výrazu nevyskytuje žádná suma. Dosaďme do vztahu (3.2). Pak máme P(správné dekódování) = yn 2 P(f(y) odesláno|y obdrženo)P(y obdrženo). (3.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(f(y) odesláno|y obdrženo). Jinak řečeno, za předpokladu, že jsme obdrželi y, rozhodneme se tak, že kódové slovo, které bylo posláno, je to nejpravdě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(c1 odesláno|y obdrženo), . . . , P(cN odesláno|y obdrženo) 44 4. KÓDOVÁNÍ A DEKÓDOVACÍ PRAVIDLA 45 a vybereme kódové slovo ci 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 cj. Máme totiž podle Bayesovy věty: P(c odesláno|y obdrženo) = P(y obdrženo|c odesláno)P(c odesláno) N k=1 P(y obdrženo|ck odesláno)P(ck odesláno) . (3.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é. 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 cj tak, že maximalizuje P(y obdrženo|cj odesláno). (3.8) Pro ty, kteří jsou obeznámeni s odhady maximální pravděpodobnosti ve statistice, je analogie zřejmá. 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 pravidlem ideálního pozorovatele. (3.9) Důkaz je snadný. Totiž platí P(c odesláno) = 1 N . Tedy platí dle (3.7) P(c odesláno|y obdrženo) = P(y obdrženo|c odesláno) N k=1 P(y obdrženo|ck odesláno) . (3.10) Odtud pak máme, že maximum na pravé straně obdržíme právě tehdy, když budeme mít maximum na levé straně. 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 45 46 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší. 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 cj, které má minimální Hammingovu vzdálenost od y: pokud je vícero takových slov, vybereme cj libovolně. P(y obdrženo|cj odesláno). (3.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 1 2 je dekódovací pravidlo minimální vzdálenosti ekvivalentní k pravidlu maximální pravdě- podobnosti. Důkaz. Pro všechny vektory x a y z Vn s vlastností d(x, y) = d platí P(y bylo obdrženo|x bylo odesláno) = pd qn-d . Pokud p < 1 2 , 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í. Cvičení 4.3 1. Nechť kód sestává ze čtyř kódových slov c1 = 1000, c2 = 0110, c3 = 0001 a c4 = 1111. Pravděpodobnosti výskytu těchto kódových slov jsou dány jako P(c1) = P(c2) = 1 3 , P(c3) = P(c4) = 1 6 Používáte-li pro přenos binární symetrický kanál s pravděpodobnosti chyby 1 10 a obdržíte na výstup vektor 1001, jak by jste se rozhodoval při (a) použití pravidla ideálního pozorovatele, (b) použitím pravidla maximální pravděpodobnosti? 2. Dokažte tvrzení 3.9 tj. že v případě, že všechna kódová slova stejnou pravděpodobnost, pravidlo maximální pravděpodobnosti splývá s pravidlem ideálního pozorovatele. 46 5. KAPACITA KANÁLU 47 5 Kapacita kanálu 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 1 = {a1, . . . , am}, výstupní abecedou 2 = {b1, . . . , bn} a maticí P kanálu P = [pij] = P(bj obdrženo|ai odesláno). Přidáme-li k tomuto kanálu zdroj S bez paměti, který vysílá symboly a1, . . . , am s pravděpodobnostmi p1, . . . , pm, pak výstup kanálu můžeme považovat za zdroj J bez paměti, který vysílá symboly b1, . . . , bn s pravděpodobnostmi q1, . . . , qn, kde qj = m i=1 P(bj obdrženo|ai odesláno)P(ai odesláno) = m i=1 pipij. Informace o S podaná pomací J , definovaná v kapitole 1, je rovna I(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í p1, . . . , pm, a matici kanálu P. Je proto přirozené definovat kapacitu C kanálu jako C = sup I(S|J ), (3.12) 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í (p1, . . . , pn). Nejdříve si připomeňme, že C je dobře definováno v tom smyslu, že pouze hledáme supremum funkce f(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 3.12 přepsat jako C = max I(S|J ), (3.13) 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 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. 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 + p log p + q log q, (3.14) kde q = 1 - p. 47 48 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM Důkaz. K usnadnění označení předpokládejme, že zdroj S emituje 0 s pravděpodobností a 1 s pravděpodobností = 1 - . Pak výstup J má rozdělení 0 s pravděpodobností q + p, 1 s pravděpodobností q + p. Je tedy H(S, J ) právě entropie rozdělení (q, p, q, q). Po jednoduché úpravě I(S|J ) = p log p + q log q - (q + p) log(q + p) -(p + q) log(p + q) . Derivujme dle . Pak obdržíme, že I(S|J ) má maximum v případě, že = 1 2 a obdržíme pak 3.14. Poznamenejme, že kapacita má očekávané vlastnosti ­ C(p) je monotonní funkce p, 0 p 1 2 , a C(0) = 1, C( 1 2 ) = 0, což odpovídá intuici, že, pokud p = 1 2 , 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ů. Příkladem první z těchto technik je následující výsledek. Věta 5.2 Má-li kanál S bez paměti kapacitu C, má jeho r-té rozšíření S(r) kapacitu rC. Důkaz. Označme jako C(r) kapacitu r-tého rozšíření tak, že C(r) = supXH(X) - H(X|Y), (3.15) kde X = (X1, . . . , Xr) a Y = (Y1, . . . , Yr) jsou vstupní a výstupní dvojice. Máme ale H(X) - H(X|Y) = H(Y) - H(Y|X). (3.16) a H(Y|X) = x p(x)H(Y|X = x). Protože se jedná o kanál bez paměti, máme H(Y|X = x) = i H(Yi|X = x) = i H(Yi|Xi = xi). 48 6. VĚTA O KÓDOVÁNÍ SE ŠUMEM 49 Zejména H(Y|X)= x p(x)H(Yi|Xi = xi) = i u H(Yi|Xi = u) P(Xi = u). Tedy H(Y|X) = r i H(Yi|Xi). (3.17) Obecně platí H(Y) H(Y1) + . . . + H(Yr), a tedy celkem C(r) rC. Připomeňme, že rovnost nastává právě tehdy, když Y1, . . . , Yr jsou nezávislá. Toho lze dosáhnout tím, že zvolíme X1, . . . , Xr jako nezávislé a vybráním rozdělení, při kterém bylo dosaženo kapacity C kanálu. Cvičení 5.3 1. Vypočtěte kapacitu binárního vypouštěcího kanálu s pravděpodobností chyby . 2. Uvažujeme-li kanál bez paměti s maticí 1 0 0 1 0 1 , ukažte, že kapacity lze dosáhnout více než jedním rozdělením na vstupu. Ukažte, že rozšířením 2. řádu můžeme dosáhnout kapacity pomocí rozdělení na vstupu, kteé není součinem rozdělení na vstupu původního kanálu. (Feinstein, 1958) 6 Věta o kódování se šumem Již dříve jsme viděli, že můžeme dosáhnou libovolně velké spolehlivosti pouze dostatečně častým opakováním každého zdrojového symbolu. Zřejmě je tato metoda velmi časově náročná a hlavním účelem tohoto odstavce je dokázat překrásné tvrzení C. Shannona (1948), které tvrdí, že za předpokladu, že rychlost (míra) přenosu je pod kapacitou kanálu, lze dosáhnout libovolně velké spolehlivosti. Budeme se koncentrovat na binární symetrický kanál. Tyto myšlenky lze rozšířit na podstatně komplikovanější kanály, ale důležitější je plně porozumět nosným principům, než se obklopit matematickými detaily. Buď dán kód C a dekódovací schéma pro C. Pravděpodobnost chyby e(C) je obvykle definovaná jako průměrná pravděpodobnost chyby za předpokladu, že všechna kódová slova byla vyslána se stejnou pravděpodobností. Jinak řečeno, máme-li M kódových slov c1, . . . , cM z C, pak platí e(C) = 1 M M i=1 P(nastala chyba|ci bylo přeneseno). 49 50 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM V případě binárních kódů můžeme předpokládat, pokud nebude jinak uvedeno, že používáme dekódovací pravidlo maximální pravděpodobnosti (=pravidlo minimální vzdálenosti), a tudíž se často budeme odvolávat na pravděpodobnost chyby kódování bez specifického připomenutí dekódovacího pravidla. Zřejmě je předmětem příkladu najít kódy s malou průměrnou pravděpodobností chyby. Avšak, podstatně silnějším požadavkem je, že maximální pravděpodobnost chyby je malá. Jak lze očekávat, ta je definována jako ^e(C) = maxiP(nastala chyba|ci bylo přeneseno), a evidentně ^e 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 + p log p + (1 - p) log (1 - p). Dokažme následující verzi Shannonovy věty o kódování se šumem. Věta 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 < ) přirozených čísel splňujících 1 Mn 2Rn (1 n < ), a všechna kladná > 0, existuje posloupnost kódů (Cn : 1 n < ) a přirozené číslo N0() tak, že Cn má Mn kódových slov délky n a maximální pravděpodobnost chyby ^e(Cn) pro všechna n N0(). 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 20.75n 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 n 4 = m N0(). (b) Zakódujte každý z těchto m-bloků do kódu Cn tak, že použijete kódové slovo délky 4m 3 pro každý m-blok. (b) Přeneste nově zakódovanou posloupnost kanálem. 50 6. VĚTA O KÓDOVÁNÍ SE ŠUMEM 51 Č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. Důkaz Shannonovy věty, který chceme provést níže, závisí na dvou nerovnostech ­ z ních 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 . (3.18) Druhá nerovnost je méně známá a má rovněž pravděpodobnostní interpretaci; lze ji vyslovit následovně. Omezená nerovnost Pro všechna , 0 1 2 , platí n k=0 n k 2nh() , (3.19) kde h() = -[ log + (1 - ) log (1 - )]. Důkaz. Let m = n . We put 0 = m n . Then 0 < 0 + 1 n . Assume > 0 0, = - 0 > 0. Then 2nh() = 2-n[0 log +(1-0) log (1-)] 2-n[ log - log (1-)] 2-n[0 log 0+(1-0) log (1-0)] 2n log 1- 2nh(0) 2n log 1- 2nh(0) 2log 1- 2nh(0) 1- 2nh(0) Můžeme tedy bez újmy na obecnosti předpokládat, že bylo vybráno tak, že n je přirozené číslo. Pak můžeme psát 1 = [ + (1 - )]n n k=0 n k k (1 - )n-k (1 - )n n k=0 n k 1- n = n (1 - )n(1-) n k=0 n k . Tudíž n k=0 n k n (1 - )n(1-) = 2nh() , logaritmujeme-li při základu 2 a pak znovu umocníme. 51 52 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM Důkaz věty o kódování se šumem 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 ci Vn. Vybereme ta kódová slova ci trochu bláznivou metodou vybráním vektorů z Vn náhodně a nezávisle na i, (1 i 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éru se středem y, tj. Sr(y) = {z : z Vn, d(y,z) r}. Pak, je-li y obdržený vektor, můžeme dekódovat y jako kódové slovo cj, je-li cj jediné kódové slovo v Sr(y); jinak budeme dekódovat y jako libovolné jiné kódové slovo, např. c1. Začněme nyní s vlastním důkazem. Nechť Y je vektor, který obdržíme, když je přenášeno kódové slovo c a E buď událost, že nastala chyba. Přitom chyba může nastat právě tehdy, když buď (a) d(c, Y) > r nebo (b) d(c, Y) r a d(c', Y) r pro nějaké jiné kódové slovo c'. Označme po řadě A a B události popsané (a) a (b). Pak E = A B a tudíž P(E) = P(A B) 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. Označíme-li po řadě tyto události B1 a B2, máme pak, protože B = B1 B2, P(B) P(B2). (3.20) Uvažme nyní B2; protože kódová slova jsou vybrána náhodně, pravděpodobnost, že ci má vzdálenost menší nebo rovnu r od Y je Nr(n)/2n , kde Nr(n) = r k=0 n k (3.21) je počet vektorů z Vn, které leží v Sr(y). 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 P(B2) M - 1 2n r k=0 n k . (3.22) 52 6. VĚTA O KÓDOVÁNÍ SE ŠUMEM 53 Položme tudíž, pro všechna > 0, r = np + n jakožto maximální celé číslo ne větší než np + n, obdržíme pak z 3.20, 3.21, 3.22 a omezené nerovnosti, že P(B) M 2n 2nh(p+) . (3.23) 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. Tudíž P(A) = P(U > np + n) P(|U - np| > ) D(U)/n2 2 , dle Čebyš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) pq n2 + M2-n[1-h(p+)] . pro dostatečně velká n. Protože kapacita C(p + ) = 1 - h(p + ), máme pak P(E) pq n2 + M2-nC(p+) . Protož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 < . Položme proto = 1 2 a Mn = 2Mn. Poznamenejme, že protože Mn 2Rn a R < C, musí existovat R tak, že R < R < C, a N0 tak, že pro všechna n N0 platí Mn 2nR a tudíž existuje posloupnost kódů Cn tak, že Cn má Mn kódových slov a průměrnou pravděpodobnost chyby < pro n N0. 53 54 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM Jsou-li x1, . . . , xM kódová slova z Cn, znamená to, že Mn i=1 P(E|xi) Mn. Tedy alespoň polovina těchto kódových slov xi musí splňovat P(E|xi) 2 = . (3.24) Buď Cn kód sestávající z Mn kódových slov splňujících 3.24; pak máme náš požadovaný kód s maximální pravděpodobností . 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. 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. Například následující silnější výsledek 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 < ) tak, že: (a) Cn má 2Rn kódových slov délky n (b) maximální pravděpodobnost chyby ^e(Cn) kódování Cn splňuje ^e(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á exponenciálně. Důkaz tohoto tvrzení přesahuje rámec přednášky. Cvičení 6.3 1. 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? 2. 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? 54 7. KAPACITA JAKO HRANICE SPOLEHLIVÉ KOMUNIKACE 55 7 Kapacita jako hranice spolehlivé komunikace 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řesné informace rychlostí vyšší nebo rovné než je C bitů za sekundu. Přesněji, dokážeme následující základní výsledek. 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 < ) tak, že: Cn má 2Rn kódových slov délky n a pravděpodobnost chyby e(Cn) kódování Cn konverguje k nule pro n . 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 . 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í lemmata. 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) = H(U, V, W) - H(W|U, V) - H(V) H(U, W|V), protože entropie je nezáporná. Ale zároveň H(U, W|V) = H(U, V, W) - H(V, W) + H(V, W) - H(V) = H(U|V, W) + H(W|V) H(U|V, W) + H(W), což se mělo dokázat. Lemma 7.3 Fanova nerovnost Buď C kód s M kódovými slovy {c1, . . . , 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), (3.25) kde qE = 1 - pE. 55 56 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM Důkaz. Definujme novou náhodnou proměnnou Z jakožto Z = 0 pokud X = Y 1 pokud X = Y. Je tedy speciálně entropie náhodné proměnné Z rovna H(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. Zejména tedy H(X|(Y, Z) = (y, 1)) log2(M - 1). a H(X|(Y, Z)) = y H(X|(Y, Z) = (y, 1)) P((Y, Z) = (y, 1)) log2(M - 1) y P((Y, Z) = (y, 1)) pE log2(M - 1). Položme pak U = X, V = Y a W = Z. Z lemmatu 7.2 máme Fanovu nerovnost. Důkaz věty 7.1 Předpokládejme, že takováto posloupnost kódů existuje. Uvažme pak náhodný vektor X, který nabývá hodnot v kódu Cn tak, že pokud položíme R = C + , > 0, máme H(X) = n(C + ). 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 n = n(C + ) - nC H(X|Y). Aplikujeme-li Fanovu nerovnost, pak z toho, že máme dle předpokladu 2n(C+) kódových slov, je n H(X|Y) H(pE, qE) + pE log (M - 1) H(pE, qE) + pEn(C + ), tj. n - H(pE, qE) n(C + ) 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. 56 7. KAPACITA JAKO HRANICE SPOLEHLIVÉ KOMUNIKACE 57 Problémy 3.1 1. V binárním symetrickém kanálu s pravděpodobností chyby > 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. 2. 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. 3. Nechť kód pro přenos binárním symetrickým kanálem, který má pravděpodobnost chyby > 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? 4. 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 CN = 1 + pN logpN + qN logqN , kde pN = 1 2 [1 - (q - p)N ], qN = 1 - pN . 5. Uvažme dva diskrétní kanály bez paměti o kapacitách C1 a C2 tak, že oba mají vstupní abecedu 1 a výstupní abecedu 2. Součinem kanálů je kanál, jehož vstupní abeceda je (2) 1 a výstupní abeceda (2) 2 , přičemž kanálové pravděpodobnosti jsou určeny vztahem p(y1y2|x1x2) = p1(y1|x1)p2(y2|x2), kde pi(yi|xi) je pravděpodobnost, že jsme obdželi řetězec yi, pokud jsme odeslali řetězec xi prostřednictvím i-tého kanálu. Dokažte, že kapacita C součinu kanálů je určena vztahem (Shannon 1957) C = C1 + C2. 6. Zdroj bez paměti S je spojen ke kanálu C1 o kapacitě C1 a výsledný výstup S1 je vstup ke kanálu C2 o kapacitě C2 (viz níže uvedený diagram). Ukažte, že platí I(S|S2) I(S|S2) a I(S|S2) I(S1|S2). 57 58 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM 58 Kapitola 4 Kódy opravující chyby 1 Kódování a odhady Připomeňme si následující předpoklady pro kódování. Zdroj vytváří zprávu, která sestává z posloupnosti zdrojových symbolů a tato zpráva je přenesena k příjemci přes kanál s možnou chybou. Přitom lze bez újmy na obecnosti předpokládat, že kanál má stejnou abecedu jak na vstupu tak na výstupu. Kód C nad abecedou je soubor posloupností symbolů ze , prvky z C se nazývají kódová slova . Budeme předpokládat, že všechna kódová slova mají stejnou délku. Takovéto kódy se nazývají blokové kódy a při jejich použití je dekódování podstatně snazší. Pokud mají kódová slova z C délku n a || = q, pak mluvíme o q-árním kódu délky n (binárním kódu, pokud q = 2). Zakódování zdrojové zprávy není nic jiného než přiřazení každé k-dlouhé sekvenci znaků nad zdrojovou abecedou jedno kódové slovo z C. Během samotného dekódování se přijatá sekvence rozčlení na bloky délky n a každý se zpracovává samostatně. Jelikož přijaté n-bloky mohou mít díky chybám při přenosu obecně jinou podobu než vysílaná kódová slova, musí dekodér rozhodovat, které slovo bylo vysláno. Pokud je kód dobře navržen, je pravěpodobnost špatného rozhodnutí mnohem menší než pravděpodobnost, že libovolný kódový znak je chybně přenesen. Proces rozhodování může být definován pomocí dekódovací tabulky. Kódová slova tvoří první řádek tabulky. Pokud jsme obdrželi kódové slovo, je logické předpokládat, že i stejné slovo bylo vysláno. Rozhodovací pravidlo pro zbylá možně přijatá slova je dáno rozdělením těchto slov do seznamů pod každým kódovým slovem, podle kterého se tato přijatá slova budou dekódovat. Tedy, každé slovo délky n nad abecedou se objeví v tabulce právě jednou. Definice. Buď u, v přirozená čísla. Řekneme, že kód C určí u chyb, jestliže, pokud každé kódové slovo změníme alespoň na jednom a ne více než u místech, nebude výsledný řetězec kódové slovo. Řekneme, že kód C určí právě u chyb, jestliže určí u chyb a neurčí u + 1 chyb. 59 60 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Řekneme, že kód C opraví v chyb, jestliže, pokud použijeme pravidlo minimální vzdálenosti, jsme schopni opravit alespoň v chyb a v případě, kdy se nebudeme moci rozhodnout, dostaneme na výstupu chybu v dekódování. Řekneme, že kód C opraví právě v chyb, jestliže opraví v chyb a neopraví v + 1 chyb. Dále budeme předpokládat, že abychom byli schopni zjistit chyby při přenosu, bude příjemce schopen zkontrolovat přijatý řetězec proti seznamu všech kódových slov. Pokud řetězec nebude na seznamu, příjemce ví, že nastala alespoň jedna chyba, ale není schopen zjistit kolik chyb skutečně nastalo. Zároveň by mělo být jasné, že pokud obdržené slovo nebude kódové slovo, bude podle pravidla minimální vzdálenosti zpátky dekódováno, ale příjemce neví, zda se skutečně jedná o odeslané slovo. Příjemce pouze ví, že, v případě kódu opravujícího v chyb a pokud nastane nejvýše V , pak dekódovací proces bude úspěšný. Příklad 1.1 Chceme vysílat čtyři znaky: a, b, c, d a zpráva bude přenášena pomocí binárního blokového kódu délky 5. Musíme tedy zvolit čtyři kódová slova, např. 11000 pro a, 00110 pro b, 10011 pro c a 01101 pro d. Dekódování musí zahrnout všech 25 = 32 binárních slov délky 5. Jedno takové dekódovácí pravidlo je na (obr.4.1). 11000 00110 10011 01101 11001 00111 10010 01100 11010 00100 10001 01111 11100 00010 10111 01001 10000 01110 11011 00101 01000 10110 00011 11101 11110 00000 01011 10101 01010 10100 11111 00001 Obrázek 4.1: Příklad kódové tabulky pro binární blokový kód délky 5. Konstrukce kódu a dekódovacího schématu z příkladu 1.1 opravuje ne více než jednu chybu. V tabulce je to vždy prvních 5 slov v seznamu pod kódovým slovem. U více chyb už nemáme jistotu, že dekódování proběhne správně. Například pokud by při přenosu bloku 11000 vznikly dvě chyby vedoucí k přijetí slova 11110 na výstupu kanálu, pak toto schéma chyby odstraní. Ovšem při obdržení 11011 bude toto slovo dekódováno chybně jako 10011. Označme dále Vn() množinu všech posloupností délky n nad abecedou a nazývejme prvky ze Vn() slova nebo vektory . Někdy budeme psát místo Vn() také Vn(q). Podobně jako v binárním případě je Hammingova vzdálenost d(x, y) mezi vektory x a y počet míst, ve kterých se x a y liší. Váha slova x = x1x2 xn je pak počet nenulových znaků slova x, tj. wt(x) = {d(x, 0) | kde 0 je slovo z n nul}. 60 1. KÓDOVÁNÍ A ODHADY 61 Definice. Buď x Zn r , 0. Sférou Sn,r (x) v Zn r se středem x a poloměrem rozumíme množinu Sn,r (x) = {y Zn r : d(x, y) }. Objemem sféry Sn,r (x) nazveme číslo Vn,r (x) = card({y Zn r : d(x, y) }), tj. počet řetězců délky n, které mají Hammingovu vzdálenost od x nejvýše . Pokud budou čísla n, r jasná ze souvislosti, budeme psát jednoduše S(x) a V(x). Platí pak Lemma 1.2 Objem sféry Sn,r (x) je určen vztahem Vn r (x, ) = k=0 n k (r - 1)k . Důkaz. Plyne z toho, že počet řetězců délky n, které mají Hammingovu vzdálenost od x právě k je přesně číslo n k (r - 1)k . Příklad 1.3 Hammingova vzdálenost slov 01110010 a 11110101 je 4 a váha slova 01110101 je 5. Dekódování podle principu minimální vzdálenosti znamená, že dekódujeme obdržený vektor y jako to kódové slovo c, které má minimální vzdálenost od y, pokud máme možný výběr, vybereme libovolně. Je-li tedy C kód, je minimální vzdálenost kódu C číslo d(C) = min d(ci, cj), kde je minimum bráno přes všechny navzájem různé dvojice kódových slov z C. Pojem minimální vzdálenosti je klíčový pojem pro hodnocení kódu; dobré kódy mají rozložená kódová slova tak, že jejich minimální vzdálenost je velká. Důvod důležitosti minimální vzdálenosti je jasný z následující věty. Věta 1.4 Má-li kód minimální vzdálenost d, lze opravit pomocí dekódování podle pravidla minimální vzdálenosti až 1 2 (d - 1) chyb. Důkaz. Položme v = 1 2 (d - 1) a uvažme v-sféru bodu x. To je množina Su(x) = {y : d(x, y) u}. Jsou-li x, z různá kódová slova, platí Sv(x) Sv(z) = . Tedy dekódování podle pravidla minimální vzdálenosti opraví až v chyb. 61 62 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Máme pak následující jednoduché tvrzení. Věta 1.5 Buďte u, v přirozená čísla. Pak kód C určí u (opraví v) chyb právě tehdy, když d(C) u + 1 (d(C) 2v + 1). Důkaz. První část tvrzení je jednoduché přeformulování definice kódu určujícíh u chyb. Pro druhou část tvrzení jsme ukázali ve větě 1.4 implikaci zprava doleva. Předpokládejme nyní, že C je kód opravující v chyb a že existují dvě různá kódová slova c a d tak, že d(c, d) = d(C) 2v. Budeme chtít dokázat, že za předpokladu, že jsme odeslali kódové slovo c a nastalo nejvýše v chyb, je přesto možné, abychom podle pravidla minimální vzdálenosti obdrželi buď chybové hlášení nebo dekódovali obdržené slovo nesprávně jako d. To pak bude spor s tím, že C opravuje v chyb. Nejdříve si uvědomme, že d(c, d) = d(C) v + 1. Jinak bychom totiž mohli převést c na d při nejvýše v chybách, které by zůstaly neopraveny. Můžeme pak předpokládat, že se c a d liší na prvních k = d(C) místech, přičemž v+1 k 2v (jinak provedeme permutaci souřadnic). Uvažme nyní obdržené slovo x, které se shoduje se slovem c na prvních k - v pozicích, dále se shoduje se slovem d na dalších v pozicích a shoduje se s oběma slovy c a d na posledních n - k pozicích, tj. x = x1 . . . xk-v shoduje se s c xk-v+1 . . . xk shoduje se s d xk+1 . . . xn shoduje se s oběma . Protože nutně d(c, x) = v, d(d, x) = k - v v, je buďto d(c, x) = d(d, x) (v tomto případě obdržíme chybové hlášení) nebo d(c, x) > d(d, x) (v tomto případě je x dekódováně nesprávně jako d). Definice. Pokud má kód C právě M kódových slov délky n a má minimální vzdálenost d, mluvíme o (n, M, d)-kódu. Pro pevné n působí parametry M a d navzájem proti sobě tak, že zvětšení M způsobí zmenšení d a naopak. Máme pak následující důsledek. D usledek 1.6 1. (n, M, d)-kód C opraví právě v chyb tehdy a jen tehdy, když d = 2v + 1 nebo d = 2v + 2. 2. Kód C má minimální vzdálenost u = d(C) tehdy a jen tehdy, když opraví právě 1 2 (u - 1) chyb. Poznamenejme nyní, že určení chyby a její oprava jdou proti sobě, takže nemůžeme naráz dosáhnout jejich maximální úrovně. Uveďme si to na jednoduchém příkladě. 62 1. KÓDOVÁNÍ A ODHADY 63 Příklad 1.7 Předpokládejme nyní, že kód C má minimální vzdálenost d. Je to tedy kód určující d - 1 chyb a opravující u = 1 2 (d - 1) chyb. Pokud použijeme C pouze pro určení chyb, je schopen určit až d - 1 chyb. Z druhé strany, pokud chceme na C opravit chybu, kdykoliv je to možné, pak je schopen opravit až v chyb, ale není schopen určit situaci, kdy nastalo více než v a méně než d chyb. Totiž, pokud nastalo více než v chyb, můžeme podle pravidla minimální vzdálenosti "opravit" přijatý řetězec na špatné kódové slovo a pak bude chyba nedetekovatelná. Máme pak následující definici. Definice. Uvažme následující strategii pro opravu/určení chyby. Buď u, v přirozená čísla. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost nejvýše v a existuje-li pouze jediné takové kódové slovo, budeme dekódovat x jako kódové slovo c. Pokud existuje více než jedno kódové slovo se stejnou minimální vzdáleností k x nebo má nejbližší kódové slovo vzdálenost větší než v, obdržíme na výstup chybové hlášení. Řekneme, že kód C zároveň opraví v chyb a určí u chyb, jestliže nastala alespoň jedna a nejvýše v chyb, výše popsaná strategie opraví tyto chyby a kdykoliv nastane alespoň v +1 a nejvýše u+v chyb, výše popsaná strategie nahlásí chybu. Věta 1.8 Kód C zároveň opraví v chyb a určí u chyb právě tehdy, když d(C) 2v + u + 1. Důkaz. Předpokládejme nejprve, že d(C) 2v + u + 1. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost nejvýše v a existuje-li alespoň jedno další takové kódové slovo d, máme 2v + u + 1 d(c, d) d(c, x) + d(x, d) 2v, což je spor. Nutně tedy máme, že pokud obdržíme slovo x a nejbližší kódové slovo c ke slovu x má vzdálenost nejvýše v, je toto kódové slovo jediné s touto vlastností a podle pravidla minimální vzdálenosti budeme správně dekódovat. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost alespoň v + 1 a nejvýše u + v, při použití výše uvedené strategie dostaneme chybové hlášení. Předpokládejme nyní, že C je kód opravující v chyb a určující u chyb. Nechť dále d(C) 2v + u. Nutně pak 2v +1 d(C). Víme, že existují dvě různá kódová slova c a d tak, že k = d (c, d) = d(C). Můžeme pak předpokládat, že se c a d liší na prvních k = d(C) místech, přičemž 2v + 1 k 2v + u (jinak provedeme permutaci souřadnic). Uvažme nyní obdržené slovo x, které se shoduje se slovem c na prvních v pozicích, dále se shoduje se slovem d na dalších k - v pozicích a shoduje se s oběma slovy c a d na posledních n - k pozicích, tj. x = x1 . . . xv shoduje se s c xv+1 . . . xk shoduje se s d xk+1 . . . xn shoduje se s oběma . 63 64 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Nutně pak d(c, x) = k - v, d(d, x) = v, v + 1 k - v v + u. Je-li tedy c odesláno a x je obdrženo, nutně je pak počet chyb při přenosu (tj. číslo k - v) mezi v + 1 a v + u, uvažovaná strategie by nám měla dát na výstupu chybové hlášení, ale místo toho nám dekóduje x nesprávně na d. Definice. (n, M, d)-kód C se nazývá maximální, pokud není obsažen v žádném větším kódu se stejnou minimální vzdáleností tj. není obsažen v žádném (n, M + 1, d)-kódu. Je zřejmé, že pro každý kód C můžeme vždy najít maximální kód C , který jej obsahuje. Přitom platí Věta 1.9 (n, M, d)-kód C je maximální právě tehdy, když pro všechna slova x existuje kódové slovo c s vlastností d(x, c) < d. Důkaz. (n, M, d)-kód C je maximální právě tehdy, když není obsažen v žádném (n, M+1, d)-kódu. Předpokládejme, že existuje slovo x tak, že pro všechna kódová slova c platí d(x, c) d. Položíme-li C = C{x}, je pak evidentně C (n, M+1, d)kód obsahující kód C. Obráceně, nechť pro všechna slova x existuje kódové slovo c s vlastností d(x, c) < d. Předpokládejme, že kód C není maximální tj. existuje (n, M + 1, d)kód obsahující kód C. Vyberme slovo x C - C. Pak ale existuje kódové slovo c C C tak, že d(C ) d(x, c) < d, spor. Poznamenejme, že pokud (n, M, d)-kód C není maximální, mohou nastat jak výhodné tak nevýhodné situace při jeho rozšíření na maximální kód C . Víme, že kód C rovněž opraví 1 2 (d - 1) chyb, což je dobré a přitom C může zakódovat více zdrojových symbolů, což je rovněž dobré. Ale zatímco C může být případně schopen opravit více než 1 2 (d - 1) chyb, kód C nebude nikdy schopen opravit více než 1 2 (d - 1) chyb. Příklad 1.10 Uvažme kód C = {00000, 11000}, který má minimální vzdálenost 2. Tento kód opravuje jednu chybu, ale je přitom schopen opravit další jiné chyby. Například, pokud bylo odesláno slovo 00000 a přijato slovo 00111, bude toto slovo správně dekódováno (totiž d(00000, 00111) = 3, d(11000, 00111) = 5), ačkoliv při přenosu nastaly tři chyby. Pokud ale doplníme C do maximálního kódu, bude dekódování chybné. Z výše uvedeného příkladu vyplývá, že maximální kódy jsou nejlepší, pokud nás u kódu pouze zajímá předem určená schopnost opravení chyby. Je tedy daleko obtížnější zkoumat pravděpodobnost chyby při dekódování u kódů, které nejsou maximální. Pro maximální kódy je to jednodušší. 64 2. EKVIVALENCE KÓDŮ A KONSTRUKCE NOVÝCH KÓDŮ 65 Věta 1.11 Buď C (n, M, d)-kód. Pak pro binární symetrický kanál s pravděpodobností chyby p je při použití dekódovacího pravidla minimální P(nastala chyba při dekódování) 1 - 1 2 (d-1) k=0 n k pk (1 - p)n-k . Je-li navíc kód C maximální, je n k=d n k pk (1 - p)n-k P(nastala chyba při dekódování). Důkaz. Každý (n, M, d)-kód C opravuje evidentně 1 2 (d-1) chyb. Je tedy pravděpodobnost správného dekódování alespoň tak velká jako je pravděpodobnost, že nastane nejvýše 1 2 (d - 1) chyb tj. P(správné dekódování) 1 2 (d-1) k=0 n k pk (1 - p)n-k . Máme pak P(nastala chyba při dekódování) = 1 - P(správné dekódování) 1 - 1 2 (d-1) k=0 n k pk (1 - p)n-k . Buď dále (n, M, d)-kód C maximální. Pak, je-li přeneseno slovo c a nastaneli d nebo více chyb, tj. d(c, x) d, bude nutně x bližší k jinému kódovému slovu d = c a tedy při použití pravidla minimální vzdálenosti nastane dekódovací chyba. Protože pravděpodobnost, že nastane právě k chyb při průchodem binárním symetrickým kanálem, je n k pk (1 - p)n-k , obdržíme následující dolní hranici pro pravěpodobnost dekódovací chyby n k=d n k pk (1 - p)n-k P(nastala chyba při dekódování), čímž je věta dokázána. 2 Ekvivalence kódů a konstrukce nových kódů Užitečným prostředkem pro redukci množství práce při nalezení dobrých kódů je pojem ekvivalence kódů. Předpokládejme, že máme (n, M, d)-kód C. Přirozeným 65 66 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY způsobem jeho prezentace je pomocí matice o rozměrech M × n, přičemž řádky jsou různá kódová slova. Předpokládejme nyní, že je permutace množiny {1, 2, . . . , n} a pro každé kódové slovo c C budeme aplikovat transformaci : C C definovanou předpisem (c) = (c(1), . . . , c(n)). Takovou transformaci nazýváme poziční permutací. Podobně, je-li permutace množiny , pak pro každý index i, 1 i můžeme aplikovat transformaci ^i : C C definovanou předpisem ^i(c)j = cj pokud i = j (ci) pokud i = j. Mluvíme pak o symbolové permutací. Lze-li kód C získat z kódu C pomocí konečné posloupnosti pozičních nebo symbolových permutací, říkáme že kód C je ekvivalentní kódu C. Příklad 2.1 Předpokládejme, že máme kód C délky 5 nad abecedou = {a, b, c} s kódovými slovy c1, c2, c3 a c4 tak, že C = c1 c2 c3 c4 a b c a c b a b a b b c c b a c b a c a . Aplikujeme-li permutaci (1 2, 2 3, . . . , 5 1), obdržíme poziční permutaci a k ní odpovídající ekvivalentní kód je C = c1 c2 c3 c4 c a b c a b b a b a a b c c b a c b a c . Podobně, aplikujeme-li permutaci (a b, b c, c a) na první sloupec kódu C , obdržíme symbolovou permutaci a k ní odpovídající ekvivalentní kód je C = c1 c2 c3 c4 a a b c a c b a b a b b c c b b c b a c . Lemma 2.2 Jsou-li C a C ekvivalentní kódy, jsou množiny vzdáleností kódových slov z C a C stejné. Důkaz. Protože jak poziční tak symbolová permutace zachovávají vzdálenost permutovaných slov, platí totéž i pro takovouto posloupnost permutací. 66 2. EKVIVALENCE KÓDŮ A KONSTRUKCE NOVÝCH KÓDŮ 67 Lemma 2.3 Je-li C kód délky n a u vektor délky n nad stejnou abecedou, pak existuje kód C , který je ekvivalentní s C a obsahuje vektor u. Důkaz. První kódové slovo c1 lze převést na u pomocí nejvýše n symbolových permutací. Definice. Buď x, y binární slova délky n. Průnik x y binárních slov x a y je binární řetězec délky n, který má jedničku přesně na těch místech, na kterých ji mají obě slova x a y. Všude jinde má pak nuly. Jinak řečeno, x y = x1 y1x2 y2 . . . xn yn. Platí pak následující jednoduché lemma. Lemma 2.4 Jsou-li x a y binární řetězce délky n, pak d(x, y) = w(x) + w(y) - 2w(x y). Důkaz. Položme A11 = {i : 1 i n, xi = yi = 1}, a11 = card(A11), A10 = {i : 1 i n, xi = 1, yi = 0}, a10 = card(A10), A01 = {i : 1 i n, xi = 0, yi = 1}, a01 = card(A01), A00 = {i : 1 i n, xi = 0, yi = 0}, a00 = card(A00). Pak platí d(x, y) = a10 + a01 = (a11 + a10) + (a11 + a01) - 2a11 = w(x) + w(y) - 2w(x y), čímž je lemma dokázáno. Definice. Postup, při kterém přidáme ke všem kódovým slovům z daného kódu jednu nebo více dodatečných pozic, a tedy zvýšíme délku kódu, se nazývá rozšíření kódu. Nejznámější metoda rozšíření kódu se nazývá kontrola parity. Pro jednoduchost uvažme binární případ. Je-li C binární (n, M, d)-kód, budeme konstruovat nový kód následovně. Ke každému kódovému slovu c = c1c2 . . . cn C přidáme dodatečný bit tak, že nové výsledné kódové slovo bude mít sudou váhu. Tedy, mělo-li c lichou váhu, přidáme jedničku, mělo-li c sudou váhu, přidáme nulu. Označíme-li tedy výsledné slovo jako c, máme c = c1c2 . . . cn0 pokud w(c) je sudá, c1c2 . . . cn1 pokud w(c) je lichá. Nový kód C má pak délku n + 1 a velikost M. Minimální vzdálenost kódu C bude buď d nebo d + 1 a toto číslo bude záviset na tom, zda bude d sudé nebo liché číslo. Totiž, protože všechna kódová slova v C mají sudou váhu, bude vzdálenost mezi každými dvěma slovy sudé číslo (to plyne z lemmatu 2.4). Je tedy 67 68 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY i minimální vzdálenost kódu C sudé číslo. Nutně pak dostáváme, že, je-li d(C) = d sudé číslo a nastává pro pro slova c, d, pak nutně mají obě slova stejnou paritu a tedy nutně platí d(c, d) = d(c, d). Je tedy d(C) = d(C). Nechť je minimální vzdálenost kódu C liché číslo a nastává pro pro slova c, d, pak nutně má jedno ze slov sudou paritu (například c) a druhé lichou paritu (d). Pak w(c) = w(c), w(d) + 1 = w(d), w(c d) = w(c d). Tedy d(C) + 1 = d(C). V obou případech pak máme 1 2 (d(C) - 1) = 1 2 (d(C) - 1) . Z toho pak plyne, že se nám při použití kontroly parity nezvýší schopnost opravit chybu. Obecně pak, máme-li kódovou abecedu vybránu tak, že nám tvoří konečné pole, řekněme Zp, kde p je prvočíslo, můžeme definovat kontrolu parity jako c = c1c2 . . . cncn+1, kde cn+1 = - n i=1 cn. Definice. Postup, při kterém odebereme ta kódová slova z daného kódu, která se liší na určené pozici i od určeného symbol s, a ze zbývajících slov tuto pozici odstraníme, a tedy zkrátíme délku kódu, se nazývá zkrácení kódu typu xi = s. Je-li pak C (n, M, d)-kód, má zkrácený kód C délku n-1 a minimální vzdálenost alespoň d. Opravdu, zkrácení kódu může mít za důsledek podstatné zvětšení minimální vzdálenosti tedy i schopnosti opravit nového kódu, protože můžeme odstranit ta kódová slova, která se "špatně chovají vzhledem ke vzdálenosti". Samozřejmě ale zkrácením kódu se nám zmenší i počet kódových slov, což není zrovna lákavé. Věta 2.5 Buď d liché přirozené číslo. Pak existuje binární (n, M, d)-kód právě tehdy, když existuje binární (n + 1, M, d + 1)-kód. Důkaz. Pokud existuje binární (n + 1, M, d + 1)-kód C, můžeme snadno zkonstruovat binární (n, M, d)-kód. Jednoduše vybereme dvě kódová slova c a d tak, že d(c, d) = d + 1, najděme pozici, na které se liší a odebereme tuto pozici z každého kódového slova. Nový kód označíme C . Nutně pak mají nová zkrácená slova c a d vzdálenost d(c , d ) = d a žádná jiná dvě slova nemají od sebe menší vzdálenost než d. Celkem je tedy C binární (n, M, d)-kód. Obráceně, předpokládejme, že máme binární (n, M, d)-kód D (d liché). Kód D, který vznikl jako kód kontroly parity z D, má délku n + 1, velikost M a minimální vzdálenost d + 1. 68 3. HLAVNÍ PROBLÉM TEORIE KÓDOVÁNÍ 69 3 Hlavní problém teorie kódování Definice. Buď dána přirozená čísla d, n, q. Položme Aq(n, d) jakožto maximální M takové, že existuje q-ární (n, M, d)-kód. Každý takový q-ární (n, M, d)-kód nazýváme optimální. Čísla Aq(n, d) hrají ústřední roli v teorii kódování a na jejich nalezení bylo vynaloženo velké úsilí. Často se mluví o hlavním problému teorie kódování. V dalším pro ilustraci určíme jisté hodnoty Aq(n, d) pro malé hodnoty n a d a dokážeme obecná tvrzení o těchto číslech. Poznamenejme, že abychom dokázali, že Aq(n, d) = K pro jisté přirozené číslo K, stačí ověřit, že Aq(n, d) K a následně najít vhodný q-ární (n, K, d )-kód C, kde d d . Pak totiž K Aq(n, d ) Aq(n, d). Věta 3.1 Je-li d sudé číslo, je A2(n, d) = A2(n - 1, d - 1). Důkaz. Plyne okamžitě z věty 2.5. Totiž pak nutně platí A2(n, d) A2(n-1, d- 1) a A2(n, d) A2(n - 1, d - 1). D usledek 3.2 Je-li d sudé číslo a existuje binární (n, M, d)-kód, pak existuje binární (n, M, d)-kód, ve kterém mají všechna kódová slova sudou váhu. Důkaz. Plyne okamžitě z věty 3.1. Totiž pak nutně existuje binární kód (n - 1, M, d - 1)-kód a pomocí operace kontroly parity existuje binární (n, M, d)-kód, ve kterém mají všechna kódová slova sudou váhu. Následující dva snadné výsledky nám budou ilustrovat, jakým způsobem můžeme určit hodnoty A2(n, d) pro malé hodnoty n a d. Použijeme přitom lemma 2.3, ze kterého plyne, že pro daný (n, M, d)-kód C existuje ekvivalentní (n, M, d)-kód C , který obsahuje nulové slovo (samozřejmě za předpokladu, že kódová abeceda obsahuje 0 ­ jinak ji lze dodat záměnou za jiný symbol). Můžeme tedy v dalším předpokládat, že naše kódy obsahují nulové slovo. Věta 3.3 Platí A2(4, 3) = 2. Důkaz. Buď C nějaký (4, M, 3)-kód. Můžeme bez újmy na obecnosti předpokládat, že 0 = 0000 C. Protože d(C) = 3, libovolné další kódové slovo c z C musí splňovat d(c, 0) 3 a tedy musí obsahovat alespoň tři jedničky. Máme tedy celkem pět možností pro nenulová slova ležící v C, a to 1110, 1101, 1011, 0111, 1111. Ale každá takováto dvě slova mají vzdálenost nejvýše 2 a tedy pouze jedno z nich může být obsaženo v C. Platí tedy A2(4, 3) 2. Dále platí, protože C = {0000, 1110} je (4, 2, 3)-kód, máme A2(4, 3) 2 a tedy celkem A2(4, 3) = 2. 69 70 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Věta 3.4 Platí A2(5, 3) = 4. Důkaz. Buď C nějaký (5, M, 3)-kód. Můžeme bez újmy na obecnosti předpokládat, že 0 = 0000 C a přitom pro vhodné c z C platí d(0, c) = 3, c1 = 0. Uvažme nyní zkrácení C typu x1 = 0. Víme pak, že 0 , c C a d(0 , c ) = 3. Dále víme, že A2(4, 3) = 2 a A2(4, 4) = A2(3, 3) = 2. Tedy i card(C ) = 2. Definuje nyní zkrácený kód C jakožto zkrácení typu typu x1 = 1. Pak buďto card(C ) = 1 nebo card(C ) > 1 a d(C ) = 3 a tedy nutně jako výše card(C ) = 2. Celkem tedy card(C ) + card(C ) = card(C) 4. Platí tedy A2(5, 3) 4. Dále platí, protože C = {00000, 11100, 00111, 11011} je (5, 4, 3)-kód, máme A2(5, 3) 4 a tedy celkem A2(5, 3) = 4. Věta 3.5 Platí následující: 1. Aq(n, d) qn pro všechna 1 d n; 2. Aq(n, 1) = qn ; 3. Aq(n, n) = q. Důkaz. První tvrzení platí, protože pro každý kód C je C Vn(q) tj. card(C) qn . Druhé tvrzení plyne z toho, že uvážíme-li C = Vn(q), máme d(Vn(q)) = 1. Třetí část plyne z toho, že se kódová slova musí lišit na všech pozicích a takových kódových slov můžeme vybrat nejvýše q. Ale máme, pro kód D = {0, . . . , q-1}, že D je (n, q, n)-kód. Už pro malé hodnoty q, n a d není velikost Aq(n, d) známa. Následující tabulka shrnuje většinu našich znalostí o A2(n, d). Poznamenejme, že problém určení A2(n, d) je problémem konečných geomet- rií. Pro odhad Aq(n, d) platí následující jednoduché tvrzení. Věta 3.6 Pro všechna n 2, Aq(n, d) qAr(n - 1, d). (4.1) Důkaz. Buď C kód realizující hodnotu Aq(n, d). Uvažme nyní zkrácení Cj typu xn = j. Pak nutně card(Cj) Aq(n-1, d) (mohou totiž nastat pouze dva případy: card(Cj) = 1, což evidentně platí, a K = card(Cj) > 1, kde pak Cj je (n-1, K, d )kód, d d a tedy tvrzení rovněž platí). Celkem pak C = q-1 j=0 Cj tj. Aq(n, d) = q-1 j=0 card(Cj) qAr(n - 1, d). Cvičení 3.7 1. Ukažte, že A2(3, 2) = 4. 70 4. DOLNÍ A HORNÍ HRANICE AQ(N, D); PERFEKTNÍ KÓDY 71 n d = 3 d = 5 d=7 5 4 2 - 6 8 2 - 7 16 2 2 8 20 4 2 9 40 6 2 10 72-79 12 2 11 144-158 24 4 12 256 32 4 13 512 64 8 14 1024 128 16 15 2048 256 32 16 2560-3276 256-340 36-37 Tabulka 4.1: Hodnoty A2(n, d) 4 Dolní a horní hranice Aq(n, d); perfektní kódy Určeme nejprve horní hranici (sphere-packing upper bound) čísla Aq(n, d). Lemma 4.1 Nechť e = 1 2 (d - 1) . Pak platí Aq(n, d) e k=0 n k (q - 1)k qn . (4.2) Důkaz. Buď C kód s minimální vzdáleností d; pak, je-li Se(x) koule o poloměru e se středem x, máme pro každou dvojici kódových slov x a y, že Se(x) Se(y) = . Ale je evidentní, že |Se(x)| = e k=0 n k (q - 1)k . (4.3) Pravá strana nerovnosti 4.2 je celkový počet slov délky n nad abecedou o q symbolech. Levá strana je počet prvků obsažených v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Maximální počet takovýchto různých kódových slov je Aq(n, d). Tedy dostáváme nerovnost 4.2. Podobně platí Lemma 4.2 (Gilbert-Varshamova hranice) Aq(n, d) d-1 k=0 n k (q - 1)k qn . (4.4) 71 72 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Důkaz. Buď C (n, M, d)-kód s maximálním počtem kódových slov. Pak zcela jistě neexistuje vektor z Vn(q) - C, jehož vzdálenost od všech kódových slov je alespoň d, jinak by totiž M nebyl maximální počet kódových slov. Jinak řečeno, koule o poloměru d musí pokrývat celý prostor Vn(q). Ale to je přesně podmínka 4.4. Definice. Poloměr pokrytí blokového kódu C je nejmenší poloměr takový, Fn q cC S(c). Poloměr pokrytí je další charakterizací kódů, nemá však tak hojné uplatnění jako minimální vzdálenost. Věta 4.3 Nechť C je blokový kód délky n. Pak je poloměr pokrytí kódu C právě tehdy, když = maxfFn q mincC d(c, f). Důkaz: Nechť Fn q cC S(c), kde je minimální. Pak pro každé f Fn q existuje c C takové, že d(c, f) , a současně existují f Fn q a c C splňující d(c , f ) = . Z minimality plyne, že = maxfFn q d(f, C) = maxfFn q mincC d(c, f). Naopak, nechť = maxfFn q mincC d(c, f) = maxfFn q d(f, C). Pak pro všechna f Fn q platí d(f, C) a existují f Fn q a c C splňující rovnost a pro všechna c C je d(c, f ). Předpokládejme, že existuje s, > s, takové, že každé f Fn q je prvkem množiny {x Fn q | d(c, x) s} pro nějaké c C. To je ale spor s existencí slov f a c , a tedy je poloměr pokrytí kódu C. Ideální situace z ekonomického pohledu je najít kód C nad Vn(q) tak, že pro jisté kladné t > 0 jsou všechny prvky z Vn(q) obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Takový kód se pak nazývá perfektní. Z jeho definice je zřejmé, že perfektní kód dokáže pomocí pravidla minimální vzdálenosti opravit až t chyb, a nedokáže opravit t + 1 chyb. Je tedy nutná podmínka pro to, aby (n, M, d)-kód byl perfektní, že d je liché číslo. Celkem tedy je (n, M, d)-kód perfektní právě tehdy, když M = Aq(n, d) a Aq(n, d) d-1 2 k=0 n k (q - 1)k = qn . (4.5) Příklad 4.4 Zřejmým příkladem perfektního kódu je 1. každý kód s právě jedním kódovým slovem, 2. každý binární kód s právě dvěma slovy lichých délek, např. 00 . . . 0 a 11 . . . 1. Tyto kódy se nazývají triviální perfektní kódy. 72 4. DOLNÍ A HORNÍ HRANICE AQ(N, D); PERFEKTNÍ KÓDY 73 Věta 4.5 (Singletonova hranice) Platí Aq(n, d) qn-d+1 . (4.6) Důkaz. Buď C nějaký (n, M, d)-kód. Pokud odstraníme posledních d - 1 pozic z každého kódového slova z C, musí být nutně výsledná zkrácená slova navzájem různá (jinak by původní slova musela mít vzdálenost d - 1). Ale počet všech slov délky n - (d - 1) je právě qn-d+1 tj. Aq(n, d) qn-d+1 . Lemma 4.6 Buď M přirozené číslo. Pak funkce f : {0, . . . , M} N definovaná jako f(k) = k(M - k) nabývá svého maxima pro k = M 2 pokud M je sudé M1 2 pokud M je liché a f(k) = M2 4 pokud M je sudé M2-1 4 pokud M je liché. Důkaz. Důkaz okamžitě plyne ze vztahu a b 1 2 (a + b) a z průběhu funkce f. Věta 4.7 (Plotkinova hranice) Je-li n < 2d, máme A2(n, d) 2 d 2d - n . (4.7) Důkaz. Buď C = {c1, . . . , cM } nějaký (n, M, d)-kód. Uvažme součet S = i d(y, c). To je ekvivalentní s tím, že d(0, z0) > d(y - c, 0) tj. w(z0) > w(y - c). Ale pak H(y - c) = Hy - Hc = Hy , protože c je kódové slovo. Zejména tedy má y - c stejný syndrom jako y, leží ve stejném kosetu a a má váhu ostře menší než je váha reprezentanta kosetu z0, což je spor. V dalším budeme předpokládat, že kódování a dekódování pro lineární [n, k]kód C = {c1, . . . , cM , c1 = 0 při přenosu binárním symetrickým kanálem s pravděpodobností chyby p bude probíhat pomocí následující tabulky 0 c2 c3 cM f2 f2 + c2 f2 + c3 f2 + cM f3 f3 + c2 f3 + c3 f3 + cM ... ... ... ... ... fs fs + c2 fs + c3 fs + cM Dále předpokládejme, že každý reprezentant fi příslušného kosetu má váhu wt(fi). Platí pak následující tvrzení. Označme, pro 1 j n, wj počet reprezentantů váhy j. Věta 7.4 Buď C binární lineární [n, k]-kód. Pak pravděpodobnost správného dekódování při přenosu binárním symetrickým kanálem je P(správné dekódování) = s i=1 pwt(fi) (1 - p)n-wt(fi) tj. P(správné dekódování) = n j=1 wjpj (1 - p)n-j . Důkaz. Protože reprezentant fi příslušného kosetu má váhu wt(fi), pravděpodobnost, že nám vznikne z c slovo d je stejná, že nám vznikne z 0 příslušný reprezentant fi tj. P(reprezentant je fi) = pwt(fi) (1 - p)n-wt(fi) . Posčítáme-li přes všechny reprezentanty, obdržíme požadované tvrzení. 81 82 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Nevýhody této kódovací metody lze nejlépe vidět na následujícím příkladu. Příklad 7.5 Předpokládejme, že C je binární kód, jehož generující matice G je určena následovně G = 1 0 1 0 0 1 1 1 . Pak kontrolní matice H má tvar H = 1 1 1 0 0 1 0 1 . Kódová slova kódu C jsou 0000, 1010, 0111, 1101. Příslušná prohlížecí tabulka má tvar Syndrom s Reprezentant z0 kosetu H, s = Hz0 00 0000 10 0010 01 0001 11 0100 . Předpokládejme tedy, že jsme obdrželi vektor y = 1111. Je ho syndrom je vektor Hy = 10. Odpovídající reprezentant je 0010, je tedy slovo 1111 dekódováno jakožto 1101. Poznamenejme, že tato prohlížecí tabulka není určena jednoznačně, například za reprezentanta syndromu 10 lze vzít vektor 1000. V případě binárního [n, k]-kódu máme právě |Vn|/|C| = 2n-k (obecně pak qn-k ) různých kosetů; zejména tedy bude mít prohlížecí tabulka v Kroku 1(b) právě 2n-k různých položek. Prohledávání takovéto tabulky je pro velká k, n velmi náročné. Avšak ostatní výhody této metody opravňují její široké používání. 8 Binární Hammingovy kódy Abychom ilustrovali dříve uvedené techniky, uvažme následující příklad. Omezme naši pozornost na binární příklad; buď r nějaké kladné celé číslo a položme n = 2r - 1. Dále definujme kontrolní matici H jakožto matici typu r × (2r - 1), jejíž sloupce tvoří všechny navzájem různé nenulové vektory z Vr. Pak H je kontrolní matice binárního [n, k]-kódu, kde n = 2r - 1, k = n - r. Mluvíme pak o Hammingově [n, k]-kódu . Klíčovou vlastnost Hammingových kódů lze zformulovat v následující větě. 82 8. BINÁRNÍ HAMMINGOVY KÓDY 83 Věta 8.1 Každý Hammingův kód je perfektní kód opravující jednu chybu. Důkaz. Nejprve ukažmě, že minimální vzdálenost každého Hammingova kódu je alespoň 3. Protože C je lineární kód, je minimální vzdálenost d(C) rovna minimální váze vektorů z C. Předpokládejme nejprve, že C má kódové slovo u váhy 1 s nenulovým vstupem v i-té souřadnici. Pak platí Hu = 0, tj. i-tý sloupec hi matice H je nulový, což není z definice matice H možné. Předpokládejme dále, že C má kódové slovo v váhy 2 s nenulovými vstupy v i-té a j-té souřadnicích. Pak platí Hv = 0, tj. hi + hj = 0. Protože pracujeme s binárními kódy, je nutně hi = hj, což není možné. je tedy d(C) 3. Ukažme, že C je perfektní. Poznamenejme, že každá 1-koule kolem kódového slova bude obsahovat právě 1 + n = 2r vektorů délky n = 2r - 1. Protože C obsahuje právě 2k = 2n-r kódových slov, disjunktní sjednocení těchto 1-koulí je právě celá množina Vn vektorů délky n, jichž je právě 2n = 2n-r 2r . Důležitým důsledkem perfektnosti Hammingových kódů je, že 1. Pro Hammingův [n, k]-kód jsou reprezentanti kosetů vektory z Vn váhy 1. To vede k následujícímu elegantnímu dekódovacímu algoritmu pro Hammingovy kódu. Nejprve poznamenejme: 2. Sloupce matice H lze přemístit tak, že j-tý sloupec matice H je právě binární reprezentace čísla j. Je-li obdržen vektor y, spočtěme jeho syndrom Hy a předpokládejme, že reprezentuje číslo j. Předpokládáme-li pouze jednu chybu, pravidlo minimální vzdálenosti (=pravidlo maximální pravděpodobnosti) nám dává: (a) Pokud j = Hy = 0, pak nepředpokládáme žádnou chybu a y je kódové slovo. (b) Pokud j = Hy = 0, pak předpokládáme chybu v j-té pozici a dekódujeme y jeho změnou v j-té pozici. 83 84 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Příklad 8.2 Hammingův [7, 4]-kód má matici kontroly parity H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 . Předpokládejme, že jsme obdrželi vektor y = (1, 0, 1, 0, 1, 1, 0). Pak Hy = (001). Tedy za předpokladu, že nenastala více než jedna chyba, předpokládáme, že se chyba vyskytla na prvním místě a dekódujeme pak y jakožto y , y = (0, 0, 1, 0, 1, 1, 0). Cvičení 8.3 1. Napište matici kontroly parity binárního [15, 11, 3]-kódu. Jak bychom dekódovali obdržené vektory: (a) (100000000000000), (b) (111111111111111)? 9 Cyklické kódy Diskutujme nyní důležitou skupinu lineárních kódů. Kód C se nazývá cyklický, jestliže platí následující podmínky: 1. C je lineární, 2. pokud vektor w = (w1, . . . , wn) C, pak i vektor w = (wn, w1, . . . , wn-1) C. Tyto kódy mají atraktivní algebraické vlastnosti a můžeme je snadno sestrojit pomocí lineárních posouvacích registrů (blíže viz [7]). Budeme dále pracovat pouze v binárním případě a během tohoto paragrafu budeme identifikovat vektor w = (w1, . . . , wn) s polynomem w(x) = w1 + w2x + w3x2 + . . . + wnxn-1 . Dále budeme počítat pouze v okruhu Rn binárních polynomů stupně nejvýše n - 1 modulo polynom xn - 1. Tedy Rn se skládá z polynomů stupně n - 1 s koeficienty 0 a 1 tak, že platí následující pravidla pro sčítání a násobení polynomů: a(x) + b(x) = n-1 i=0 (ai + bi)xi a(x) b(x) = a(x)b(x) mod (xn - 1). 84 9. CYKLICKÉ KÓDY 85 Základním pozorováním je následující skutečnost: posunu v kódovém slově odpovídá násobení odpovídajícího polynomu monomem x v okruhu Rn. Totiž w(x) x = w1x + w2x2 + w3x3 + . . . + wn-1xn-1 + wnxn mod (xn - 1) = w1x + w2x2 + w3x3 + . . . + wn-1xn-1 + wnx0 . Platí pak následující lemma Lemma 9.1 Je-li w(x) polynomiální reprezentace kódového slova w C, je i w(x)f(x) kódové slovo pro každý polynom f stupně nejvýše n - 1. Důkaz. Protože w(x) C, je i xw(x) C (posunutí o 1 místo doprava). Nutně tedy pro každé přirozené číslo k platí, že xk w(x) C. Ale protože je C lineární kód, je i libovolná lineární kombinace kódových slov tvaru xk w(x) opět v C, zejména tedy je polynom f(x)w(x) v C. Lemma 9.2 Je-li g(x) nenulový polynom minimálního stupně v C, pak g(x) generuje kód C v tom smyslu, že každé kódové slovo w(x) C je tvaru w(x) = f(x)g(x) pro vhodný polynom f(x). Důkaz. Předpokládejme, že existuje w(x) C, které nelze napsat ve výše uvedeném tvaru. Pak lze psát w(x) = q(x)g(x) + r(x), kde r(x) je zbytek po dělení polynomem g(x) tj. jeho stupeň je menší než stupeň polynomu g(x). Ale nutně q(x)g(x), w(x) C tj. r(x) C tj. nutně je r(x) nulový polynom, spor. Tedy je každý polynom z C násobkem g(x). Mluvíme pak o polynomu g(x) jakožto o generujícím polynomu kódu C. Tím pak dostaneme velmi dobrou reprezentaci kódu C. Připomeňme dále, že cyklický kód není nic jiného než ideál v okruhu polynomu a 9.2 plyne bezprostředně z toho, že každý ideál v okruhu polynomů je hlavní ideál. Příklad 9.3 Předpokládejme, že n = 3 a násobení je prováděno modulo polynom x3 - 1. Pak kód C = {0, 1 + x, x + x2 , 1 + x2 } je cyklický a generován polynome 1 + x. Standardní reprezentace kódu C sestává z vektorů {(0, 0, 0), (1, 1, 0), (0, 1, 1), (1, 0, 1)}. 85 86 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Lemma 9.4 Je-li C cyklický kód délky n s generujícím polynomem g(x) = g1 + g2x + . . . + gkxk-1 , pak jeho generující matice typu (n - k + 1) × n má tvar G = g1 g2 g3 . . . gk 0 0 . . . 0 0 g1 g2 . . . gk-1 gk 0 . . . 0 0 0 g1 . . . gk-2 gk-1 gk . . . 0 ... ... ... ... ... ... ... ... ... 0 0 . . . . . . . . . . . . gk-2 gk-1 gk . Důkaz. Evidentně, řádky matice G jsou lineárně nezávislé. Ukažme, že každé kódové slovo lze reprezentovat pomocí těchto řádků. Je-li tedy c = (c0, c1, . . . , cn-1) kódové slovo, je odpovídající polynom c(x) = c0 + c1x + . . . + cn-1xn-1 tvaru c(x) = g(x)f(x) (mod(xn - 1)) pro jistý polynom f stupně nejvýše n - 1. Ale to neznamená nic jiného, než že c(x) = n-1 i=0 fixi g(x) (mod(xn - 1)); tj. položíme-li g(i) (x) = xi g(x) a je-li g(i) odpovídající reprezentace polynomu g(i) (x) (i + 1-ní řádek matice G), máme c = n-1 i=0 fig(i) . Lemma 9.5 Je-li g generující polynom cyklického kódu délky n C, pak g dělí polynom (xn - 1). Důkaz. Předpokládejme, že tomu tak není. Můžeme pak psát xn - 1 = g(x)q(x) + r(x), kde r(x) je nenulový polynom se stupněm menším než je stupeň g. Protože q(x)f(x) C a r = -qg v tomto okruhu, plyne z linearity, že i r je kódové slovo, tj. se nemůže jednat o polynom minimálního stupně a tedy r = 0, spor. Lemma 9.6 Je-li dán polynom p stupně < n, pak množina všech polynomů C = {qp(mod(xn - 1)) : q je polynom stupně < n} je cyklický kód délky n. Důkaz. Evidentně, C je lineární kód. Zároveň, je-li qp C, je i xqp C tj. C je cyklický kód. 86 10. MARINERŮV KÓD A REED-MULLEROVY KÓDY 87 Lemma 9.7 Je-li g generující polynom stupně k cyklického kódu délky n C, pak polynom p stupně menšího než n je kódové slovo tehdy a jen tehdy, když p(x)h(x) = 0 (mod(xn - 1)), kde h je polynom stupně n - k splňující g(x)h(x) = (xn - 1) z Lemmatu 9.5. Polynom h pak nazýváme kontrolní polynom kódu C. Důkaz. Je-li c(x) kódové slovo, pak dle Lemmatu 9.2 platí c(x) = f(x)g(x) pro vhodný polynom f(x). Tudíž c(x)h(x) = f(x)g(x)h(x) = f(x)(xn - 1)) = 0 (mod(xn - 1)). Obráceně, předpokládejme, že p je nenulový polynom splňující p(x)h(x) = 0 (mod(xn - 1)). Pak p musí být stupně alespoň k. Nechť p(x) = g(x)q(x) + r(x), kde r(x) je polynom se stupněm menším než je stupeň g. Protože p(x)h(x) = 0 (mod(xn -1)) g(x)q(x)h(x) = 0 (mod(xn -1)), musí být i r(x)h(x) = 0 (mod(xn - 1)). Ale stupeň r(x)h(x) je menší než n. Tedy r(x)h(x) = 0 tj. i r(x) = 0. Je tedy i p(x) = g(x)q(x) C. 10 Marinerův kód a Reed-Mullerovy kódy V tomto odstavci se budeme věnovat dalším dvěma příkladům, kdy pomocí klasické moderní algebry byly zkonstruovány a vyvinuty nové třídy kódů. 10.1 Hadamardovy kódy Kódování R(1, 5) použité v roce 1969 kosmickým korábem Mariner 9 pro přenos fotografií z Marsu je speciálním případem následujících obecných kódů. Nejprve si připomeňme některé pojmy z moderní algebry. Hadamardova matice je matice H typu n × n, jejíž koeficienty jsou buď +1 nebo -1 tak, že HHT = nEn, (4.12) kde En je jednotková matice typu n × n. Jsou-li dále A a B čtvercové matice typu m × m a n × n, definujeme jejich Kroneckerův součin jako matici A B typu mn × mn A B = a11B a12B . . . a1mB ... ... ... am1B am2B . . . ammB . (4.13) Přímým výpočtem pak snadno dokážeme: 87 88 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY Lemma 10.1 Jsou-li H1 a H2 Hadamardovy matice, je jejich Kroneckerův součin H1 H2 Hadamardova matice. Důkaz. Počítejme G = (H1 H2)(H1 H2)T . Pak gij, i = i + n (^i - 1), j = j + n (^j - 1). Zejména gij = m l=1 a^ila^jl( n k=1 bikbjk). Pokud i = j, je nutně ^i = ^j a i = j a tedy i gii = m l=1 a^ila^il( n k=1 bikbik). Ale n k=1 bikbik = n a tedy gii = m l=1 a^ila^iln = mn. Nechť tedy i = j. Pak buď i = j nebo ^i = ^j. Nechť například ^i = ^j. Pak gij = ( m l=1 a^ila^jl)( n k=1 bikbjk) = 0( n k=1 bikbjk) = 0.. Nechť tedy i = j. Podobně, gij = ( m l=1 a^ila^jl)( n k=1 bikbjk) = ( m l=1 a^ila^jl)0 = 0. Začneme-li tedy s nejmenší netriviální Hadamardovou maticí H2 = 1 1 1 -1 , můžeme postupně iterovat Kroneckerovým součinem, abychom obdrželi posloupnost Hadamardových matic s exponenciálně rostoucím typem. Chceme-li pak tuto posloupnost použít pro účely kódování, předpokládejme, že H je Hadamardova matice rozměru n × n, přičemž n je sudé. Definujme pak A jakožto matici typu 2n × n A = H -H . Pak definujme M jakožto matici, kterou získáme z matice A tak, že nahradíme každý výskyt -1 v A číslem 0. Snadno se ověří následující tvrzení Lemma 10.2 Hadamardovo kódování 1. Jsou-li x a y dva různé řádky matice M, je pak vzdálenost d(x, y) vektorů x a y rovna číslu n 2 nebo n. 2. Řádky matice M tvoří binární (n, 2n, n 2 )-kód. Důkaz. Snadné cvičení. Totiž, vezmeme-li 2 různé řádky vzniklé z H, nutně je počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. d(x, y) = n 2 . Podobně, vezmeme-li 2 různé řádky, z nichž jeden vznikl z H a druhý z -H a zároveň oba z různých vektorů z H, je nutně opět počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. opět d(x, y) = n 2 . Případ, kdy oba řádky vznikly ze stejného vektoru, nám dává vzdálenost rovnu n. Poslední případ, kdy oba řádky vznikly z -H, se převede na první případ. Zbývající část tvrzení je triviální. Provedeme-li výše uvedené pětkrát za sebou na matici H2, obdržíme n = 32 a to je přesně kódování použité Marinerem. Kódy získané výše uvedeným postupem se nazývají Hadamardovy kódy. 88 10. MARINERŮV KÓD A REED-MULLEROVY KÓDY 89 10.2 Reed-Mullerovo kódování Tato prakticky důležitá třída kódů byla objevena I.S. Reedem a D.E. Mullerem v roce 1954. Abychom mohli popsat tyto kódy, budeme nejprve prezentovat jednoduchý způsob zkonstruování nových kódování ze starých původních. Lemma 10.3 Je-li dán (n, M1, d1) binární kódování C1 a jiné (n, M2, d2) binární kódování C2, můžeme pak definovat třetí binární kódování C3 = C1 C2 jakožto C3 = {(u, u + v) : u C1, v C2}. Přitom C3 je (2n, M1M2, d3)-kód, kde d3 = min{2d1, d2}. (4.14) Důkaz. Totiž délka kódových slov v C3 je nutně 2n a snadno se ověří, že jich je právě M1M2. To plyne z toho, že pokud (u1, u1 + v1) = (u2, u2 + v2) je nutně u1 = u2 a tedy i v1 = v2. Takovýchto uspořádaných dvojic (u, v) je právě M1M2. Zbývá ověřit, že minimální délka kódování C3, kterou značíme d3, je rovna min{2d1, d2}. To je ale zřejmé. Totiž, je-li (u1, u1 +v1) = (u2, u2 +v2), pak mohou nastat následující případy 1. u1 = u2: pak d(v1, v2) = d((u1, u1 + v1), (u2, u2 + v2)) d2. 2. v1 = v2: pak d(u1, u2) + d(u1, u2) = d((u1, u1 + v1), (u2, u2 + v2)) 2d1. 3. v1 = v2 a v1 = v2: pak označíme-li In = {i : i(u1) = i(u2)}, Ie = {i : i(u1) = i(u2)}, Jn = {i : i(v1) = i(v2)}, Je = {i : i(v1) = i(v2)}, je d((u1, u1+v1), (u2, u2+v2)) = |In|+|JeIn|+|JnIe| = |Jn|+2|JeIn| d2. Přitom v prvním a druhém případě může pro vhodně vybrané dvojice nastat rovnost, tj. tvrzení platí. Definujme nyní rekurzivně Reed-Mullerův kód C(r, m) předpisem: Pro všechna nezáporná celá čísla m a r taková, že 0 r m, definujeme C(r, m) jakožto kód délky n = 2m takový, že C(0, m) = {0, 1}, (4.15) kde 0 = (0, 0, . . . , 0) a 1 = (1, 1, . . . , 1), C(m, m) je množina všech binárních vektorů délky n = 2m tj. C(m, m) = 22m a C(r + 1, m + 1) = C(r + 1, m) C(r, m) (4.16) 89 90 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY pro r < m. Můžeme pak tyto kódy konstruovat následovně: m = 1 C(0, 1) = {00, 11} C(1, 1) = {00, 01, 10, 11} m = 2 C(0, 2) = {0000, 1111} C(1, 2) = C(1, 1) C(0, 1) = {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111} atd. Aplikujeme-li nyní lemma 10.3, obdržíme následující větu: Věta 10.4 Pro všechna nezáporná celá čísla m a r taková, že 0 r m je Reed-Mullerův C(r, m) binární kód charakteristiky (nr, Mr, dr), kde 1. Mr = 2a , kde a = r i=0 m i = 1 + m 1 + . . . + m r , 2. nr = 2m , 3. dr = 2m-r . Důkaz. Důkaz povedeme indukcí vzhledem k definici C(r, m). Totiž pro C(0, m) = {0, 1} je počet slov M0 roven dvěma a protože zároveň nutně a = 1, první část tvrzení pro C(0, m) platí. Protože délka nr vektorů je dle definice 2m , platí druhá část tvrzení. Protože kód obsahuje pouze dva vektory, které se liší na nr = 2m místech, je vzdálenost kódu rovna nr = 2m-0 = dr. Uvažme nyní kód C(m, m), což je množina všech binárních vektorů délky n = 2m = nm. Je tedy v našem případě a = n a tedy i Mm = 2a .Vzdálenost kódu je pak nutně 1 = 2m-m . Věnujme se nyní případu C(r + 1, m + 1) = C(r + 1, m) C(r, m). Z indukčního předpokladu a lemmatu 10.3 víme, že Mr+1 = 2 r+1 i=0 m i 2 r i=0 m i = 2 r+1 i=0 m i + r i=0 m i = 2 r+1 i=0 m i . Dále víme, že nr+1 = 2 2m = 2m+1 a dr+1 = min{2 2m-r-1 , 2m-r } = 2m-r = 2m+1-(r+1) . Problémy 4.1 1. Ukažte, že pokud platí (a) 2k d-2 i=0 n - 1 i < 2n , pak existuje binární lineární [n, k]-kód s minimální vzdáleností alespoň d. Tudíž odvoďte, že (a) 2k A2(n, d), 90 10. MARINERŮV KÓD A REED-MULLEROVY KÓDY 91 kde k je největší přirozené číslo splnující nerovnost (1). Návod: Zkonstruujte matici H typu (n - k) × n, takovou, že její hodnost je nejvýše d - 2. 2. Ukažte, že je-li H Hadamardova matice řádu n, je nutně n = 1, 2 nebo je n násobek 4. Poznamenejme, že existuje hypotéza, že pokud n je násobek čtyř, existuje Hadamardova matice řádu n. 91 92 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY 92 Dodatek A Náhodné jevy a náhodné veličiny Tento dodatek obsahuje základní pojmy nutné pro pochopení probírané látky. Je založen na skriptech [4]. 1 Měřitelný prostor a vztahy mezi náhodnými jevy Neprázdnou množinu možných výsledků náhodného pokusu značíme a nazýváme ji základní prostor . Možné výsledky náhodného pokusu značíme t, t T, kde T je indexová množina. Systém podmnožin A základního prostoru , který 1. obsahuje základní prostor, 2. s každými dvěma množinami obsahuje i jejich rozdíl, 3. obsahuje-li každou ze spočetné posloupnosti množin, obsahuje i jejich sjed- nocení se nazývá jevové pole . Poznamenejme, že má-li základní prostor alespoň dva prvky, není jevové pole uvedenými třemi axiomy určeno jednoznačně. Je-li A A, řekneme, že A je náhodný jev vzhledem k jevovému poli A. Dvojici (, A) nazveme měřitelný prostor , množinu pak nazveme jistý jev, množinu nemožný jev. Prvek nazveme elementární jev. Nechť I je libovolná neprázdná indexová množina. Pak iI Ai značí společné nastoupení náhodných jevů Ai, i I a iI Ai značí nastoupení alespoň jednoho z náhodných jevů Ai, i I. Ai = - Ai značí opačný náhodný jev k náhodnému jevu Ai, i I. Přitom to, že Ai, i I znamená, že možný výsledek je příznivý jevu Ai. Nechť i, j I. Pak Ai - Aj znamená nastoupení jevu Ai za nenastoupení jevu Aj, Aj Ai znamená, že náhodný jev Aj má za důsledek náhodný jev Ai a Ai Aj = znamená, že náhodné jevy Ai a Aj jsou neslučitelné. 93 94 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY 2 Pravděpodobnostní prostor Nechť (, A) je měřitelný prostor. Pravděpodobností rozumíme reálnou množinovou funkci P : A R, která je 1. nezáporná (pro všechna A A je P(A) 0), 2. spočetně aditivní ( i=1 j=i+1Ai Aj = = P( i=1 Ai) = i=1 P(Ai)), 3. normovaná (P() = 1). Trojice (, A, P) se nazývá pravděpodobnostní prostor. Za předpokladu, že A = {, }, není pravděpodobnost P uvedenými třemi axiomy jednoznačně ur- čena. 3 Klasická pravděpodobnost Nechť základní prostor je konečná neprázdná množina a nechť jevové pole A obsahuje všechny podmnožiny základního prostoru tj. A = 2 . Označme m() = || počet všech možných výsledků a pro libovolný jev A A označme m(A) = |A| počet možných výsledků příznivých jevu A. Pak reálnou funkci P : A R definovanou pro všechna A A vztahem P(A) = m(A) m() nazveme klasická pravděpodobnost. Všem elementárním jevům pak přiřazujeme stejnou pravděpodobnost 1 m() . Není-li tato podmínka splněna, nelze klasickou pravděpodobnost použít. Věta 3.1 Buďte A1, . . . , An A libovolné náhodné jevy. Pak platí P( n i=1 Ai) = n i=1 P(Ai) - 1i 0. Pak platí P(A1. . .An) = P(A1)P(A2|A1)P(A3|A1A2). . .P(An|A1A2. . .An-1). Nechť (, A, P) je pravděpodobnostní prostor a nechť je dán rozklad (Hi : i I) základního prostoru na nejvýše spočetně mnoho jevů Hi o nenulových pravděpodobnostech P(Hi). Říkáme, že je dán úplný systém hypotéz. Potom 1. pro libovolný jev A A platí formule úplné pravděpodobnosti: P(A) = iI P(Hi) P(A|Hi), 2. pro náhodný jev A s nenulovou pravděpodobností a pro libovolný jev Hk z úplného systému hypotéz platí 1. Bayesův vzorec: P(Hk|A) = P(Hk) P(A|Hk) iI P(Hi) P(A|Hi) , 3. pro náhodný jev A s nenulovou pravděpodobností a pro libovolný jev B A platí 2. Bayesův vzorec: P(B|A) = iI P(Hi) P(A|Hi) P(B|A Hi) iI P(Hi) P(A|Hi) . Použití 1. Bayesova vzorce: V souladu s textem úlohy stanovíme jevy Hi, i I, které se navzájem vylučují a přitom vyčerpávají všechny možnosti. Jeden z nich musí být náhodný jev, jehož pravděpodobnost nás zajímá. Jev, o němž je v úloze řečeno, že skutečně nastal, označíme A. Pak pro i I vypočteme apriorní pravděpodobnosti P(Hi) a podmíněné pravděpodobnosti P(A|Hi). Dosazením do 1. Bayesova vzorce vypočteme aposteriorní pravděpodobnost P(Hk|A). Použití 2. Bayesova vzorce: Stanovíme opět úplný systém hypotéz Hi, i I. Jev, který skutečně nastal, označíme A a náhodný jev, na jehož pravděpodobnost se ptáme, označíme B. Pak pro i I vypočteme apriorní pravděpodobnosti P(Hi) a podmíněné pravděpodobnosti P(A|Hi) a P(B|AHi). Dosazením do 2. Bayesova vzorce dostaneme pravděpodobnost P(B|A). Charakteristický znak, který odlišuje úlohy vedoucí na 1. Bayesův vzorec od úloh vedoucích na 2. Bayesův vzorec spočívá v tom, že v prvním případě se ptáme na pravděpodobnost jevu, který je totožný s jednou z hypotéz, kdežto ve druhém případě se ptáme na pravděpodobnost jevu, který je zcela nový a nesouvisí s ostatními jevy v úloze popsanými. 95 96 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY 5 Stochasticky nezávislé náhodné jevy Nechť (, A, P) je pravděpodobnostní prostor. Řekneme, že náhodné jevy A1, A2, . . . , An jsou stochasticky nezávislé vzhledem k pravděpodobnosti P, jestliže platí multiplikativní vztahy: i < j : P(Ai Aj) = P(Ai) P(Aj) i < j < k : P(Ai Aj Ak) = P(Ai) P(Aj) P(Ak) . . . P(A1 . . . An) = P(A1) . . . P(An). Definici lze rozšířit i na spočetnou posloupnost jevů: Řekneme, že jevy A1, A2, . . . , Ak, . . . A jsou stochasticky nezávislé vzhledem k pravděpodobnosti P, jestliže pro všechna přirozená n jsou stochasticky nezávislé náhodné jevy A1, A2, . . . , An. Ověřujeme-li stochastickou nezávislost náhodných jevů, musíme prozkoumat platnost všech multiplikativních jevů. Je-li v textu úlohy řečeno, že jevy jsou stochasticky nezávislé a máme-li stanovit pravděpodobnost nastoupení alespoň jednoho z těchto jevů, využijeme de Morganova pravidla a počítáme P( n i=1 Ai) = P( n i=1 Ai) = 1 - P( n i=1 Ai) = 1 - n i=1 (1 - P(Ai)). 6 Borelovské množiny a náhodné veličiny Nechť n je přirozené číslo. Množinu Rn nazýváme n-rozměrným prostorem a množinu R = RN nazýváme spočetně rozměrným prostorem. Minimální jevové pole na Rn obsahující třídu všech intervalů (-, x1] × (-, x2] × . . . × (-, xn] pro (x1, x2, . . . , xn) Rn , nazýváme n-rozměrným borelovským polem B(n) a prvky tohoto pole nazýváme n-rozměrnými borelovskými množinami. Podobně pro spočetné borelovské pole B() . Mezi borelovské množiny patří zejména prázdná množina, celý konečně rozměrný popř. spočetně rozměrný prostor, všechny jednobodové, konečné resp. spočetné množiny, všechny intervaly, všechny otevřené i uzavřené oblasti a všechna nejvýše spočetná sjednocení takových množin. Kartézský součin borelovských množin je opět borelovská množina, ale vyšší dimenze. Zobrazení X : R se nazývá náhodná veličina vzhledem k jevovému poli A, jestliže B B : { : X() B} = X-1 (B) A, tj. úplný vzor každé borelovské množiny je náhodným jevem. 96 7. NÁHODNÉ VEKTORY 97 Obraz X() se nazývá číselná realizace náhodné veličiny X příslušná k možnému výsledku . Jestliže nehrozí nebezpečí nedorozumění, zapisujeme náhodnou veličinu i její realizaci týmž symbolem X. Množinu { : X() B} zkráceně zapisujeme {X B}. Víme, že každá množina typu {X B} (kde B B(n) ) je jevem. Ve speciálním případě B = {x} nebo B = (-, x] píšeme jednodušeji {X = x} {X x}. Podmínky mohou být vyjadřovány logickými spojkami negace, konjunkce, disjunkce a implikace. Jim odpovídají množinové operace komplement, průnik, sjednocení a relace množinové inkluze. Zápis odpovídající pravděpodobnosti zkrátíme takto: P({ : X() B}) := P(X B), což je pravděpodobnost, že náhodná veličina X se realizuje v množině B; P({ : X() B}|{ : Y () C} := P(X B|Y C), což je pravděpodobnost, že náhodná veličina X se realizuje v množině B za podmínky, že náhodná veličina Y se realizuje v množině C. Funkce : R R definovaná vztahem x R : (x) = P(X x) se nazývá distribuční funkce náhodné veličiny X vzhledem k pravděpodobnosti P. Náhodná veličina X se nazývá diskrétní, jestliže existuje funkce (x) nulová v R s výjimkou nejméně jednoho a nejvýše spočetně mnoha bodů, kde je kladná (vlastnost D1: pro všechna x R je (x) 0), je normovaná (vlastnost D2: x=- (x) = 1, kde se sčítají jen kladné hodnoty) a platí pro ni x R : (x) = tx (t). Tato funkce se nazývá pravděpodobnostní funkce náhodné veličiny X. Kromě D1, D2 má tyto vlastnosti: x R : (x) = P(X = x), je-li x0 R libovolný, ale pevně daný bod, pak (x0) = (x0) - limxx- 0 (x). Pro diskrétní náhodnou veličinu je charakteristické, že nabývá pouze konečně nebo nejvýše spočetně mnoha hodnot. Její distribuční funkce má schodovitý cha- rakter. Má-li funkce (x) vlastnosti D1, D2, pak existuje pravděpodobnostní prostor (, A, P) a na něm definovaná diskrétní náhodná veličina X tak, že (x) je její pravděpodobnostní funkce. 7 Náhodné vektory Nechť (, A, P) je pravděpodobnostní prostor, X1, X2, . . . , Xn náhodné veličiny definované na (, A, P), 1, 2, . . . , n jejich distribuční funkce a jedná-li se o diskrétní náhodné veličiny, pak 1, 2, . . . , n buďte jejich pravděpodobnostní funkce. Náhodný vektor je uspořádaná n-tice X = (X1, X2, . . . , Xn). Jeho distribuční funkci definujeme vztahem: (x1, x2, . . . , xn) = P(X1 x1 X2 x2 . . . Xn xn). Náhodný vektor X = (X1, X2, . . . , Xn) se nazývá diskrétní, jestliže existuje funkce (x) nulová v Rn s výjimkou nejméně jednoho a nejvýše spočetně mnoha 97 98 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY bodů, kde je kladná (vlastnost D1: pro všechna x Rn je (x) 0), je normovaná (vlastnost D2: x1=- . . . xn=- (x1, . . . , xn) = 1, kde se sčítají jen kladné hodnoty) a platí pro ni x R : (x1, . . . , xn) = t1x1 . . . tnxn (t1, . . . , tn). Tato funkce se nazývá pravděpodobnostní funkce diskrétního náhodného vektoru X. Kromě D1, D2 má tyto vlastnosti: x Rn : (x) = P(X = x), je-li 1 i n libovolný index, pak x1=- . . . xi-1=- xi+1=- . . . xn=- (x1, . . . , xn) = i(xi). Nechť T je neprázdná indexová množina. Řekneme, že náhodné veličiny Xt jsou stochasticky nezávislé, jestliže pro všechny konečné podmnožiny {u, . . . , v} T a všechny borelovské podmnožiny Bu, . . . , Bv jsou stochasticky nezávislé jevy {Xu Bu}, . . . , {Xv Bv} tj. (x1, . . . , xn) = 1(x1 . . . n(xn). Zobrazení g : R R nazýváme borelovskou funkcí, jestliže vzor borelovské množiny je borelovská množina tj. B B(1) : {x R : g(x) B} B(1) . Obecně zobrazení g = (g1, g2, . . . , gn) : Rn Rm nazýváme borelovskou funkcí, jestliže vzor borelovské množiny je borelovská množina tj. B B(m) : {(x1, . . . , xn) Rn : (g1(x1, . . . , xn), . . . , gm(x1, . . . , xn)) B} B(n) . Mezi borelovské funkce náleží zejména všechny funkce spojité na celém n-rozměrném prostoru nebo v každé z disjunktních oblastí, na něž byl tento prostor rozložen. Rovněž limita všude konvergentní posloupnosti takovýchto funkcí je borelovská funkce. Z dané náhodné veličiny X : R vytvoříme pomocí borelovské funkce g : R R zobrazení Y : R dané takto: : Y () = g(X()). Toto zobrazení je opět náhodná veličina. Nazývá se transformovaná náhodná veličina . Z daného náhodného vektoru X = (X1, . . . , Xn) : Rn vytvoříme pomocí borelovské funkce g = (g1, . . . , gm) : Rn Rm zobrazení Y : Rm dané takto: : Y () = g(X()). Toto zobrazení je opět náhodný vektor. Nazývá se transformovaný náhodný vektor. Rozepsáno: : (Y1(), . . . , Ym()) = (g1(X1(), . . . , Xn()), . . . , gm(X1(), . . . , Xn())). Předpokládejme nyní, že X je diskrétní náhodný vektor s pravděpodobnostní funkcí (x1, . . . , xn) a g : Rn R je borelovská funkce. Odvodíme pravděpodobnostní funkci (y) transformované náhodné veličiny Y () = g(X()). Totiž (y) = P(Y = y) = P(g(X1, . . . , Xn) = y) = P((X1, . . . , Xn) S(y)), 98 8. STŘEDNÍ HODNOTA, ROZPTYL, KOVARIANCE A KOEFICIENT KORELACE NÁHODNÝCH VELIČIN 99 kde S(y) = {(x1, . . . , xn) Rn : g(x1, . . . , xn) = y}, tedy (y) = (x1,...,xn)S(y) (x1, . . . , xn). 8 Střední hodnota, rozptyl, kovariance a koeficient korelace náhodných veličin Nechť je dán pravděpodobnostní prostor (, A, P) a skalární náhodná veličina X. Je-li náhodná veličina X diskrétní a má pravděpodobnostní funkci (x), nazýváme její střední hodnotou vzhledem k pravděpodobnosti P číslo E(X) = x=- x (x) za předpokladu, že případná nekonečná řada vpravo absolutně konverguje. Jinak řekneme, že E(X) neexistuje. Střední hodnota E(X) je číslo, které charakterizuje polohu číselných realizací náhodné veličiny X na číselné ose. Nechť Y = g(X), kde g je borelovská funkce, X diskrétní náhodná veličina. Pak E(Y ) = xR g(x)(x), pokud nekonečná řada vpravo absolutně konverguje. Číslo D(X) = E([X - E(X)]2 ) nazýváme rozptylem náhodné veličiny X vzhledem k pravděpodobnosti P za předpokladu, že obě střední hodnoty vpravo existují. Číslo D nazýváme směrodatnou odchylkou náhodné veličiny X. Pro výpočty je výhodný tvar D(X) = E(X2 )-[E(X)]2 . Rozptyl D(X) je číslo, které charakterizuje variabilitu číselných realizací náhodné veličiny X kolem střední hodnoty E(X). Nechť (X1, X2) je náhodný vektor. Kovariancí náhodných veličin X1, X2 nazýváme číslo C(X1, X2) = E([X1 -E(X1)][X2 -E(X2)]) za předpokladu, že střední hodnoty vpravo existují. Kovariance C(X1, X2) je číslo, které charakterizuje společnou variabilitu číselných realizací náhodných veličin X1, X2 kolem středních hodnot E(X1), E(X2). Je-li C(X1, X2) = 0 řekneme, že náhodné veličiny X1, X2 jsou nekorelované, tzn. že mezi nimi neexistuje žádná lineární závislost. Pro výpočty je výhodný tvar C(X1, X2) = E(X1, X2) - E(X1)E(X2). Koeficientem korelace náhodných veličin X1, X2 nazýváme číslo R(X1, X2) = E X1 - E(X1) D(X1) X2 - E(X2) D(X2) = C(X1, X2) D(X1) D(X2) , D(X1) D(X2) = 0 za předpokladu, že střední hodnoty vpravo existují. Koeficient korelace R(X1, X2) je číslo, které charakterizuje míru těsnosti lineární závislosti číselných realizací náhodných veličin X1, X2. Nabývá hodnot z intervalu < -1, 1 >. 99 100 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY 9 Cauchy-Schwarz-Buňakovského nerovnost, Markovova a Čebyševova nerovnost a) Cauchy-Schwarz-Buňakovského nerovnost Nechť X1, X2 jsou náhodné veličiny. Jestliže existují jejich střední hodnoty a rozptyly, pak |C(X1, X2)| D(X1) D(X2), tj. |R(X1, X2)| 1 a rovnost nastane tehdy a jen tehdy, když mezi veličinami X1, X2 existuje s pravděpodobností 1 úplná lineární závislost, tedy existují konstanty a1, a2 tak, že P(X2 = a1 + a2X1) = 1. b) Markovova nerovnost Jestliže je P(X > 0) = 1 a E(X) existuje, pak pro všechna > 0 platí P(X > E(X)) 1 . b) Čebyševova nerovnost Jestliže existují E(X) a D(X), pak pro každé t > 0 platí: P(|X - E(X)| > t D(X)) 1 t2 . 100 Literatura [1] J. Adámek: Stochastické procesy a teorie informace - úlohy. ČVUT, Praha 1989. [2] J. Adámek: Kódování. SNTL, Praha 1989. [3] J. Adámek: Foundations of Coding Theory. John Wiley & Sons, New York 1991. [4] M. Budíková, Š. Mikoláš, P. Osecký: Teorie pravděpodobnosti a matematická statistika - sbírka příkladů. Masarykova univerzita, Brno 1996. [5] V. Klíma: Kódy, komprimace a šifrování. Chip 2/1993, str. 24-28. [6] L. Kučera a J. Nešetřil: Algebraické metody diskrétní matematiky. SNTL, Praha 1989. [7] J. Paseka: Kryptografie. Učební texty Masarykova univerzita, Brno 1997. [8] Š. Porubský a O. Grošek: Šifrovanie. Algoritmy, Metódy, Prax. Grada, Praha 1992. [9] S. Roman: Introduction to Coding and Information Theory. Springer-Verlag New York, New York 1997. [10] D. Welsh: Codes and Cryptography. Oxford University Press, New York 1989. [11] A. D. Wyner: The wire-tap channel. Bell Syst. Tech. J. 54, 1975, str. 1355- 1387. 101