Optimální (entropické) kódování informačního zdroje

Podľa teórie informácie, entropické kódovanie je bezstratová kompresia dát, ktorá je nezávislá na vlastnostiach média. Pri efektívnom kódovaní ide o to, nájsť také, pri ktorom bude priemerná prenosová rýchlosť správ cez informačný kanál čo najväčšia, t.j. priemerný počet signálov použitých na zakódovanie správy bude čo najmenší. Inými slovami, pri entropickom kódovaní sa nahrádzajú symboly rovnakej dĺžky vo vstupnej správe kódovými slovami rôznej dĺžky a to tak, že najčastejšie sa vyskytujúce symboly majú priradené najkratšie kódové slová. Pre entropické kódovanie platí vlastnosť prefixu – žiadne kódové slovo nie je začiatkom iného kódového slova.

Príklady entropického kódovania

Najznámejšie algoritmy entropického kódovania vynašli:

• C. Shannon
• D. Huffman
• R. Fano

Huffmanove kódovanie

Je založené na predpoklade znalosti pravdepodobnosi výskytu kódovaných znakov. Pri tvorbe Huffmanovho kódu sa generujú binárne stromy, ktoré umožňujú vytvorenie kódových slov, pomocou cesty z počiatočného do koncového uzlu.

Shannon-Fanove kódovanie

Podobne ako pri Huffmanovom kódovaní, aj tu je výsledkom kódovania binárny strom, ktorý sa ale na rozdiel od neho konšturuje od koreňa. Pri kódovaní sa hodnotí pravdepodobnosť výskytu slov a priraďuje sa im kódové slovo zodpovedajúcej dľžky. Tento typ kódovania nám vydáva optimálny kód často,nie však vždy.

Aritmetické kdovanie

Pri aritmetickom kódovaní sú správy reprezentované intervalom reálnych čísel medzi 0 a 1. So zväčšovaním správy sa zmenšuje interval potrebný na reprezentáciu a počet bitov potrebných na špecifikáciu intervalu narastá. Po sebe idúce symboly správy redukujú veľkosť intervalu podľa pravdepodobností vygenerovaných modelom. Častejšie symboly redukujú rozsah viac, ako menej časté symboly a preto pridávajú menej bitov do správy.