Teorema sursei de criptare a lui Shannon

În teoria informației, teorema sursei de criptare a lui Shannon (sau teorema de criptare silențioasă) stabilește o limită pentru compresia maximă a datelor și o valoare numerică pentru entropia lui Shannon .

Teorema arată că (atunci când cantitatea de date tinde spre infinit într-un flux de variabile aleatoare distribuite independent și egal (IED)) este imposibil să se comprima datele astfel încât estimarea codului (numărul mediu de biți pe simbol) să fie mai mică decât entropia Shannon a datelor originale, fără pierderea acurateței informațiilor. Cu toate acestea, este posibil să se obțină un cod apropiat de entropia Shannon fără pierderi semnificative.

Teorema sursei de criptare pentru codurile de caractere aduce limite superioare și inferioare la lungimea minimă posibilă a cuvintelor criptate în funcție de entropia cuvântului de intrare (care este reprezentat ca o variabilă aleatorie) și de dimensiunea alfabetului necesar.

Declarație

Codul sursă este o mapare (secvență) din depozitul de informații într-o secvență de caractere alfabetice (de obicei biți), astfel încât caracterul sursă poate fi obținut în mod unic din cifre binare (sursă de codificare fără pierderi) sau obținut cu o oarecare diferență (sursă de codare cu pierderi) . Aceasta este ideea din spatele compresiei datelor.

Sursă de criptare pentru codurile de caractere

În informatică, teorema sursei de criptare (Shannon 1948) afirmă că:

O variabilă aleatorie N cu entropie H ( X ) poate fi comprimată în mai mult de N  H ( X ) biți cu risc neglijabil de pierdere a datelor dacă N merge la infinit, dar dacă compresia este mai mică de N  H ( X ) biți, atunci datele cel mai probabil să se piardă. (MacKay 2003).”

Teorema sursei de criptare pentru codurile de caractere

Fie , să desemnăm două alfabete finite și să fie și să notăm mulțimea tuturor cuvintelor finite din aceste alfabete (ordonate). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Să presupunem că X este o variabilă aleatoare care ia o valoare de la , iar f este un cod descifrabil de la , unde . Fie S o variabilă aleatoare dată de lungimea cuvântului f ( X ). $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Dacă f este optim în sensul că are lungimea minimă a cuvântului pentru X , atunci

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

(Shannon 1948).

Dovada teoremei sursei de criptare

Dat fiind că este un NOR, seria sa temporală X 1 , …, X n este de asemenea un NOR cu entropie H ( X ) în cazul valorilor discrete și cu entropie diferențială în cazul valorilor continue. Teorema sursei de criptare afirmă că pentru fiecare, pentru fiecare estimare mai mare decât entropia resursei, există un n suficient de mare și un criptator care preia n copii NOP ale resursei , , , și o mapează la biți binari într-un asemenea mod că caracterul original poate fi recuperat din biți binari, X cu o probabilitate de cel puțin . $X$ $\epsilon >0$ $X^{1:n}$ $n.(H(X)+\epsilon )$ $X^{1:n}$ $1-\epsilon$

Dovada

Hai să luăm câteva . formula pentru, , arată astfel: $\epsilon >0$ $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)\right|<\epsilon \right\}$

AEP arată că pentru n suficient de mare , secvența generată de la sursă este nesigură în cazul tipic - , convergent. În cazul suficient de mare: n , (vezi AEP) $A_{n}^{\epsilon }$ $P(A_{n}^{\epsilon })>1-\epsilon$

Definiția mulțimilor tipice implică faptul că acele secvențe care se află într-o mulțime tipică satisfac:

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

Rețineți că:

Probabilitatea ca secvența să fi fost obținută din $X$

${A_{\epsilon }}^{(n))$ mai mult decât $1-\epsilon$

$\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon ))$ întrucât probabilitatea populaţiei totale este cea mai mare. ${A_{\epsilon }}^{(n))$

$\left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon ))$ . Pentru demonstrație, utilizați o limită de probabilitate superioară pentru fiecare termen în cazul tipic și o limită inferioară pentru cazul general . ${A_{\epsilon }}^{(n))$

Începând cu biți este suficient pentru a distinge orice șir $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Algoritm de criptare: codificatorul verifică dacă secvența de intrare este falsă, dacă da, apoi returnează indexul frecvenței de intrare în secvență, dacă nu, atunci returnează un număr de cifre aleatoare. valoare numerică. Dacă probabilitatea de intrare este incorectă în secvență (cu o frecvență de aproximativ ), atunci codificatorul nu generează o eroare. Adică, probabilitatea de eroare este mai mare decât $n.(H(X)+\epsilon )$ $1-\epsilon$ $\epsilon$

Dovada reversibilității Dovada reversibilității se bazează pe faptul că se cere să se arate că pentru orice secvență de dimensiune mai mică decât (în sensul exponentului) va acoperi frecvența șirului mărginit de 1. $A_{n}^{\epsilon }$

Dovada teoremei sursei de criptare pentru codurile de caractere

Fie lungimea cuvântului pentru fiecare posibil ( ). Să definim , unde C este ales în așa fel încât: . $si}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Apoi

{\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}}+\sum _{i=1}^{n}p_{i}\log _{2}C=\\&=-\sum _{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}}

unde a doua linie este inegalitatea Gibbs și a cincea linie este inegalitatea Kraft , . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

pentru a doua inegalitate o putem stabili

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

asa de

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

și apoi

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

și

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

Astfel, minimul S satisface

{\begin{aliniat}\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{aliniat}}

Note

Cover, Thomas M. Capitolul 5: Comprimarea datelor // Elemente de teoria informației (neopr.) . - John Wiley & Sons , 2006. - ISBN 0-471-24195-4 .
C. E. Shannon, „ A Mathematical Theory of Communication ”, Bell System Technical Journal , vol. 27, pp. 379-423, 623-656, iulie, octombrie 1948