Základy kódování

Kódování (encoding) a dekódování (decoding) se od šifrování (encrypting) a dešifrování (decrypting) liší v úmyslu, který s datovým vstupem máme. Zatímco šifrování převádí vstup do nečitelné podoby s tím účelem, aby byl původní vstup pro neautorizované osoby zcela nedostupný, tak kódování převádí vstup do nečitelné podoby pouze pro to, aby měl výstup lepší vlastnosti. K převodu zakódované zprávy do výchozí podoby není potřeba znát žádný klíč apod. Lepšími vlastnostmi zakódovaného výstupu se rozumí například, aby šel snadno přenést přes zašuměný kanál, měl menší velikost (komprese dat), či aby šlo snáz detekovat chybu po přenosu (kontrolní kódy).

Základní pojmy

Abeceda: konečná množina znaků, označme ji třeba A, např. A = {A, B, C}
Slovo (řetězec, zpráva) w nad abecedou A: je konečná posloupnost znaků z A, počet takových znaků je délka slova w, značí se |w|, množinu všech (možných) slov nad A značíme A*.
Kód: je v podstatě zobrazení (matematicky funkce) z počáteční abecedy do množiny všech slov koncové abecedy.

Prefixové kódy

Jsou takové kódy, kde žádné slovo není prefixem (česky předponou) jiného slova. Například uvažujme následující kódování:

A = 1
B = 01
C = 00

takové kódování vstupní abecedy A = {A, B, C} je prefixové. Naopak například Morseova abeceda NENÍ prefixová (existují slova, která jsou prefixem jiných, například A = ·- je prefixem L = ·-·· a tak dále). To má za následek toliko, že jednotlivé znaky Morseovy abecedy musí být při odesílání odděleny odmlkou (jinak by nebylo možné dekódovat), což nemusí být vždy praktické.

Kraftova a McMillanova nerovnost

Kraftova nerovnost představuje základní vlastnost tzv. prefixových kódů. Specifikuje omezení na délky kódových slov, jenž musí kód splňovat, aby mohl být prefixový.

Předpokládejme, že máme k-znakovou vstupní abecedu, kterou bychom chtěli zakódovat do výstupní l-znakové výstupní abecedy s délkami jednotlivých kódových slov ve výstupní abecedě:

r₁, r₂, ···, r_k

pak musí platit následující Kraftova nerovnost:

∑_{i = 1}^k l^-r_i = l^-r₁ + l^-r₂ + ··· + l^-r_k ≤ 1

aby byl kód jednoznačně dekódovatelný. Pokud tato nerovnost neplatí, nelze kód dekódovat jednoznačně, tedy se některé znaky namapují na jiné.

Například pro naši ukázku máme k = 3 (počet písmen abecedy A = {A, B, C}), dále l = 2 (počet symbolů výstupní abecedy, kde máme pouze symboly 0 a 1), nakonec r₁ = 1, r₂ = 2, r₃ = 2 (protože A se kóduje na jeden znak, B na dva a C také na dva znaky výstupní abecedy). Kraftova nerovnost tedy bude mít formu:

∑_{i = 1}^k l^-r_i = 2^-1 + 2^-2 + 2^-2 = 1 ≤ 1

Naprosto identicky je zavedena McMillanova nerovnost (někdy se oboje uvádí pouze jako Kraft-McMillanova nerovnost). Ta se vztahuje na každé jednoznačně dekódovatelné kódování. Jinými slovy, pro každé jednoznačně dekódovatelné kódování platí uvedená (Kraftova) nerovnost. Z toho také vyplývá, že 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.

Základní témata v kódování