Kódování
Jan Paseka
9. března 2011
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.
3
4
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.
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
).
5
Teorie kódování je založena na teorii informace - viz následující schéma uvedené např. v [5].
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) v rámci studijních materiálů předmětu M8170 Teorie kódování v IS MU.
6
Obsah
1 Entropie = neurčitost = nejistota = informace 11
1 Nejistota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Entropie a její vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Podmíněná entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Informace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Závěr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 Věta o kódování bez šumu pro zdroje bez paměti 35
1 Zdroje bez paměti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Prefixové a jednoznačně dekódovatelné kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Kraftova a McMillanova nerovnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Věta o kódování bez šumu pro zdroje bez paměti . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Konstruování kompaktních kódování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6 Generování diskrétních rozdělení pomocí vrhu ideální mince . . . . . . . . . . . . . . . . . . 52
3 Komunikace kanály se šumem 63
1 Komunikační systém . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2 Diskrétní kanál bez paměti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7
8 OBSAH
3 Kódování a dekódovací pravidla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4 Kapacita kanálu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Věta o kódování se šumem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6 Kapacita jako hranice spolehlivé komunikace . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4 Kódy opravující chyby 89
1 Kódování a odhady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
2 Ekvivalence kódů a konstrukce nových kódů . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3 Hlavní problém teorie kódování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4 Dolní a horní hranice Aq(n, d); perfektní kódy . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5 Lineární kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6 Použití lineárních kódů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7 Pravidlo minimální vzdálenosti pro lineární kódy . . . . . . . . . . . . . . . . . . . . . . . . 115
8 Binární Hammingovy kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9 Cyklické kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
10 Marinerův kód a Reed-Mullerovy kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
10.1 Hadamardovy kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
10.2 Reed-Mullerovo kódování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
A Náhodné jevy a náhodné veličiny 133
1 Měřitelný prostor a vztahy mezi náhodnými jevy . . . . . . . . . . . . . . . . . . . . . . . . 133
2 Pravděpodobnostní prostor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3 Klasická pravděpodobnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4 Podmíněná pravděpodobnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5 Stochasticky nezávislé náhodné jevy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6 Borelovské množiny a náhodné veličiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7 Náhodné vektory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8 Střední hodnota, rozptyl, kovariance a koeficient korelace náhodných veličin . . . . . . . . . . 141
OBSAH 9
9 Cauchy-Schwarz-Buňakovského nerovnost, Markovova a Čebyševova nerovnost . . . . . . . . 142
10 OBSAH
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,
11
12 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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:
(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é.
1. NEJISTOTA 13
(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) + p · H(p1/p, . . . , pm/p) + q · H(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ěpodobnostmi
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.
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.
14 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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
1. NEJISTOTA 15
(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
,
16 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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.
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.
1. NEJISTOTA 17
Poznámka 1.4 Entropii náhodné veličiny X můžeme rovněž interpretovat jakožto střední hodnotu náhodné
proměnné log2
1
p(X)
. Tedy
H(X) = E(log2
1
p(X)
) = −
k
pk · log2 pk. (1.3)
Příklad 1.5 Nechť
X =
1 s pravděpodobností p
0 s pravděpodobností 1 − p.
(1.4)
Pak
H(X) = −p log2 p − (1 − p) log2(1 − p). (1.5)
Cvičení 1.6
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).
18 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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 vektoru jako
H(X) = −
m
k=1
p(uk) · log2 p(uk). (2.1)
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), (2.2)
2. ENTROPIE A JEJÍ VLASTNOSTI 19
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í. (2.3)
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 konkávní 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.
20 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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.
2. ENTROPIE A JEJÍ VLASTNOSTI 21
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.
Jednoduchým rozšířením této metody lze dokázat:
H(X1, . . . , Xn) ≤ H(X1) + · · · + H(Xn), (2.4)
přičemž rovnost nastává právě tehdy, když X1, . . . , Xn jsou navzájem nezávislé;
H(U, V) ≤ H(U) + H(V) (2.5)
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 ).
22 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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).
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, (3.1)
H(X|Y ) = H(X) jsou-li X a Y nezávislé. (3.2)
3. PODMÍNĚNÁ ENTROPIE 23
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), (3.3)
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. (3.4)
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 ).
24 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é.
4. INFORMACE 25
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.
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)
26 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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),
4. INFORMACE 27
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é terminologii.
Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Předpokládejme,
že X je náhodný vektor, který nabývá hodnoty x1, . . . , xm, s pravděpodobnostmi p1, . . . , pm. Pak
každá z elementárních událostí X = xk (1 ≤ k ≤ m) obsahuje sdruženou informaci rovnou −log2pk a
poznamenejme, že entropie vektoru X je určena vztahem
H(X) = − pklog2pk = pkI(X = xk),
28 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
tedy H(X) má přirozenou interpretaci jako střední hodnota informace sdružené s elementárními událostmi
určenými X.
Obecněji, jsou-li X a Y dva náhodné vektory, definujeme informaci o X poskytnutou Y jako číslo
I(X|Y) = H(X) − H(X|Y).
Jinak řečeno, I(X|Y) vyjadřuje množství nejistoty o X odstraněné Y.
Zřejmě platí, že
I(X|X) = H(X),
I(X|Y) = 0 právě tehdy, když X a Y jsou nezávislé.
Důkaz. Výsledek plyne bezprostředně z dřívější poznámky, že H(X) = H(X|Y) právě tehdy, když X a Y
jsou nezávislé.
Poněkud udivující symetrie v I je následující výsledek,
který zřejmě nemá intuitivní vysvětlení.
I(X|Y) = H(X) − H(X|Y)
= H(X) − [H(X, Y) − H(Y)]
= H(X) + H(Y) − H(X, Y)
= I(Y|X).
5. ZÁVĚR 29
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ěpodob-
nost.]
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.
30 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).
5. ZÁVĚR 31
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.
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
,
32 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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)
.
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).
5. ZÁVĚR 33
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).
34 KAPITOLA 1. ENTROPIE = NEURČITOST = NEJISTOTA = INFORMACE
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
35
36 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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
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.
2. PREFIXOVÉ A JEDNOZNAČNĚ DEKÓDOVATELNÉ KÓDY 37
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)|.
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 budoucnosti.
38 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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 Jiný pohled na prefixové kódování.
Uvažujme D-ární strom, tj. každý uzel buď má D následníků nebo
je listem. Nechť dále větve stromu reprezentují symboly příslušných
kódových slov. Např., D větví vycházejících z kořenového uzlu reprezentuje
možné výskyty prvního symbolu kódového slova. Pak
každé kódové slovo je reprezentováno listem našeho stromu. Cesta
od kořene k listu se pak řídí symboly kódového slova. Evidentně,
protože kódová slova jsou právě listy, není žádné kódové slovo předchůdcem
jiného kódového slova, tj. naše kódování je prefixové.
Obráceně, mějme prefixové kódování na abecedě o D písmenech a
uvažme maximální D-ární strom, který má hloubku rovnu nejdelšímu
slovu našeho kódování.
3. KRAFTOVA A MCMILLANOVA NEROVNOSTI 39
Podmínka, že se jedná o prefixové kódování implikuje, že žádné kódové slovo není předchůdcem jiného
kódového slova v našem stromu. Zejména tedy každé kódové slovo eliminuje všechny své následníky jakožto
možná kódová slova. Lze tedy z maximálního stromu odebrat všechny následníky kódových slov a obdržíme
pak D-ární strom, kde listy odpovídají kódovým slovům.
Poznámka 2.5 Ačkoliv jsme definovali kódování jako zobrazení, často ho identifikujeme se souborem C
kódových slov.
Cvičení 2.6
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.
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. (3.1)
McMILLANOVA NEROVNOST
40 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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. (3.2)
Protože nj jsou všechna nezáporná, postupně dostaneme z (2.2) nerovnosti
3. KRAFTOVA A MCMILLANOVA NEROVNOSTI 41
nl−1 ≤ Dl−1
− n1Dl−2
− · · · − nl−2D,
nl−2 ≤ Dl−2
− n1Dl−3
− · · · − nl−3D,
n3 ≤ D3
− n1D2
− · · · − n2D, (3.3)
n2 ≤ D2
− n1D,
n1 ≤ D.
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
42 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
D−l1
+ · · · + D−lN
r
=
rl
i=1
biD−i
, (3.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.
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 PAMĚTI 43
4 Věta o kódování bez šumu pro zdroje bez pamě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.
44 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
Definujme qi (1 ≤ i ≤ N) jako
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. (4.1)
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.
4. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI 45
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
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}.
46 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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, (5.1)
ale snadno se vidí, že dolní hranice lze dosáhnout pouze, když pi jsou jisté celočíselné mocniny D. Z KraftMcMillanovy
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.
5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 47
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.
48 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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
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.
5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 49
Příklad 5.4 V sousední tabulce je
uvedeno Huffmanovo kódování anglického
jazyka.
Budeme ilustrovat Huffmanovu metodu
na skutečně malém příkladě.
Příklad 5.5 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.
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.
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í
50 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
Poznámka 5.6 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).
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
5. KONSTRUOVÁNÍ KOMPAKTNÍCH KÓDOVÁNÍ 51
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 = S∪S a máme |S | = r+t(r−1)−|S|.
Cvičení 5.7
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?
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.
52 KAPITOLA 2. VĚTA 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.
6 Generování diskrétních rozdělení pomocí vrhu ideální mince
Uvažme následující otázku. Kolik vrhů ideální mince je potřeba, abychom vygenerovali náhodnou proměnnou
X vzhledem k předem zadanému pravděpodobnostnímu rozdělení?
Zkusme si to nejprve ukázat na jednoduchém příkladě.
Příklad 6.1 Buď dána posloupnost vrhů ideální mincí (tj. ideální bity). Dále předpokládejme, že si přejeme
vygenerovat náhodnou proměnnou X s rozdělením
X =



