Teoremele lui Shannon pentru o sursă generală

Teoremele lui Shannon pentru o sursă generală descriu posibilitățile de codificare a unei surse generale folosind coduri separabile. Cu alte cuvinte, sunt descrise capabilitățile maxime de codare fără pierderi realizabile.

Teorema directă

După cum se aplică codării literă cu literă, teorema directă poate fi formulată după cum urmează:

Există un prefix , adică un cod separabil , pentru care lungimea medie a mesajului diferă de entropia normalizată cu cel mult unu :

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

Unde:

$U$ - unele surse de mesaje, precum și setul tuturor mesajelor sale $u_{1},u_{2},...,u_{K)$
${\displaystyle w_{1},w_{2},...,w_{K))$ este lungimea mesajelor sursă după codificare
$E_{U}w\stânga(U\dreapta)$ — lungimea medie a mesajului
$H\stanga(U\dreapta)$ este entropia sursă
$D$ — numărul de litere din alfabetul de codificare (de exemplu, 2 pentru alfabetul binar, 33 pentru codificarea cu majuscule rusești etc.)

Ca o dovadă a teoremei, sunt investigate caracteristicile codului Shannon-Fano . Acest cod îndeplinește condițiile teoremei și are proprietățile indicate.

Teorema inversă

Teorema inversă limitează raportul de compresie maxim care poate fi realizat cu codare fără pierderi. Așa cum este aplicat codificării literă cu literă, descrie o constrângere privind lungimea medie a cuvântului de cod pentru orice cod separabil.

Pentru orice cod separabil cu lungimi , lungimea medie a mesajului este mai mare sau egală cu entropia sursei , normalizată la logaritmul binar al numărului de litere din alfabetul codificatorului: ${\displaystyle w_{1},w_{2},...,w_{K))$ $U$ $D$

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

Literatură

Gabidulin E. M. , Pilipchuk N. I. §3.4 Teoremele lui Shannon pentru sursă // Prelegeri despre teoria informaţiei - MIPT , 2007. - P. 49-52. — 214 p. — ISBN 978-5-7417-0197-3