Shannonovy teorémy pro obecný zdroj

Shannonovy teorémy pro obecný zdroj popisují možnosti kódování obecného zdroje pomocí oddělitelných kódů. Jinými slovy, jsou popsány maximální dosažitelné schopnosti bezeztrátového kódování.

Přímá věta

Pokud jde o kódování písmeno po písmenu, může být přímá věta formulována následovně:

Existuje předpona , tedy oddělitelný kód , pro který se průměrná délka zprávy neliší od normalizované entropie o více než jednu :

E_{U}w\left(U\right)<{\frac {H\left(U\right)}{\log _{2}D))+1

kde:

$U$ - nějaký zdroj zpráv, stejně jako soubor všech jeho zpráv ${\displaystyle u_{1},u_{2},...,u_{K))$
${\displaystyle w_{1},w_{2},...,w_{K))$ je délka zdrojových zpráv po zakódování
$E_{U}w\left(U\right)$ — průměrná délka zprávy
$H\left(U\right)$ je zdrojová entropie
$D$ — počet písmen v kódovací abecedě (například 2 pro binární abecedu, 33 pro kódování velkými ruskými písmeny atd.)

Jako důkaz teorému jsou zkoumány charakteristiky Shannon-Fano kódu . Tento kód splňuje podmínky věty a má uvedené vlastnosti.

Inverzní věta

Inverzní věta omezuje maximální kompresní poměr dosažitelný s bezztrátovým kódováním. Jak je aplikováno na kódování písmeno po písmenu, popisuje omezení průměrné délky kódového slova pro jakýkoli oddělitelný kód.

Pro jakýkoli oddělitelný kód s délkami je průměrná délka zprávy větší nebo rovna zdrojové entropii , normalizované na binární logaritmus počtu písmen v abecedě kodéru: ${\displaystyle w_{1},w_{2},...,w_{K))$ $U$ $D$

{\frac {H\left(U\right)}{\log _{2}D}}\leq E_{U}w\left(U\right)

Literatura

Gabidulin E. M. , Pilipchuk N. I. §3.4 Shannonovy teorémy pro zdroj // Lectures on information theory - MIPT , 2007. - S. 49-52. — 214 s. — ISBN 978-5-7417-0197-3