a s pravděpodobností 1
2
,
b s pravděpodobností 1
4
,
c s pravděpodobností 1
4
.
(6.1)
Není žádný problém uhodnout odpověď. Je-li první bit 0, položíme X = a. Jsou-li první dva bity 10, položíme
X = b. Pokud vidíme 11, položíme X = c. Je jasné, že X má požadované rozdělení.
Určeme dále průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné. V
tomto případě to je 1
2
(1) + 1
4
(2) + 1
4
(2) = 1, 5 bitů.
Obecný problém můžeme pak formulovat následovně. Mějme dánu posloupnost vrhů ideální mincí Z1, Z2, . . . ,.
Přejeme si vygenerovat diskrétní náhodnou proměnnou X s oborem hodnot {a1, a2, . . . , am} s pravděpodobnostním
rozdělením p1, p2, . . . , pm. Nechť náhodná proměnná T označuje počet vrhů mince použitých v
algoritmu.
Můžeme popsat algoritmus zobrazující řetězce bitů Z1, Z2, . . . , na možné výstupy náhodné proměnné X
pomocí binárního stromu.
6. GENEROVÁNÍ DISKRÉTNÍCH ROZDĚLENÍ POMOCÍ VRHU IDEÁLNÍ MINCE 53
Listy stromu jsou označeny výstupními symboly X a cesta k
listům je zadána posloupností bitů generovanou vrhem ideální
mincí.
Například strom pro generování pravděpodobnostního rozdělení
1
2
, 1
4
, 1
4
z příkladu 6.1 je uveden na sousedním obrázku.
Strom reprezentující algoritmus musí splňovat jisté vlastnosti:
1. Strom musí být úplný, tj. každý uzel je buď list nebo má dva následníky ve stromu. Strom může být
nekonečný.
2. Pravděpodobnost listu hloubky k je 2−k
. Mnoho listů může být označeno stejným výstupním symbolem
- celková pravděpodobnost všech těchto listů je pak rovna požadované pravděpodobnosti výstupního
symbolu.
3. Průměrný počet ideálních bitů ET požadovaných na vygenerování X je roven střední hodnotě hloubky
tohoto stromu.
Samozřejmě máme mnoho možných algoritmů, které generují stejné rozdělení pravděpodobnosti. Například,
zobrazení 00 → a, 01 → b, 10 → c, 11 → a nám rovněž poskytne rozdělení 1
2
, 1
4
, 1
4
z příkladu
6.1. Ale průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné je
1
4
(2) + 1
4
(2) + 1
4
(2) + 1
4
(2) = 2 bity. Není tedy tak efektivní jako přiřazení z příkladu 6.1, kde jsme potřebovali
pouze 1, 5 bitů.
Můžeme tedy očekávat, že budeme potřebovat alespoň tolik nahodilosti v ideálních bitech kolik vytvoříme
ve výstupních symbolech. Protože entropie je míra nahodilosti a každý ideální bit má entropii jednoho bitu,
můžeme čekat, že počet použitých ideálních bitů bude alespoň tolik jako entropie výstupu.
54 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
Pro další úvahy označme Y množinu listů úplného stromu. Dále uvažujme pravděpodobnostní rozdělení
na listech tak, že pravděpodobnost listu hloubky k stromu bude 2−k
. Buď dále Y náhodná proměnná s touto
distribucí. Máme pak následující lemma.
Lemma 6.2 Pro každý úplný strom uvažujeme pravděpodobnostní rozdělení na listech tak, že pravděpodobnost
listu hloubky k stromu bude 2−k
. Pak střední hodnota hloubky stromu je rovna entropii tohoto rozdělení.
Důkaz. Střední hodnota hloubky stromu je rovna
ET =
y∈Y
k(y)2−k(y)
(6.2)
a entropie rozdělení náhodné proměnné Y je
H(Y ) = −
y∈Y
1
2k(y)
log2
1
2k(y)
=
y∈Y
k(y)2−k(y)
, (6.3)
kde k(y) značí hloubku listu y ∈ Y. Tedy H(Y ) = ET.
Věta 6.3 Pro každý algoritmus generující náhodnou proměnnou X je střední hodnota počtu ideálních bitů
alespoň rovna entropii H(X), tj.
ET ≥ H(X). (6.4)
Důkaz. Každý algoritmus generující náhodnou proměnnou X pomocí ideálních bitů můžeme reprezentovat
pomocí úplného binárního stromu. Označme všechny listy tohoto stromu různými symboly y ∈ Y =
{1, 2, . . . }. Je-li strom nekonečný, pak je i abeceda Y nekonečná.
Uvažme nyní náhodnou proměnnou Y definovanou na listech tohoto stromu tak, že pro každý list y ∈ Y
hloubky k(y) je pravděpodobnost P(Y = y) = 2−k(y)
. Dle Lemmatu 6.2 je střední hodnota hloubky stromu
rovna entropii H(Y ). Ale náhodná proměnná X je funkcí náhodné proměnné Y a tedy z nerovnosti 3.4 na
straně 23 okamžitě obdržíme
H(X) ≤ H(Y ) = ET. (6.5)
6. GENEROVÁNÍ DISKRÉTNÍCH ROZDĚLENÍ POMOCÍ VRHU IDEÁLNÍ MINCE 55
Řešme nyní otázku optimality pro dyadické rozdělení.
Věta 6.4 Nechť náhodná proměnná X má dyadické rozdělení. Pak optimální algoritmus pro vygenerování
X pomocí vrhu ideální mincí má střední hodnotu počtu vrhu mincí rovnu entropii, tj.
H(X) = ET. (6.6)
Důkaz. Z věty 6.3 máme nerovnost H(X) ≤ ET. Věnujme se nyní obrácené nerovnosti. Pro dyadické
rozdělení pak Huffmanovo kódování C splňuje l(C) = H(X). Pro každé x ∈ X je hloubka listu k(x) v
kódovacím stromu odpovídajícímu x rovna délce odpovídajícího kódového slova, což je k(x) = log2
1
p(x)
.
Použijeme-li toto kódování pro vygenerování náhodné proměnné X, tento list bude mít pravděpodobnost
2−k(x)
= 2−log2
1
p(x) = p(x). Střední hodnota počtu vrhů mincí je pak rovna střední hodnotě hloubky stromu,
což je následně rovno entropii (protože rozdělení je dyadické). Máme tedy okamžitě, že pro dyadické rozdělení
optimální generující algoritmus splňuje H(X) = ET.
Co se stane, pokud pravděpodobnostní rozdělení nebude dyadické? V tomto případě pak nelze použít
tutéž myšlenku, protože Huffmanovo kódování bude generovat dyadické pravděpodobnostní rozdělení na
listech, nikoliv rozdělení, se kterým jsme začali. Protože všechny listy z našeho stromu mají pravděpodobnost
tvaru 2−k(z)
, je jasné, že bychom měli rozdělit každou pravděpodobnost pi, která není dyadická, do atomů,
které už dyadické jsou. Můžeme pak připojit tyto atomy k listům našeho stromu. Například, má-li jeden z
výstupů x pravděpodobnost p(x) = 1
4
, budeme potřebovat pouze jeden atom (list stromu v úrovni 2), ale
pokud p(x) = 7
8
= 1
2
+ 1
4
+ 1
8
, budeme potřebovat tři atomy, jeden na úrovni 1, druhý na úrovni 2 a třetí na
úrovni 3 našeho stromu.
Abychom minimalizovali střední hodnotu hloubky stromu, měli bychom použít atomy s co největšími
pravděpodobnostmi. Tedy, je-li dána pravděpodobnost pi, která není dyadická, najdeme největší atom tvaru
2−k
, který je menší než pi a připojíme tento atom ke stromu. Pak spočítáme zbytek a najdeme největší atom,
který je pod zbytkem. Tento proces opakujeme a pak lze rozdělit všechny pravděpodobnosti do dyadických
56 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
atomů. Zřejmě je tento proces ekvivalentní nalezení binárních rozvojů pravděpodobností pi. Buď tedy binární
rozvoj pravděpodobnosti pi tvaru
pi =
j≥1
p
(j)
i , (6.7)
kde p
(j)
i = 2−j
nebo 0. Pak atomy rozvoje jsou {p
(j)
i | i = 1, 2, . . . , m, j ≥ 1}.
Protože m
i=1 pi = 1, bude i součet těchto atomů i,j≥1 p
(j)
i = 1. Přitom připojíme atom s pravděpodobností
2−j
jako list hloubky j ke stromu. Hloubky atomů splňují Kraftovu nerovnost, můžeme tedy
zkonstruovat binární strom, kde atomy mají požadovanou hloubku.
Příklad 6.5 Nechť náhodná proměnná X má pravděpodobnostní rozdělení
X =
a s pravděpodobností 2
3
,
b s pravděpodobností 1
3
.
(6.8)
Nejprve určíme binární rozvoje těchto pravděpodobností:
2
3
= 0.10101010 . . .2,
1
3
= 0.01010101 . . .2. (6.9)
Pak příslušné atomy pro rozvoj jsou:
2
3
→
1
2
,
1
8
,
1
32
, . . . ,
1
3
→
1
4
,
1
16
,
1
64
, . . . . (6.10)
6. GENEROVÁNÍ DISKRÉTNÍCH ROZDĚLENÍ POMOCÍ VRHU IDEÁLNÍ MINCE 57
Tyto atomy můžeme připojit ke stromu (viz sousední obrázek),
který generuje pravděpodobnostní rozdělení 2
3
, 1
3
.
Tato procedura nám poskytne binární stom, který generuje
náhodnou proměnnou X. V předchozím jsme tvrdili, že tato
procedura je optimální v tom smyslu, že náš binární strom
bude mít minimální střední hodnotu hloubky. Nepodáme
zde úplný formální důkaz, ale namísto toho ohraničíme
střední hodnotu hloubky stromu vygenerovaného tímto po-
stupem.
Věta 6.6 Pro optimální algoritmus generující náhodnou proměnnou X střední hodnota počtu ideálních bitů
mezi H(X) a H(X) + 2, tj.
H(X) ≤ ET < H(X) + 2. (6.11)
Důkaz. Dle věty 6.3 máme H(X) ≤ ET. Abychom určili horní hranici, určeme pro každou pravděpodobnost
pi binární rozvoj
pi =
j≥1
p
(j)
i , (6.12)
kde p
(j)
i = 2−j
nebo 0.
Zkonstruujeme pomocí těchto atomů binární strom tak, že jeho listy odpovídají atomům našeho dyadického
rozdělení. Pak počet vrhů ideální mincí potřebných pro vygenerování každého atomu je jeho hloubka
v našem stromu a tedy střední hodnota počtu vrhů ideální mincí je rovna střední hodnotě hloubky našeho
stromu, která je okamžitě rovna entropii dyadického rozdělení atomů. Tudíž
ET = H(Y ), (6.13)
58 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
kde náhodná proměnná Y má pravděpodobnostní rozdělení p
(1)
1 , p
(2)
1 , . . . , p
(1)
2 , p
(2)
2 , . . . , p
(1)
m , p
(2)
m , . . . . Protože
náhodná proměnná X je funkcí náhodné proměnné Y , z nerovnosti 3.4 na straně 23 okamžitě obdržíme
H(Y ) = H(Y, X) = H(X) + H(Y |X), (6.14)
stačí ověřit, že H(Y |X) < 2.
Uvažujme nyní příslušný podstrom a podterm Ti pro každou pravděpodobnost pi. Pak
Ti =
j≥1 : p
(j)
i >0
j2−j
a H(Y ) =
m
i=1
Ti. (6.15)
Můžeme najít takové přirozené číslo ni, že 2−ni
≤ pi < 2−ni+1
, neboli
ni − 1 < −log pi ≤ ni. (6.16)
Nutně tedy p
(j)
i > 0 pouze pokud j ≥ n. Můžeme tedy přepsat 6.15 do tvaru
Ti =
j≥ni : p
(j)
i >0
j2−j
a H(Y ) =
m
i=1
Ti. (6.17)
Zároveň dle definice atomu můžeme zapsat pi jakožto
pi =
j≥ni : p
(j)
i >0
2−j
. (6.18)
6. GENEROVÁNÍ DISKRÉTNÍCH ROZDĚLENÍ POMOCÍ VRHU IDEÁLNÍ MINCE 59
Ukažme nejprve, že platí Ti < −pilog pi + 2pi. Zřejmě
Ti + pilog pi − 2pi
(a)
< Ti + pi(ni − 1) − 2pi = Ti − (ni + 1)pi
= j≥ni : p
(j)
i >0
j2−j
− (ni + 1) j≥ni : p
(j)
i >0
2−j
= j≥ni : p
(j)
i >0
(j − ni − 1)2−j
= −2−n
+ 0 + j≥(ni+2) : p
(j)
i >0
(j − ni − 1)2−j
(b)
= −2−n
+ k≥1 : p
(k+ni+1)
i >0
k2−(k+ni+1)
(c)
≤ −2−n
+ k≥1 k2−(k+ni+1)
= −2−n
+ −2−(n+1)
2 = 0,
přičemž (a) plyne ze vztahu (6.16), (b) plyne ze změny proměnných v rámci sumy a (c) plyne z rozšíření
oboru sumace. Ukázali jsme tedy, že
Ti < −pilog pi + 2pi. (6.19)
Protože ET = m
i=1 Ti, máme okamžitě, že
ET =
m
i=1
Ti < −
m
i=1
pilog pi + 2
m
i=1
pi = H(X) + 2. (6.20)
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.
60 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
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 pravdě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.
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}
6. GENEROVÁNÍ DISKRÉTNÍCH ROZDĚLENÍ POMOCÍ VRHU IDEÁLNÍ MINCE 61
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 (mluvíme o tzv.
Shannonově kódování).
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, tj.
mi = log2
1
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).
62 KAPITOLA 2. VĚTA O KÓDOVÁNÍ BEZ ŠUMU PRO ZDROJE BEZ PAMĚTI
Ukažte, že platí
r ≤ pmax + log[2(log e)/e] = pmax + 0.086,
kde pmax = maxipi.
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
63
64 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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ý, 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.
2. DISKRÉTNÍ KANÁL BEZ PAMĚTI 65
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 ) 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.
66 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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 je uveden na obrázku vpravo.
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.
• 0
0 •
1
−
ε
•
∗
ε
-
1 •
ε
•
1.
1
−
ε
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
2. DISKRÉTNÍ KANÁL BEZ PAMĚTI 67
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 2.2 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.
68 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
Cvičení 2.3 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.
3 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 3.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.
3. KÓDOVÁNÍ A DEKÓDOVACÍ PRAVIDLA 69
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žijeme-li například formuli
úplné pravděpodobnosti, obdržíme následující dva vztahy:
P(správné dekódování) =
c∈C
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í) =
y∈Σn
2
P(správné dekódování|y obdrženo)P(y obdrženo), (3.2)
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 odeslá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)
70 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
Provedeme-li substituci do (3.1), obdržíme
P(správné dekódování) =
c∈C,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í) =
y∈Σn
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)
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:
3. KÓDOVÁNÍ A DEKÓDOVACÍ PRAVIDLA 71
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
72 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
V hlavní části této přednášky budeme pracovat s binárním symetrickým kanálem. Pro tento kanál má
pravidlo maximální pravděpodobnosti obzvlášť snadnou implementaci.
Nechť Vn označuje množinu všech posloupností délky n složených z nul a jedniček a, pokud to bude
nutné, považujme Vn za vektorový n-dimenzionální prostor nad tělesem celých čísel modulo 2. Jsou-li x a y
vektory z Vn, definujme Hammingovu vzdálenost d(x, y) mezi x a y jako počet míst, ve kterých se x a y liší.
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 3.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í 3.3
4. KAPACITA KANÁLU 73
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.
4 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.
74 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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 ), (4.1)
kde supremum je bráno přes všechny zdroje bez paměti S, nebo, ještě přesněji, nad všemi možnými rozděleními
pravděpodobností (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 4.1 přepsat jako
C = max I(S|J ), (4.2)
Dále si uvědomme, že C je kvantitativní veličina určená pouze maticí kanálu P. Můžeme ji zhruba
považovat za konduktanci 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 4.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, (4.3)
kde q = 1 − p.
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í
4. KAPACITA KANÁLU 75
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 4.3.
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 4.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), (4.4)
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). (4.5)
76 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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).
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). (4.6)
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í 4.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

 ,
