Kapitola 18
Kódování

18.1  Jednotky

18.1.1  Jednotky pro měření informace

Každá zpráva nese určité množství informace o nějaké události. Množství informace spojujeme s neočekávaností události, o které hovoří zpráva. Čím je událost méně očekávána, tím více informace zpráva nese. Množství přijaté informace

I = log2 P2 P1 = log2 P2 − log2 P1       [bit],

kde P₁ je pravděpodobnost události před přijetím zprávy a P₂ pravděpodobnost události po přijetí zprávy. V případě, že po přijetí zprávy je naše znalost o události taková, že je jisté, že se koná (P₂ = 1), potom se vztah pro určení množství informace ve zprávě zjednoduší na I = −log₂ P₁.

18.1.2  Entropie diskrétních zpráv

Diskrétní zpráva je taková, jejíž přenos se děje po symbolech – písmenech abecedy, číslicích. Nechť počet všech symbolů v abecedě je m a počet předaných symbolů n. V oněch n symbolech mohou být symboly abecedy zastoupeny různě, získáme tak různé n-tice symbolů, kterých je dohromady mⁿ. Bude-li pravděpodobnost výskytu každé z možných n-tic symbolů stejná, pak pravděpodobnost výskytu některé konkrétní n-tice bude P₁ = 1 / mⁿ a množství informace v jedné zprávě o n symbolech bude I = −log₂ P₁ = −log₂ (1 / mⁿ) = log₂ mⁿ = n log₂ m. Entropie takové zprávy, čili množství informace na jeden symbol, bude

H = I n = log2 m       [bit / symbol].

Běžně při přenosu zpráv ale není pravděpodobnost přenosu každé z n-tic stejná, navíc i symboly jsou užívány s různou pravděpodobností.

IN = −(n1 log2 P1 + n2 log2 P2 + … + nm log2 Pm)

Průměrné množství informace na jeden symbol je

H =	IN N	=	− (	n1 N	log2 P1 +	n2 N	log2 P2 + … +	nm N	log2 Pm	) =
		=	− (	P1 log2 P1 + P2 log2 P2 + … + Pm log2 Pm						)

Největší entropii má taková abeceda symbolů, jejíž symboly jsou používány se stejnou četností. Nejsou-li symboly používány se stejnou četností, je entropie nižší. Předávání zpráv ve formě textu se děje s entropií silně sníženou vůči maximu. Nejen že se jednotlivé symboly (písmena) vyskytují s různými pravděpodobnostmi, ale i mezi předávanými písmeny existuje silná korelace.

Skutečnost, že danou abecedu nevyužíváme pro přenos s nejvyšší entropií, zachycuje pojem redundance neboli nadbytečnost . Definuje se vztahem

R = Hmax− H Hmax = 1 − H Hmax .

Poměr H / H_max vlastně udává, s jakou efektivitou využíváme maximálně dosažitelnou entropii. Při dané abecedě bychom mohli tedy informaci posílat rychleji. To, že plně nevyužíváme možnosti abecedy, nás však z druhé strany chrání před poruchami. Bez nadbytečnosti by bylo možné zprávu správně pochopit jen při velmi nízké úrovni poruch.

18.1.3  Entropie spojitých zpráv

18.1.4  Informační kapacita

18.2  Kódování bez rušení

Kódem se nazývá systém korespondence mezi diskrétními prvky zprávy – symboly, písmeny abecedy – a signály, s jejichž pomocí se tyto symboly zaznamenávají nebo předávají po spojovém kanálu. Kódování tedy spočívá v přeměně předávané zprávy na posloupnost relativně jednoduchých elektrických signálů.

18.2.1  Střední výkon

18.2.2  Počet úrovní

Kolik má mít zakódovaný signál úrovní, aby byl přenos co nejefektivnější? V praxi se nejčastěji volí dvojúrovňový signál. Šum neruší, dokud zůstanou úrovně (šumem ovlivněné) v tolerančním pásmu. Pro přenos právě dvou úrovní je třeba nejmenší výkon při daném rušení (neboli daný šum nejméně ruší), nejmenší potřebná energie, ale je pomalejší.

