Kódování zdroje

Úvod do teorie kódování (kódování s proměnnou délkou zdroj) s problematikou bezztrátové komprese. Tento zjednodušený problém řeší pouze odesílání unárních symbolů (rozkmitání drátu) k zaslání jednotlivých symbolů. Zdroj kódování se snaží o kompresi dat ze zdroje, aby bylo možné jej přenášet efektivněji.

Začněme s problémem.

Alice a Bob žijí v obydlích na stromě,
které jsou oddělené,

bez přímé viditelnosti mezi sebou.

A potřebují komunikovat.

Rozhodli se natáhnout drát
mezi dvěma domy.

Drát pevně utáhli,

a na každém konci připojili plechovku,

která jim umožní vyslat jejich hlas

slabě po drátu.

[BOB] "Haló?"

[ALICE] Haló? Neslyším tě.

[BOB] Já tě slyším, ale málo.

[ALICE] 1. 2. 3. 4. 5.

Je zde ale problém:

hluk.

Kdykoli, kdy je silný vítr,

není možné slyšet

signál přes hluk.

Potřebují způsob ke zvýšení

úrovně energie signálu,

aby jej oddělili od hluku.

Bob dostal nápad.

Mohou jednoduše na drát zahrát,

což je mnohem jednodušší ke zjištění při hluku.

To ale vede k novému problému.

Jak budou kódovat jejich zprávy při rozkmitání drátu?

Od chvíle, kdy chtěli hrát

deskové hry na dálku,

museli se nejprve vypořádat s nejčastějšími společnými zprávami -

součet dvou čísel na kostkách.

V tomto případě, mohly být zasílané zprávy

myšleny jako výběr

z konečného počtu 'symbolů' -

v tomto případě, jedenáct možných čísel,

kterým říkáme 'diskrétní zdroj.'

Prvně se rozhodli použít nejjednodušší metodu.

Poslali součet jako počet rozkmitání drátu.

K poslání "3" rozkmitali drát třikrát.

"9" devět rozkmitání.

A "12" je dvanáct rozkmitání.

Avšak brzy si uvědomili,

že to trvá mnohem déle, než potřebují.

Z praxe zjistili, že jejich nejvyšší rychlost rozkmitávání

jsou dvě rozkmitání za vteřinu.

Rychleji ne, a byli zmatení.

Dvě rozkmitání za sekundu
může být myšleno jako 'míra' -

nebo 'kapacita' - pro poslání informace tímto způsobem.

A ukazuje se,

že nejčastějším číslem je "7",

takže poslání čísla 7 trvá 3,5 vteřiny.

Alice si pak uvědomila,
že to mohou dělat o mnoho lépe,

pokud změní jejich kódovací strategii.

Uvědomila si, že statistiky
každého zaslaného čísla

tvoří jednoduchý model.

Je jedna cesta, jak zaslat 2.

Jsou dva způsoby,
jak zaslat 3.

Tři způsoby, jak poslat 4.

Čtyři cesty, jak zaslat 5.

Pět způsobů,
jak poslat 6.

A šest způsobů,
jak poslat 7 -

nejčastější součet.

A pět cest k zaslání 8.

Čtyři způsoby, jak zaslat 9 -

a tak dále, až k jednomu způsobu zaslání 12.

Toto je graf znázorňující

počet způsobů k součtu každého čísla.

Tento model je zřejmý.

Nyní změňme graf na

'počet rozkmitání versus každý symbol.'

Postupujme mapováním

nejběžnějšího čísla -

7 - k nejkratšímu signálu - jedno zatáhnutí.

[ZVUK ROZKMITÁNÍ]

Pokračuje k dalšímu
nejpravděpodobnějšímu číslu.

Pokud je tam svazek, jedno náhodně vybere.

V tomto případě, vybírá 6 na dvě rozkmitání,

pak 8 jako tři rozkmitání,

poté zpět k 5 jako čtyři rozkmitání,

a 9 je pět rozkmitání,

zpět ke čtvrtému, dokud nedosáhneme 12,

která je přiřazeno 11 rozkmitání.

Nyní, nejčastější číslo, 7,

může být zasláno za méně než jednu vteřinu -

obrovské zlepšení.

Tato jednoduchá změna jim umožnila zaslat

více informace v průměru za stejný čas.

Vlastně, tato kódovací strategie je optimální

pro tento jednoduchý příklad -

v něm je pro vás nemožné

přijít s kratší metodou

zasílání dvou čísel na kostkách
- využívající stejné rozkmitání.

Avšak po hraní si s drátem za nějaký čas

Boba napadla nová myšlenka.