5. VĚTA O KÓDOVÁNÍ SE ŠUMEM 77
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)
5 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).
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),
78 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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 5.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.
5. VĚTA O KÓDOVÁNÍ SE ŠUMEM 79
(b) Přeneste nově zakódovanou posloupnost kanálem.
Č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
. (5.1)
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(λ)
, (5.2)
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)
80 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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.
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
5. VĚTA O KÓDOVÁNÍ SE ŠUMEM 81
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). (5.3)
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
(5.4)
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
. (5.5)
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 5.3, 5.4, 5.5 a omezené nerovnosti, že
P(B) ≤
M
2n
2nh(p+ε)
. (5.6)
82 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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
nε2
+ M2−n[1−h(p+ε)]
.
pro dostatečně velká n. Protože kapacita C(p + ε) = 1 − h(p + ε), máme pak
P(E) ≤
pq
nε2
+ 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
5. VĚTA O KÓDOVÁNÍ SE ŠUMEM 83
ε = 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.
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ε = ε. (5.7)
Buď Cn kód sestávající z Mn kódových slov splňujících 5.7; 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).
84 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
Věta 5.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í 5.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?
6 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 6.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 → ∞.
6. KAPACITA JAKO HRANICE SPOLEHLIVÉ KOMUNIKACE 85
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 6.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 6.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), (6.1)
kde qE = 1 − pE.
86 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 6.2 máme Fanovu nerovnost.
Důkaz věty 6.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| = 2R·n
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.
6. KAPACITA JAKO HRANICE SPOLEHLIVÉ KOMUNIKACE 87
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.
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?
88 KAPITOLA 3. KOMUNIKACE KANÁLY SE ŠUMEM
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).
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
89
90 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
š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.
Ř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).
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í
1. KÓDOVÁNÍ A ODHADY 91
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.
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}.
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).
92 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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.
1. KÓDOVÁNÍ A ODHADY 93
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.
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).
94 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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ě.
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.
1. KÓDOVÁNÍ A ODHADY 95
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
.
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í
96 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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šší.
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
.
1. KÓDOVÁNÍ A ODHADY 97
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 nastane-li 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.
98 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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 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



 .