18.2.3  Huffmanovo kódování

Při kódování je následující postup. Nejprve přenášené symboly seřadíme podle pravděpodobnosti výskytu. Ze dvou symbolů s nejnižší pravděpodobnosti vytvoříme symbol nový, jehož pravděpodobnost je dána součtem pravděpodobností výskytu symbolů, ze kterých vznikl. Symboly znovu setřídíme a pokračujeme stejným způsobem, až vzniknou jen dva symboly. Poté „jdeme zpět“ a přiřazujeme log. 0 a log. 1 pro každou úroveň.

18.2.4  Fanovo kódování

Symboly se rozdělí na dvě skupiny, které by měly, pokud možno, mít stejnou pravděpodobnost a měly by jít dále dělit obdobným způsobem. Nakonec opět přiřadíme log. 0 a log. 1.

18.3  Kódování s nadbytečností

Když je rušení při přenosu příliš velké, pak se volí N < N₀, kde N₀ je počet znaků možný a N počet znaků užívaných. Je dobré konkrétní kód volit tak, aby při změně jednoho bitu nastala chyba (přijmul by se nedovolený znak). Při vysílání zpráv vysíláme některou z N kombinací. V důsledku chyby se může právě vysílaná kombinace změnit na některou z N₀ − 1 kombinací, tj. pro danou kombinaci zjistíme právě N₀ − 1 různých chyb. Můžeme vysílat kteroukoliv z N dovolených kombinací, pro každou z nich rozlišíme N₀− 1 chyb. Celkově máme tedy N (N₀ − 1) různých případů chyb. Vysíláme-li právě některou dovolenou kombinaci, pak vlivem chyby může tato kombinace přejít na N₀− N kombinací nedovolených, a takové kombinace jsme schopni zjistit. Pro N kombinací je tedy zjistitelných N (N₀ − N) chyb. Každé dovolené kombinaci přiřadím jednu nebo několik kombinací nedovolených – nejlépe podle pravděpodobnosti, ze které dovolené kombinace příslušná nedovolená vznikne.

18.3.1  Hamingova kódová vzdálenost

Je to nejmenší ze vzdáleností dvojic kódových slov. Určuje schopnost kódu objevovat a opravovat chyby. Pro odhalování jednonásobných chyb (q = 1) postačuje Hamingova kódová vzdálenost ρ = 2. Pro odhalení všech chyb s násobností q_d a menší postačuje, aby dovolené kombinace měly Hamingovu kódovou vzdálenost ρ ≥ q_d + 1.

Chybná kombinace je opravitelná (jednoznačně), pokud její vzdálenost k dovolené kombinaci, ze které tato chybná kombinace vznikla, je menší než vzdálenost ke kterékoliv jiné dovolené kombinaci. Chceme-li jednoznačně opravovat chybné kombinace s násobností chyby q_c a menší, potom musí platit ρ ≥ 2q_c + 1. Není-li pravděpodobnost chybného přenosu symbolu příliš velká, pak se při použití kódů s opravou zvyšuje pravděpodobnost správného přenosu symbolu. Pokud je pravděpodobnost chyby při přenosu symbolu vysoká, je použití kódů s nadbytečností málo efektivní.

18.3.2  

Používají se také dekódovací zařízení „erasure channel“, které přijímají log. 0 nebo log. 1. Navíc mají definovanou neurčitou oblast, kdy není rozhodnuto, zda byla přijmuta log. 0 nebo log. 1, ale dosadí se symbol neurčitosti. Vychází se z toho, že je snažší určit, jaké znaky mají být na místě symbolů neurčitosti, než opravovat kódy, kde jsou všechny dvojkové znaky kombinace jasné, ale některé z nich jsou přijaty chybně. Při dané kódové vzdálenosti ρ je největší násobnost opravitelných symbolů neurčitosti t rovna násobnosti zjistitelných chyb, ρ ≥ t+ 1. Skutečnost že vím, na kterém místě kombinace není jasné, zda jde o znak log. 0 nebo log. 1 způsobuje, že postačuje pouze kódová vzdálenost pro odhalení chyby k tomu, abych chybu opravil.