Jednoznačná dekódovateľnosť

Hovoríme, že kód je jednoznačne dekódovateľný, ak nie je viacznačne dekódovateľný. Inak povedané, existuje iba jedna možnosť, ako daný reťazec pozostávajúci z kódových symbolov dekódovať. Ak má byť kód použiteľný, tak by mal byť jednoznačne dekódovateľný.

Keď sa pozrieme na kód v tabuľke 2.5, zistíme, že nie je jednoznačne dekódovateľný. Pokiaľ máme dekódovať sekvenciu , tak nevieme presne určiť k nej prislúchajúci zdrojový znak, teda znak, z ktorého vznikla .

Tabuľka 2.5:Nejednoznačne dekódovateľný kód

Zdrojový symbol	Kódové slovo

Vráťme sa ku kódu B (tabuľka 2.2) Predpokladajme, že sme kódovali sekvenciu (symbol nasledovaný symbolom ). Kód B, podľa tabuľky 2.2, zakóduje túto dvojicu ako a , teda dostaneme sekvenciu . Dekóder by v tomto momente nebol schopný jednoznačne určiť, akým spôsobom táto sekvencia vznikla ( , , , ...). Teda tento kód nespĺňa podmienku jednoznačnej dekódovateľnosti a preto je nepoužiteľný.

Kód A (tabuľka 2.1) je jednoznačne dekódovateľný. Všetky kódové slová majú dĺžku tri, teda pri dekódovaní vieme, že nové kódové slovo začína každé tri symboly. Jeho hlavnou nevýhodou je veľké .

Kód C (tabuľka 2.3) je tiež jednoznačne dekódovateľný, pretože spĺňa podmienku prefixovosti, tj. žiadne kratšie kódové slovo nie je prefixom dlhšieho. Kódy spĺňajúce túto podmienku nazývame prefixové kódy. Každý prefixový kód sa dá zobraziť ako binárny strom, ktorého listy predstavujú zdorjové symboly. Binárny strom, ktorý zobrazuje kód C, je na obrázku 2.1. Kódové slovo priradené danému zdrojovému symbolu je potom cesta po ohodnotených hranách v strome, ktorá vedie od koreňa stromu k danému zdrojovému symbolu. Pri dekódovaní kódového slova algoritmus sleduje cestu od koreňa stromu k jeho listom. Po dosiahnutí listu je k nemu prislúchajúci zdrojový symbol dekódovaný. Napríklad majme reťazec

.

.

.

Obrázok 2.1: Kód C v binárnom strome

Platí tvrdenie, že každý prefixový kód je jednoznačne dekódovateľný, ale neplatí tvrdenie opačné. Existujú kódy, ktoré nie sú prefixové, ale sú jednoznačne dekódovateľné. Ako príklad si môžeme zobrať kód D (tabuľka 2.4). Prefixovosť je porušená kódovým slovom 0 (prislúcha ), ktorý je prefixom 011 (prislúcha ). Všimnime si, že zvyšných šesť symbolov začína a žiadny nie je prefixom iného. Naviac, žiadny z týchto šiestich kódových slov nezačína prefixom , takže sa nikdy nepomýlime na konci kódového slova pre . Keď pri dekódovaní nového kódového slova je prvý sybmol 0, pozrieme sa ešte na ďalšie dva kódové symboly. Ak ich hodnota je , potom všetky tri symboly tvoria kódové slovo , inak je prvý symbol kódové slovo a nasledujúci symbol je začiatkom ďalšieho kódového slova. Táto vlastnosť je aj rozhodujúca pre tento kód, aby bol jednoznačne dekódovateľný.

Keď si zoberieme reťazec z predchádzajúceho príkladu a pokúsime sa ho dekódovať naším kódom D, dostaneme nasledujúce sekvencie

.