2. EKVIVALENCE KÓDŮ A KONSTRUKCE NOVÝCH KÓDŮ 99
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í.
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).
100 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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
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).
2. EKVIVALENCE KÓDŮ A KONSTRUKCE NOVÝCH KÓDŮ 101
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.
102 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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.
3. HLAVNÍ PROBLÉM TEORIE KÓDOVÁNÍ 103
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.
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.
104 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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).
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)
Poznamenejme, že problém určení A2(n, d) je problémem konečných geometrií.
Pro odhad Aq(n, d) platí následující jednoduché tvrzení.
4. DOLNÍ A HORNÍ HRANICE AQ(N, D); PERFEKTNÍ KÓDY 105
Věta 3.6 Pro všechna n ≥ 2,
Aq(n, d) ≤ qAr(n − 1, d). (3.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.
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.1)
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.2)
Pravá strana nerovnosti 4.1 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.1.
106 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
Podobně platí
Lemma 4.2 (Gilbert-Varshamova hranice)
Aq(n, d)
d−1
k=0
n
k
(q − 1)k
≥ qn
. (4.3)
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.3.
Definice. Poloměr pokrytí blokového kódu C je nejmenší poloměr ρ takový,
Fn
q ⊆
c∈C
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ž platí
ρ = max
f∈Fn
q
min
c∈C
d(c, f).
Důkaz: Nechť Fn
q ⊆ c∈C 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 ρ =
maxf∈Fn
q
d(f, C) = maxf∈Fn
q
minc∈C d(c, f).
Naopak, nechť ρ = maxf∈Fn
q
minc∈C d(c, f) = maxf∈Fn
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.
4. DOLNÍ A HORNÍ HRANICE AQ(N, D); PERFEKTNÍ KÓDY 107
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.4)
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.
Věta 4.5 (Singletonova hranice) Platí
Aq(n, d) ≤ qn−d+1
. (4.5)
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é
M±1
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.
108 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
Věta 4.7 (Plotkinova hranice) Je-li n < 2d, máme
A2(n, d) ≤ 2
d
2d − n
. (4.6)
Důkaz. Buď C = {c1, . . . , cM } nějaký (n, M, d)-kód. Uvažme součet S = i<j d(ci, cj). To není nic jiného,
než součet všech vzdáleností kódových slov z C. Protože ale d ≤ d(ci, cj) pro všechna i, j a máme právě
M
2
dvojic kódových slov z C, platí
S =
i<j
d(ci, cj) ≥ d
M
2
. (4.7)
Pokusme se nyní spočítat S tím, že se podíváme na každou pozici zvlášť. Uvažme tedy kódová slova ve
tvaru
c1 = c11 c12 . . . c1n
c2 = c21 c22 . . . c2n
...
cM = cM1cM2. . . cMn.
Máme pak, pro všechna j, 1 ≤ j ≤ n, že pokud kj bitů slova c1j . . . cMj je rovno 1 a zbývajících M − kj
bitů je nulových, pak tyto bity přispějí k součtu všech vzdáleností číslem f(kj) = kj(M − kj). Máme tedy
celkem (protože všech sloupců je n) S ≤ nf(k). Zejména tedy platí
S ≤ nf(k) =
nM2
4
pokud M je sudé
nM2−1
4
pokud M je liché.
Dáme-li obě nerovnosti dohromady, máme
M
2
· d ≤
nM2
4
pokud M je sudé
nM2−1
4
pokud M je liché.
4. DOLNÍ A HORNÍ HRANICE AQ(N, D); PERFEKTNÍ KÓDY 109
Po jednoduché úpravě pak obdržíme
M ≤
2d
2d−n
pokud M je sudé
n
2d−n
< 2d
2d−n
pokud M je liché.
položme a = 2d
2d−n
. Pak máme
M ≤
2a pokud M je sudé
2a − 1 pokud M je liché.
Předpokládejme nejprve, že k ≤ a < k + 1
2
pro nějaké přirozené číslo k. Pak 2a = 2k a 2 a = 2a .
Máme tedy, nezávisle na paritě M, že M ≤ 2 a . Předpokládejme nyní, že k + 1
2
≤ a < k + 1 pro nějaké
přirozené číslo k. Pak 2a = 2k + 1 a 2 a = 2k. Je-li M liché, máme M ≤ 2a − 1 = 2k = 2 a a, je-li
M sudé, máme M ≤ 2a − 1 = 2k + 1 tj. = M ≤ 2k = 2 a .
Nutně tedy celkem M ≤ 2 d
2d−n
.
Lemma 4.8 Buď k přirozené číslo. Pak A2(4k − 1, 2k − 1) ≤ 8k a A2(4k, 2k) ≤ 8k.
Důkaz. Ověřme nejprve, že A2(4k, 2k) ≤ 8k. Víme ale, že A2(4k, 2k) ≤ 2A2(4k − 1, 2k) ≤ 4 2k
1
= 8k dle
4.7. Protože dále platí A2(4k − 1, 2k − 1) = A2(4k, 2k) ≤ 8k, tvrzení je dokázáno.
Cvičení 4.9 1. Ukažte, že 19 ≤ A2(10, 3) ≤ 93.
2. Ukažte, že pro všechna přirozená čísla q, parametry n = (qr
− 1)/(q − 1), M = qn−r
, d = 3, kde r je
nějaké přirozené číslo ≥ 2, splňují podmínku 4.4 proto, aby se jednalo o perfektní kód. Poznamenejme,
že ačkoliv tyto parametry splňují 4.4 pro každé přirozené číslo q, byla vyslovena hypotéza, že příslušné
perfektní kódy existují právě tehdy, když je q mocnina prvočísla.
110 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
5 Lineární kódy
Předpokládejme, že C je kód s minimální vzdáleností d = 2e + 1 a lze tedy pomocí metody nejbližšího
kódového slova opravit až e chyb. Má-li kód C málo prvků, jedná se o velmi praktickou metodu. V případě,
že číslo |C| bude velké, bude tato metoda opravdu velmi časově náročná, protože musíme srovnávat přijatý
vektor y s velkým množstvím kódových slov. To je důvod pro studium více strukturovaných kódů, jako jsou
např. lineární kódy.
Předpokládejme tedy, že počet prvků q naší abecedy je prvočíselná mocnina pm
. Můžeme tedy považovat
Σ za těleso Fq o q-prvcích.
Buď dále Vn(q) vektorový prostor dimenze n nad tělesem Fq. Typický prvek tohoto vektorového prostoru
budeme psát jakožto x = (x1, . . . , xn), občas pak zkráceně jakožto x = x1 . . . xn, kde xi ∈ Fq.
Lineární kód C nad Σ je definován jakožto podprostor prostoru Vn(q). Má-li tento podprostor dimenzi k,
mluvíme o [n, k]-kódu nebo, chceme-li specifikovat minimální vzdálenost, mluvíme o [n, k, d]-kódu. Protože
každý k-dimenzionální podprostor nad Fq má qk
prvků, máme:
Každý [n, k, d]-kód nad Fq je (n, qk
, d)-kód.
Výhoda lineárních kódů je to, že pomocí k kódových slov délky n můžeme zcela popsat kód s právě
qk
kódovými slovy délky n. Tím dosáhneme obrovské úspory paměti. Totiž každý podprostor dimenze k je
úplně popsán k lineárně nezávislými vektory.
Definujeme pak generující matici pro lineární [n, k]-kód C jakožto libovolnou matici rozměru k × n, jejíž
řádky tvoří k lineárně nezávislých kódových slov z C. Předpokládejme nyní, že G je generující matice kódu
C a G je matice, kterou můžeme obdržet z G pomocí konečné posloupnosti permutací následujícího typu:
1. záměna řádků,
2. násobení řádku nenulovým skalárem,
3. přičtení k řádku skalární násobek jiného řádku,
5. LINEÁRNÍ KÓDY 111
4. záměna sloupců,
5. násobení sloupce nenulovým skalárem.
Pak lze snadno ukázat následující tvrzení.
Lemma 5.1 G je generující matice kódu C , který je ekvivalentní s kódem C.
Důkaz. Stačí ukázat, že každá z operací 1-5 odpovídá vytvoření generující matice G kódu C , který je
ekvivalentní s kódem C. Evidentně, záměna řádků, vynásobení řádku nenulovým skalárem a přičtení řádků
jsou operace takové, že dokonce kód C je totožný s kódem C. Záměna sloupců v matici G znamená, že provedeme
poziční permutaci určenou transpozicí sloupců. Vynásobení sloupce nenulovým skalárem je symbolová
permutace tohoto sloupce (pracujeme nad tělesem a pak je množina nenulových skalárů grupou). Jsou tedy
odpovídající kódy ekvivalentní s kódem C.
Lemma 5.2 Buď G matice typu k × n jejíž řádky jsou lineárně nezávislé; pak, aplikujeme-li posloupnost
operací typu (1)-(5) na G, je možné G převést na matici G = [Ek, A], kde Ek je jednotková matice typu
k × k.
Důkaz. Důkaz je veden indukcí vzhledem ke k. Pokud k = 1, je tvrzení evidentní. Stačí vynásobit řádek
matice G prvkem inverzním k prvku g11. Předpokládejme, že tvrzení platí pro k a chceme jej dokázat pro
k + 1. Protože hodnost matice G je k + 1 existuje v matici G k + 1 nezávislých sloupců. Pomocí operace
typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice G . Pak nutně v k + 1-ním sloupci
existuje nenulový prvek – jinak by hodnost matice nebyla k + 1. Provedeme pak pomocí operace typu (1)
záměnu příslušného řádku s posledním řádkem. Nový poslední řádek vynásobíme po řadě vhodnými skaláry
a odečteme jej od předchozích řádků tak, aby se nám k + 1-ní sloupec až na poslední řádek vynuloval. Pak
obdržíme matici G , jejichž prvních k řádků (po vynechání k+1-ního sloupce) je matice typu k×(n−1), která
má hodnost k. Lze pak aplikovat indukční předpoklad a obdržíme matici, která má na prvních k řádcích
submatici typu [Ek, A] (přitom na vynechaný k + 1-ní sloupec budeme provádět pouze řádkové úpravy).
Snadno se zbavíme nenulových prvků v posledním řádků na prvních k-místech pomocí operace typu (3).
Přitom nutně na místě (k + 1, k + 1) je nenulový prvek, stačí pak vynásobit prvkem k němu inverzním.
112 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
V důsledku 5.2 můžeme bez újmy na obecnosti pracovat s generujícími maticemi ve výše uvedené standardní
formě. Jinou užitečnou vlastností lineárních kódů je, že jejich minimální vzdálenost lze najít mnohem
snáze, než v případu obecných kódů. Máme pak následující výsledek
Věta 5.3 Minimální vzdálenost d lineárního kódu C je minimální váha w všech nenulových vektorů z C.
Důkaz. Buď d minimální vzdálenost lineárního kódu C a předpokládejme, že x, y ∈ C tak, že d(x, y) = d.
Pak x − y ∈ C, w(x − y) = d ≥ w = w(z) = d(z, 0) ≥ d pro vhodný vektor z ∈ C.
6 Použití lineárních kódů
Předpokládejme, že C je lineární [n, k]-kód nad Fq = Σ a že má generující matice G tvaru
G =





