Shannonova věta o zdroji šifrování

V teorii informace nastavuje Shannonova věta o zdroji šifrování (nebo věta o tichém šifrování) limit maximální komprese dat a číselnou hodnotu Shannonovy entropie .

Věta ukazuje, že (když má množství dat tendenci k nekonečnu v proudu nezávisle a rovnoměrně distribuovaných (IED) náhodných proměnných), není možné komprimovat data tak, aby odhad kódu (průměrný počet bitů na symbol) byl menší než Shannonova entropie původních dat bez ztráty přesnosti informací. Je však možné získat kód blízký Shannonově entropii bez výrazných ztrát.

Věta o zdroji šifrování pro kódy znaků přináší horní a dolní mez minimální možné délky zašifrovaných slov jako funkci entropie vstupního slova (které je reprezentováno jako náhodná veličina) a velikosti požadované abecedy.

Prohlášení

Zdrojový kód je mapování (sekvence) z úložiště informací do sekvence abecedních znaků (obvykle bitů), takže zdrojový znak lze jednoznačně získat z binárních číslic (bezeztrátový zdroj kódování) nebo získat s určitým rozdílem (zdroj se ztrátovým kódováním) . To je myšlenka komprese dat.

Zdroj šifrování pro kódy znaků

V informatice teorém o zdroji šifrování (Shannon 1948) říká, že:

N náhodná proměnná s entropií H ( X ) může být komprimována do více než NH  ( X ) bitů se zanedbatelným rizikem ztráty dat, pokud N jde do nekonečna, ale pokud je komprese menší než N H ( X ) bitů, pak s největší pravděpodobností dojde ke ztrátě dat. (MacKay 2003). 

Věta o zdroji šifrování pro kódy znaků

Nechť , označí dvě konečné abecedy a nechť a označí množinu všech konečných slov z těchto abeced (uspořádaných). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Předpokládejme, že X je náhodná proměnná, která nabývá hodnoty od , a f je dešifrovatelný kód od do , kde . Nechť S představuje náhodnou veličinu danou délkou slova f ( X ). $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Pokud je f optimální v tom smyslu, že má minimální délku slova pro X , pak

{\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}} +1

(Shannon 1948).

Důkaz věty o zdroji šifrování

Vzhledem k tomu , že se jedná o NOR, jeho časová řada X 1 , …, X n je také NOR s entropií H ( X ) v případě diskrétních hodnot as diferenciální entropií v případě spojitých hodnot. Věta o zdroji šifrování říká, že pro každý, pro každý odhad větší než entropie zdroje, existuje dostatečně velké n a šifrovač, který bere n NOP kopií zdroje , , , a mapuje jej na binární bity takovým způsobem. že původní znak lze obnovit z binárních bitů, X s pravděpodobností alespoň . $X$ $\epsilon >0$ $X^{1:n}$ $n.(H(X)+\epsilon )$ $X^{1:n}$ $1-\epsilon$

Důkaz

Vezměme si nějaké . vzorec pro, , vypadá takto: $\epsilon >0$ ${\displaystyle A_{n}^{\epsilon ))$

$A_{n}^{\epsilon }=\;\left\{x_{1}^{n}:\left|-{\frac {1}{n}}\log p(X_{1} ,X_{2},...,X_{n})-H_{n}(X)\vpravo|<\epsilon \right\}$

AEP ukazuje, že pro dostatečně velké n je sekvence generovaná ze zdroje nespolehlivá v typickém případě - , konvergentní. V případě dostatečně velké: n , (viz AEP) ${\displaystyle A_{n}^{\epsilon ))$ $P(A_{n}^{\epsilon })>1-\epsilon$

Z definice typických množin vyplývá, že posloupnosti, které leží v typické množině, splňují:

2^{-n(H(X)+\epsilon )}\leq p(x_{1},x_{2},...,x_{n})\leq 2^{-n(H (X)-\epsilon )}

Všimněte si, že:

Pravděpodobnost, ze které byla sekvence získána $X$

${\displaystyle {A_{\epsilon }}^{(n)))$ více než $1-\epsilon$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )))$ protože celková pravděpodobnost populace je největší. ${\displaystyle {A_{\epsilon }}^{(n)))$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )))$ . Pro důkaz použijte horní hranici pravděpodobnosti pro každý termín v typickém případě a dolní hranici pro obecný případ . ${\displaystyle {A_{\epsilon }}^{(n)))$

K rozlišení libovolného řetězce stačí začít bity $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Šifrovací algoritmus: kodér zkontroluje, zda je příchozí sekvence nepravdivá, pokud ano, vrátí index příchozí frekvence v sekvenci, pokud ne, vrátí náhodné číslo. číselná hodnota. Pokud je vstupní pravděpodobnost nesprávná v sekvenci (s frekvencí asi ), pak kodér negeneruje chybu. To znamená, že pravděpodobnost chyby je vyšší než $n.(H(X)+\epsilon )$ $1-\epsilon$ $\epsilon$

Důkaz vratnosti Důkaz vratnosti je založen na skutečnosti, že je třeba prokázat, že pro jakoukoli posloupnost o velikosti menší než (ve smyslu exponentu) pokryje frekvenci posloupnosti ohraničené 1. ${\displaystyle A_{n}^{\epsilon ))$

Důkaz teorému o zdroji šifrování pro kódy znaků

Nechť slovo délka pro každou možnou ( ). Definujme , kde C je zvoleno tak, že: . $s_{i}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Pak

{\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\leqslant \\&\leqslant - \sum _{i=1}^{n}p_{i}\log _{2}q_{i}=\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\součet _{i=1}^{n}p_{i}\log _{2}C=\\&=-\součet _{i=1 }^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\leqslant \\&\leqslant -\sum _{i=1}^{ n}-s_{i}p_{i}\log _{2}a\leqslant \\&\leqslant \mathbb {E} S\log _{2}a,\\\end{aligned}}

kde druhý řádek je Gibbsova nerovnost a pátý řádek je Kraftova nerovnost , . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

pro druhou nerovnost můžeme nastavit

s_{i}=\lceil -\log _{a}p_{i}\rceil ,

tak

-\log _{a}p_{i}\leqslant s_{i}<-\log _{a}p_{i}+1,

a pak

a^{-s_{i}}\leqslant p_{i}

\sum a^{-s_{i}}\leqslant \sum p_{i}=1.

Minimální S tedy vyhovuje

{\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}<\\&<\sum p_{i}\left(-\log _{a}p_{i }+1\right)=\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1=\\&= {\frac {H(X)}{\log _{2}a}}+1.\\\end{aligned}}

Poznámky

Cover, Thomas M. Kapitola 5: Komprese dat // Prvky teorie informace (neopr.) . - John Wiley & Sons , 2006. - ISBN 0-471-24195-4 .
C. E. Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , sv. 27, str. 379-423, 623-656, červenec, říjen 1948