r1
r2
...
rk





= [Ek, A] ,
kde ri jsou vektory délky n nad Fq a A je matice typu k × (n − k). Kódová slova kódu C jsou vektory délky
n tvaru
k
i=1
airi, ai ∈ Fq.
Základní myšlenka zakódování je následující. Pokud je zpráva braná jako posloupnost s = (s1, . . . , sk),
zakódujeme s pomocí kódového slova c = (c1, . . . , cn), kde ci jsou určena předpisem
[c1, . . . , cn] = [s1, . . . , sk] [Ek, A] , (6.1)
tj. ci = si pro 1 ≤ i ≤ k.
6. POUŽITÍ LINEÁRNÍCH KÓDŮ 113
Příklad 6.1 Předpokládejme, že kód C nad tělesem F3 (což je těleso zbytkových tříd po dělení 3) má
generující matici G tvaru
G =


1 0 0 1 2 0
0 1 0 0 1 1
0 0 1 2 0 1

 .
Je-li vstupní zpráva ze zdroje tvaru
102101210122 . . .
rozdělíme ji nejprve do bloků délky tři a obdržíme
102 | 101 | 210 | 122 | . . .
a pak zakódujeme zdrojová slova jakožto
102 → r1 + 2r3 = 102222, 101 → r1 + r3 = 101021
201 → 2r1 + r3 = 210221, 122 → r1 + 2r2 + 2r3 = 122211.
Dostaneme tedy posloupnost
102 | 222 | 101 | 021 | 210 | 221 | 122 | 211 | . . .
Tedy jsme, při zdvojení délky zprávy, zpomalili rychlost přenosu na polovic. Zvýšili jsme ale spolehlivost.
Poznamenejme, že vztah 6.1 je ekvivalentní s rovnicí
−A , En−k [c1, . . . , cn] = 0. (6.2)
Matice H = −A , En−k se nazývá matice kontroly parity kódu C. Zejména tedy platí, že z ∈ C právě
tehdy, když H [z1, . . . , zn] = 0.
Přitom matice H kontroly parity definuje jak vlastní kód C tak i příslušnou generující matici G. Název
matice kontroly parity znamená, že na jistých kontrolních místech jsou přidány jisté kontrolní součty, které
zkontrolují naše kódová slova. Občas budeme pro [n, k]-kód říkat, že prvních k složek kódového slova je
nazýváno informačními znaky a zbývajících n − k složek jsou symboly kontroly parity (kontrolní znaky).
114 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
Příklad 6.2 Určeme nyní matici H kontroly parity z příkladu 6.1. Ta má tvar
H =


−1 0 −2 1 0 0
−2 −1 0 0 1 0
0 −1 −1 0 0 1

 =


2 0 1 1 0 0
1 2 0 0 1 0
0 2 2 0 0 1

 .
Kódové slovo 102222 sestává z ze zprávových čísel 102 a symbolů kontroly parity 222. Evidentně, rovnost
6.2 je pro toto kódové slovo (a všechna zbývající) splněna.
Obecně musí tedy kódová slova splnit systém rovnic
2c1 + c3 + c4 = 0 c1 + 2c2 + c5 = 0 2c2 + 2c3 + c6 = 0. (6.3)
Základní idea pro metodu opravování chyb je vidět na tomto příkladě. Předpokládejme, že naše obdržené
slovo nesplňuje první a třetí rovnici 6.3 v rovnicích kontroly parity. Pak můžeme dedukovat, že chybná číslice
zprávy je číslice c3, protože to je jediná číslice, která se vyskytuje v obou rovnicích.
Věta 6.3 Je-li H matice kontroly parity kódu Cdélky n, pak kód C má minimální vzdálenost d tehdy a jen
tehdy, když každých d − 1 sloupců matice H je nezávislých, ale některých d sloupců je lineárně závislých.
Důkaz. Označme po řadě sloupce matice H jako h1, . . . , hn. Připomeňme, že pro každý řádkový vektor
[c1, . . . , cn] máme
[c1, . . . , cn]HT
=
n
i=1
cihT
i .
Předpokládejme, že d je minimální počet lineárně závislých sloupců matice H. Pak existují skaláry c1, . . . , cn,
z nichž je právě d nenulových tak, že
[c1, . . . , cn]HT
= 0T
.
Ale to neříká nic jiného, že c = c1 . . . cn ∈ C. Protože wt(c) = d, máme d(C) ≤ wt(c) = d. Obráceně, je-li
c = c1 . . . cn ∈ C kódové slovo minimální délky, pak nutně [c1, . . . , cn]HT
= 0T
a tedy je d(C) sloupců z H
odpovídajícím d nenulovým prvkům lineárně závislých. Je tedy d ≤ d(C) tj. d = d(C).
7. PRAVIDLO MINIMÁLNÍ VZDÁLENOSTI PRO LINEÁRNÍ KÓDY 115
7 Pravidlo minimální vzdálenosti pro lineární kódy
Uvažme problém dekódování pro lineární kódy. Je-li C [n, k]-kód nad abecedou Σ = Fq, pak C obsahuje qk
kódových slov délky n a počet možných obdržených vektorů je qn
. Prohlížecí tabulka, která by pro každý
možný obdržený vektor obsahovala "nejbližší" kódové slovo by zabírala příliš velké množství paměti, dokonce
pro malá n a k. Jednou z hlavních výhod používání lineárních kódů je, že existuje elegentní způsob vyhnutí
se výše uvedenému problému.
Tento postup popíšeme pouze v binárním případě. Rozšíření na jiné abecedy mohutnosti q = pm
, kde p
je prvočíslo je bezprostřední i když technicky náročnější.
Předpokládejme, že C je [n, k]-binární kód. Protože je C podprostor vektorového prostoru Vn binárních
vektorů délky n, musí být C podgrupa aditivní grupy Vn.
Připomeňme, že řád konečné grupy G je definovaný jako mohutnost |G| nosné množiny G, tj. počet
prvků G a index [G : S] podgrupy S ⊆ G je počet |G/S| různých (levých) tříd rozkladu G podle S. Přitom
(levá) třída určená prvkem a ∈ G má tvar Sa = {sa : s ∈ S}. Speciálně je přiřazení a → Sa surjektivní
homomorfismus G → G/S. Přitom dvě třídy Sa, Sb jsou totožné právě tehdy, když a = s0b pro některé
s0 ∈ S. Pravé násobení prvkem a je bijekce S → Sa a proto má každá (levá) třída rozkladu stejný počet
prvků jako podgrupa S. Protože G je sjednocení příslušných levých tříd rozkladu, je počet prvků celé grupy
G stejný jako počet tříd rozkladu krát počet prvků v S:
|G| = |G/S| · |S|.
Zejména tedy kód C určuje soubor levých tříd (kosetů) podprostoru Vn a libovolný vektor a ∈ Vn určuje
jediný koset a + C = {b : b = a + c pro vhodný vektor c ∈ C}.
Předpokládejme tedy, že y je obdržený vektor v tom případě, že jisté kódové slovo bylo přeneseno
kanálem. Řekneme, že vektor e je možný chybový vektor vektoru y, pokud existuje kódové slovo c ∈ C tak,
že
y − c = e.
116 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
Speciálně je tedy interpretace následující: vektor e je chybový vektor přidružený k obdrženému vektoru,
jestliže je schopen reprezentovat jistou možnou posloupnost chyb při přenosu. Následující triviální pozorování
je klíčové.
Lemma 7.1 Je-li y obdržený vektor, je množina možných chybových vektorů ten koset množiny C, který
obsahuje vektor y.
Důkaz. Bylo-li obdrženo slovo y, je vektor e chybový vektor právě tehdy, když existuje kódové slovo c ∈ C
tak, že y − c = e. Ale C je podprostor; tedy i −c ∈ C, tj. e = y + c a e ∈ y + C.
Co to je dekódování podle pravidla minimální vzdálenosti? To není nic jiného, než nalezení chybového
vektoru s minimální vahou. Známe-li tedy, pro každý koset jeho prvek minimální váhy, pak máme základ
pro dekódování podle pravidla minimální vzdálenosti. Řekneme pak, že vektor e je reprezentant kosetu H,
jestliže má nejmenší váhu ze všech vektorů obsažených v H = e + C. Zdůrazněme, že takovýto reprezentant
nemusí být vybrán jednoznačně.
Algoritmus I
Krok 1: Po přijetí vektoru y najdeme reprezentanta z0 kosetu y − C.
Krok 2: Vektor y pak dekódujeme jakožto kódové slovo y − z0.
Evidentně, Krok 1 může být velmi časově náročný. Urychlíme jej použitím následující vlastností lineárních
kódů.
Lemma 7.2 Dva vektory y1 a y2 leží v témže kosetu právě tehdy, když
Hy1 = Hy2 .
7. PRAVIDLO MINIMÁLNÍ VZDÁLENOSTI PRO LINEÁRNÍ KÓDY 117
Důkaz. Dva vektory y1 a y2 leží v témže kosetu právě tehdy, když existuje kódové slovo c ∈ C tak, že
y1 = y2 + c
tj.
Hc = H(y1 − y2) = 0
tj.
Hy1 = Hy2 .
Definujme syndrom kosetu H = a + C jakožto vektor Ha délky k. Evidentně, je tato definice korektní.
Máme tedy pro každý koset H jeho syndrom a jeho reprezentanta kosetu. Máme-li tedy předem vypočtenou
tabulku, ve které je pro každý syndrom určen příslušný reprezentant, můžeme urychlit výše uvedný algoritmus
následovně:
Algoritmus II – poloeficientní
Krok 1a: Po přijetí vektoru y najdeme syndrom Hy .
Krok 1b: Z výše uvedené tabulky najdeme odpovídajícího reprezentanta z0 kosetu y − C.
Krok 2: Vektor y pak dekódujeme jakožto kódové slovo y − z0.
Platí pak
Věta 7.3 Algoritmus II pracuje jakožto dekódovací pravidlo podle minimální vzdálenosti pro lineární kód C.
118 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
Důkaz. Poznamenejme nejprve, že každé obdržené slovo y můžeme dekódovat jakožto kódové slovo. To je
z toho důvodu, že y a z0 jsou ve stejném kosetu a tedy y−z0 ∈ C. Předpokládejme, že existuje kódové slovo
c tak, že
d(y, y − z0) > 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.
7. PRAVIDLO MINIMÁLNÍ VZDÁLENOSTI PRO LINEÁRNÍ KÓDY 119
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í.
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.
120 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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ě.
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.
8. BINÁRNÍ HAMMINGOVY KÓDY 121
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 pozna-
menejme:
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á:
122 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
(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.
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í,
9. CYKLICKÉ KÓDY 123
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 [8]).
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).
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.
124 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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)}.
9. CYKLICKÉ KÓDY 125
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)
.
126 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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.
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 127
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, (10.1)
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


 . (10.2)
Přímým výpočtem pak snadno dokážeme:
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).
128 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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í.
10. MARINERŮV KÓD A REED-MULLEROVY KÓDY 129
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.
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}. (10.3)
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|+|Je ∩In|+|Jn ∩Ie| =
|Jn| + 2|Je ∩ In| ≥ d2.
Přitom v prvním a druhém případě může pro vhodně vybrané dvojice nastat rovnost, tj. tvrzení platí.
130 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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}, (10.4)
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) (10.5)
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
.
10. MARINERŮV KÓD A REED-MULLEROVY KÓDY 131
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
Pr+1
i=0
m
i · 2
Pr
i=0
m
i = 2
Pr+1
i=0
m
i
+
Pr
i=0
m
i = 2
Pr+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),
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.
132 KAPITOLA 4. KÓDY OPRAVUJÍCÍ CHYBY
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 sjednocení
se nazývá jevové pole .
133
134 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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 i∈I Ai značí společné nastoupení náhodných jevů
Ai, i ∈ I a i∈I 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é.
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 135
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) − 1≤i<j≤n P(Ai ∩ Aj) + · · · +
(−1)l
1≤i1<···<il≤n P(Ai1 ∩ · · · ∩ Ail
) + · · · + (−1)n−1
P(A1 ∩ · · · ∩ An).
4 Podmíněná pravděpodobnost
Nechť (Ω, A, P) je pravděpodobnostní prostor, H ∈ A náhodný jev s nenulovou pravděpodobností. Pro
každé A ∈ A definujeme podmíněnou pravděpodobnost vzorcem
P(A|H) =
P(A ∩ H)
P(H)
.
Věta 4.1 Věta o násobení pravděpodobností Nechť (Ω, A, P) je pravděpodobnostní prostor, A1, . . . , An ∈
A náhodné jevy takové, že P(A1 ∩ · · · ∩ An−1) > 0. Pak platí
P(A1 ∩ · · · ∩ An) = P(A1) · P(A2|A1) · P(A3|A1 ∩ A2) · · · · · P(An|A1 ∩ A2 ∩ · · · ∩ An−1).
136 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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) =
i∈I
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)
i∈I 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) = i∈I P(Hi) · P(A|Hi) · P(B|A ∩ Hi)
i∈I 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|A ∩ Hi). Dosazením do 2.
Bayesova vzorce dostaneme pravděpodobnost P(B|A).
5. STOCHASTICKY NEZÁVISLÉ NÁHODNÉ JEVY 137
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.
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)).
138 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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.
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.
7. NÁHODNÉ VEKTORY 139
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) = t≤x π(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) − limx→x−
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ý charakter.
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 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) = t1≤x1
· · · tn≤xn
π(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).
140 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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(ω))).
8. STŘEDNÍ HODNOTA, ROZPTYL, KOVARIANCE A KOEFICIENT KORELACE NÁHODNÝCH VELIČIN141
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)),
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 ) = x∈R 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
142 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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 >.
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
ε
.
9. CAUCHY-SCHWARZ-BUŇAKOVSKÉHO NEROVNOST, MARKOVOVA A ČEBYŠEVOVA NEROVNOST143
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
.
144 DODATEK A. NÁHODNÉ JEVY A NÁHODNÉ VELIČINY
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] T. M. Cover, Joy A. Thomas: Elements of Information Theory. 2nd Edition, John Wiley & Sons, New
York 2006.
[6] V. Klíma: Kódy, komprimace a šifrování. Chip 2/1993, str. 24-28.
[7] L. Kučera a J. Nešetřil: Algebraické metody diskrétní matematiky. SNTL, Praha 1989.
[8] J. Paseka: Kryptografie. Učební texty Masarykova univerzita, Brno 1997.
[9] Š. Porubský a O. Grošek: Šifrovanie. Algoritmy, Metódy, Prax. Grada, Praha 1992.
[10] S. Roman: Introduction to Coding and Information Theory. Springer-Verlag New York, New York 1997.
145
146 LITERATURA
[11] D. Welsh: Codes and Cryptography. Oxford University Press, New York 1989.
[12] A. D. Wyner: The wire-tap channel. Bell Syst. Tech. J. 54, 1975, str. 1355-1387.
Index
A
Aq(n, d) 102
B
bit 27
blokový kód 89
borelovská funkce 140
C
Cauchy-Schwarz-Buňakovského nerovnost 142
cyklický kód 122
Č
Čebyševova nerovnost 143
D
diskrétní náhodná veličina 139
distribuční funkce náhodné veličiny X vzhledem k
pravděpodobnosti P 138
E
elementární jev 134
entropie náhodné veličiny 16
entropie náhodného vektoru 18
F
formule úplné pravděpodobnosti 136
G
generování diskrétních rozdělení 52
generující matice 110
generující polynom 124
Gilbert-Varshamova hranice 106
H
Hadamardova matice 127
Hadamardův kód 129
Hammingova vzdálenost 91
Hammingův [n, k]-kód 120
hlavní problém teorie kódování 102
I
index podgrupy 115
informace o X poskytnutá Y 28
informace události 26
informační znak 113
147
148 INDEX
J
jednoznačně dekódovatelné kódování 37
jevové pole 133
jistý jev 134
K
klasická pravděpodobnost 135
kód 37
kód C opraví právě v chyb 90
kód C opraví v chyb 90
kód C určí právě u chyb 90
kód C určí u chyb 90
kód C zároveň opraví v chyb a určí u chyb 94
kódování 37
kódové slovo 89
koeficientem korelace náhodných veličin 142
konečné geometrie 104
kontrola parity 100, 113
kontrolní znak 113
koset 115
kovariance náhodných veličin 141
Kroneckerův součin 127
L
lineární kód 110
M
Markovova nerovnost 142
měřitelný prostor 134
minimální vzdálenost 92
minimální vzdálenost kódu C 92
možný chybový vektor 115
možný výsledek je příznivý jevu 134
N
náhodné jevy jsou neslučitelné 134
náhodný jev 134
náhodný vektor 139
nastoupení alespoň jednoho z náhodných jevů 134
nejistota náhodné veličiny 16
nemožný jev 134
n-rozměrná borelovská množina 138
n-rozměrné borelovské pole B(n)
138
O
objem Vn,r
ρ (x) sféry Sn,r
ρ (x) 91
opačný náhodný jev k náhodnému jevu 134
optimální kód 102
P
perfektní kód 107
Plotkinova hranice 108
podmíněná entropie náhodné proměnné 22
podmíněná pravděpodobnost 135
poloměr pokrytí 106
poziční permutace 98
pravděpodobnost 134
pravděpodobnostní funkce 139
INDEX 149
pravděpodobnostní funkce diskrétního náhodného vektoru
139
pravděpodobnostní prostor 134
průnik x ∩ y binárních slov x a y 99
R
Reed-Mullerův kód C(r, m) 130
reprezentant kosetu 116
rozptyl náhodné veličiny 141
rozšíření kódování 37
rozšíření kódu 100
Ř
řád konečné grupy 115
S
sféra Sn,r
ρ (x) v Zn
r se středem x a poloměrem ρ 91
Shannonovo kódování 61
Singletonova hranice 107
slovo 91
směrodatná odchylka 141
společné nastoupení náhodných jevů 134
stochasticky nezávislé náhodné jevy 137
střední hodnota 141
symbol kontroly parity 113
symbolová permutace 98
syndrom kosetu 117
T
transformovaná náhodná veličina 140
transformovaný náhodný vektor 140
triviální perfektní kód 107
U
úplný systém hypotéz 136
V
váha slova 91
vektor 91
Z
základní prostor 133
zdroj 35
zdroj s nulovou pamětí 36
zdrojem bez paměti 36
zdrojové slovo 36
zkrácení kódu typu xi = s 101
zpráva 37, 89
1. Bayesův vzorec 136
2. Bayesův vzorec 136