Prima teoremă a lui Shannon

În teoria informației , prima teoremă a lui Shannon (sau teorema codării sursei ) stabilește limite la compresia maximă posibilă a unui set de date și definește semnificația operațională a entropiei .

Teorema stabilește că, pentru o serie de variabile aleatorii independente și distribuite identic (iid) de lungime care tinde spre infinit, nu este posibilă comprimarea datelor într-un mesaj mai scurt decât entropia totală fără pierderea informațiilor . Dimpotrivă, sunt posibile compresii în mod arbitrar apropiate de valoarea entropiei, cu probabilitatea pierderii informațiilor la fel de mică pe cât se dorește.

Teorema de codificare sursă pentru simbolurile de cod stabilește o limită inferioară și superioară la lungimea minimă așteptată a unei serii de cuvinte de cod, în funcție de entropia cuvântului de intrare (văzut ca o variabilă aleatorie ) și de dimensiunea alfabetului luat în considerare .

Codificare sursă

Codificarea sursă este o mapare de la o secvență de simboluri generate de o sursă la o secvență de simboluri ale unui alfabet (de obicei binar), astfel încât simbolurile sursă pot fi preluate exact din biți (codificare fără pierderi) sau recuperate cu o anumită distorsiune (pierderi) codificare). Acesta este conceptul din spatele compresiei datelor .

Cu alte cuvinte, se poate spune că este modalitatea cu care fiecare eveniment asociat unei surse discrete este codificat prin intermediul unei secvențe de simboluri.

Calitatea informațiilor

Codificarea sursă introduce conceptele de bază ale „calității informației”:

cantitatea de informații $I(x)$ ${\ displaystyle I (x)}$ $Eu (x)$ este dat de $I(x)=-{\log _{2}P(x)}$ ${\ displaystyle I (x) = - {\ log _ {2} P (x)}}$ ${\ displaystyle I (x) = - {\ log _ {2} P (x)}}$ , unde este $P(x)$ ${\ displaystyle P (x)}$ $P (x)$ este probabilitatea informației. Prin urmare, se poate spune că între informația în sine și probabilitatea acesteia există o relație invers proporțională (o probabilitate mare duce la o cantitate redusă de informații și invers).

Dorind, acum, să stabilim o unitate de măsură, este adecvat să ne referim la cazul în care sunt necesare informațiile minime pentru a lua o decizie. Ignorând cazul extrem (când evenimentul este sigur) în care există un singur rezultat, cazul cu cea mai mică nevoie de informații este unul în care există două rezultate la fel de probabile la fel (de exemplu: aruncarea unei monede).

Bitul este definit ca cantitatea de informații necesară și suficientă pentru a discrimina și a decide între două evenimente la fel de probabile: $1bit=K{\log _{2}(1/2)}$ ${\ displaystyle 1bit = K {\ log _ {2} (1/2)}}$ ${\ displaystyle 1bit = K {\ log _ {2} (1/2)}}$ , unde este $K.$ ${\ displaystyle K}$ $K.$ este indicele de proporționalitate.

Informația mediată sau entropia este ponderată de contribuția informațiilor prin probabilitatea sa: $\sum _{i=1}^{n}P(x)*I(x)$ ${\ displaystyle \ sum _ {i = 1} ^ {n} P (x) * I (x)}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} P (x) * I (x)}$ [bit / simbol].
Viteza de modulație sau viteza de transmisie este viteza la care simbolurile sunt emise de sursă: $V={\frac {1}{Ts}}$ ${\ displaystyle V = {\ frac {1} {Ts}}}$ ${\ displaystyle V = {\ frac {1} {Ts}}}$ , unde este $T. s$ ${\ displaystyle Ts}$ ${\ displaystyle Ts}$ este durata simbolului.
Viteza medie de transmisie a informațiilor despre sistem sau rata de biți se calculează cu: $R=V*H(x)$ ${\ displaystyle R = V * H (x)}$ ${\ displaystyle R = V * H (x)}$ .

Alți parametri importanți pot fi rezumați după cum urmează:

Lungimea medie a simbolului $\sum _{i=1}^{n}P(x)*ni$ ${\ displaystyle \ sum _ {i = 1} ^ {n} P (x) * ni}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} P (x) * ni}$ (ni = lungimea codului)
Randamentul codului $\eta ={\frac {H(x)}{L}}$ ${\ displaystyle \ eta = {\ frac {H (x)} {L}}}$ ${\ displaystyle \ eta = {\ frac {H (x)} {L}}}$ (η ia valori de la 0 la 1)
Redundanţă $\gamma =1-\eta$ ${\ displaystyle \ gamma = 1- \ eta}$ ${\ displaystyle \ gamma = 1- \ eta}$ .

Teorema codării sursei

În teoria informației, teorema codării sursei ( Claude Shannon , 1948 ) afirmă că:

" $Nu.$ ${\ displaystyle N}$ $Nu.$ iid variabile aleatorii, fiecare cu entropie $H(X)$ ${\ displaystyle H (X)}$ $H (X)$ poate fi comprimat în mai mult de $NH(X)$ ${\ displaystyle NH (X)}$ ${\ displaystyle NH (X)}$ biți cu o probabilitate de pierdere a informațiilor pe cât doriți, pentru a avea tendința $Nu.$ ${\ displaystyle N}$ $Nu.$ la nesfârșit; dimpotrivă, dacă sunt comprimate în mai puțin de $NH(X)$ ${\ displaystyle NH (X)}$ ${\ displaystyle NH (X)}$ bit este practic sigur că unele informații vor fi pierdute. "

Teorema de codare sursă pentru simboluri de cod

Este $X$ ${\ displaystyle X}$ $X$ o variabilă aleatorie cu valori într-un alfabet finit $\Sigma _{1}$ ${\ displaystyle \ Sigma _ {1}}$ $\ Sigma _ {1}$ și fie $f$ ${\ displaystyle f}$ $f$ un cod descifrabil (adică o funcție unică) din $\Sigma _{1}^{*}$ ${\ displaystyle \ Sigma _ {1} ^ {*}}$ ${\ displaystyle \ Sigma _ {1} ^ {*}}$ la $\Sigma _{2}^{*}$ ${\ displaystyle \ Sigma _ {2} ^ {*}}$ ${\ displaystyle \ Sigma _ {2} ^ {*}}$ , unde este $|\Sigma _{2}|=a$ ${\ displaystyle | \ Sigma _ {2} | = a}$ ${\ displaystyle | \ Sigma _ {2} | = a}$ . Fie S lungimea rezultată a cuvântului cod $f(X)$ ${\ displaystyle f (X)}$ $f (X)$ .

De sine $f$ ${\ displaystyle f}$ $f$ este optim în sensul că are cea mai mică lungime așteptată pentru cuvântul cod $X$ ${\ displaystyle X}$ $X$ , asa de

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

{\ displaystyle {\ frac {H (X)} {\ log _ {2} a}} \ leq \ mathbb {E} \ left \ lbrace S \ right \ rbrace <{\ frac {H (X)} {\ jurnal _ {2} a}} + 1}

{\ displaystyle {\ frac {H (X)} {\ log _ {2} a}} \ leq \ mathbb {E} \ left \ lbrace S \ right \ rbrace <{\ frac {H (X)} {\ jurnal _ {2} a}} + 1}

(Shannon 1948)

Dovadă: teorema codării sursei

Lasa-i sa fie $X$ ${\ displaystyle X}$ $X$ o sursă de variabile iid e $X_{1},...,X_{n}$ ${\ displaystyle X_ {1}, ..., X_ {n}}$ $X_ {1}, ..., X_ {n}$ o serie de rezultate cu entropie $H(X)$ ${\ displaystyle H (X)}$ $H (X)$ în cazul discret și entropie diferențială egală în cazul continuu. Teorema de codificare sursă afirmă că pentru fiecare $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ , este un $n$ ${\ displaystyle n}$ $n$ suficient de mare și un codificator care necesită $n$ ${\ displaystyle n}$ $n$ scoate iidul sursei și le mapează $n.(H(X)+\varepsilon )$ ${\ displaystyle n. (H (X) + \ varepsilon)}$ ${\ displaystyle n. (H (X) + \ varepsilon)}$ bit, astfel încât simbolurile sursă $X^{1:n}$ ${\ displaystyle X ^ {1: n}}$ ${\ displaystyle X ^ {1: n}}$ sunt recuperabile cu probabilitate de cel puțin $1-\varepsilon$ ${\ displaystyle 1- \ varepsilon}$ ${\ displaystyle 1- \ varepsilon}$ .

Dovada accesibilității

Cineva este fix $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ . Ansamblul tipic, $A_{n}^{\varepsilon }$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ , este definit ca

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

Proprietatea echipațiunii asimptotice (AEP) arată că pentru a $n$ ${\ displaystyle n}$ $n$ suficient de mare, probabilitatea ca o secvență generată de sursă să cadă în setul tipic, $A_{n}^{\varepsilon }$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ , tinde la unul. În special pentru un $n$ ${\ displaystyle n}$ $n$ suficient de mare, $P(A_{n}^{\varepsilon })>1-\varepsilon$ ${\ displaystyle P (A_ {n} ^ {\ varepsilon})> 1- \ varepsilon}$ ${\ displaystyle P (A_ {n} ^ {\ varepsilon})> 1- \ varepsilon}$ .

Definiția unui set tipic implică faptul că secvențele care se încadrează în setul tipic satisfac condiția

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

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

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

Rețineți că:

Probabilitatea ca o secvență de $X$ ${\ displaystyle X}$ $X$ intră ${A_{\varepsilon }}^{(n)}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ este mai mare decât $1-\varepsilon$ ${\ displaystyle 1- \ varepsilon}$ ${\ displaystyle 1- \ varepsilon}$
$\left|{A_{\varepsilon }}^{(n)}\right|\leq 2^{n(H(X)+\varepsilon )}$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}}$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}}$ , având în vedere că probabilitatea setului ${A_{\varepsilon }}^{(n)}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ este cel mult unul.
$\left|{A_{\varepsilon }}^{(n)}\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ geq (1- \ varepsilon) 2 ^ {n (H (X) - \ varepsilon)}}$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ geq (1- \ varepsilon) 2 ^ {n (H (X) - \ varepsilon)}}$ . Pentru dovadă este suficient să se utilizeze limita superioară a probabilității fiecărui termen din setul tipic și limita inferioară a probabilității setului set ${A_{\varepsilon }}^{(n)}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ ${\ displaystyle {A _ {\ varepsilon}} ^ {(n)}}$ .

De cand $\left|{A_{\varepsilon }}^{(n)}\right|\leq 2^{n(H(X)+\varepsilon )},n.(H(X)+\varepsilon )\;$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}, n. (H (X) + \ varepsilon ) \;}$ ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}, n. (H (X) + \ varepsilon ) \;}$ biții sunt suficienți pentru a reprezenta fiecare șir ca întreg.

Algoritmul de codificare: codificatorul verifică dacă secvența de intrare se încadrează în ansamblul tipic; dacă da, scoate indexul secvenței de intrare în setul tipic; dacă nu, codificatorul produce un număr binar arbitrar $n.(H(X)+\varepsilon )$ ${\ displaystyle n. (H (X) + \ varepsilon)}$ ${\ displaystyle n. (H (X) + \ varepsilon)}$ . Dacă secvența se încadrează în setul tipic, acest lucru se întâmplă cu probabilitatea de cel puțin $1-\varepsilon$ ${\ displaystyle 1- \ varepsilon}$ ${\ displaystyle 1- \ varepsilon}$ , codificatorul nu face greșeli. Prin urmare, probabilitatea erorii codificatorului este mai mică de $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ .

Dovada reversului

Reversul se arată arătând că orice set de dimensiuni mai mic decât $A_{n}^{\varepsilon }$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ , ar avea probabilitate la limită cu siguranță mai mică de 1.

Dovadă: teorema codării sursei pentru simbolurile de cod

Este $s_{i}$ ${\ displaystyle s_ {i}}$ $da$ lungimea fiecărui cuvânt cod posibil $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ ( $i=1,\ldots ,n$ ${\ displaystyle i = 1, \ ldots, n}$ $i = 1, \ ldots, n$ ). Definit $q_{i}=a^{-s_{i}}/C$ ${\ displaystyle q_ {i} = a ^ {- s_ {i}} / C}$ ${\ displaystyle q_ {i} = a ^ {- s_ {i}} / C}$ , unde este $C.$ ${\ displaystyle C}$ $C.$ este astfel încât $\sum q_{i}=1$ ${\ displaystyle \ sum q_ {i} = 1}$ ${\ displaystyle \ sum q_ {i} = 1}$ .

Atunci

{\begin{array}{rcl}H(X)&=&-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&&\\&\leq &-\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}\log _{2}C\\&&\\&\leq &-\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&&\\&\leq &\mathbb {E} \left\lbrace S\right\rbrace \log _{2}a\\\end{array}}

{\ displaystyle {\ begin {array} {rcl} H (X) & = & - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} \\ && \ \ & \ leq & - \ 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} \ log _ {2} C \\ && \\ & \ leq & - \ sum _ {i = 1} ^ {n} -s_ {i} p_ {i} \ log _ {2} a \\ && \\ & \ leq & \ mathbb {E} \ left \ lbrace S \ dreapta \ rbrace \ log _ {2} a \\\ end {array}}}

{\ displaystyle {\ begin {array} {rcl} H (X) & = & - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} \\ && \ \ & \ leq & - \ 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} \ log _ {2} C \\ && \\ & \ leq & - \ sum _ {i = 1} ^ {n} -s_ {i} p_ {i} \ log _ {2} a \\ && \\ & \ leq & \ mathbb {E} \ left \ lbrace S \ dreapta \ rbrace \ log _ {2} a \\\ end {array}}}

unde a doua linie derivă din inegalitatea Gibbs și a patra din inegalitatea Kraft-McMillan : $C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1$ ${\ displaystyle C = \ sum _ {i = 1} ^ {n} a ^ {- s_ {i}} \ leq 1}$ ${\ displaystyle C = \ sum _ {i = 1} ^ {n} a ^ {- s_ {i}} \ leq 1}$ Așadar $\log C\leq 0$ ${\ displaystyle \ log C \ leq 0}$ ${\ displaystyle \ log C \ leq 0}$ .

pentru a doua inegalitate pe care o putem impune

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

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

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

astfel încât

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

{\ displaystyle - \ log _ {a} p_ {i} \ leq s_ {i} <- \ log _ {a} p_ {i} +1}

{\ displaystyle - \ log _ {a} p_ {i} \ leq s_ {i} <- \ log _ {a} p_ {i} +1}

prin urmare

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

{\ displaystyle a ^ {- s_ {i}} \ leq p_ {i}}

{\ displaystyle a ^ {- s_ {i}} \ leq p_ {i}}

Și

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

{\ displaystyle \ sum a ^ {- s_ {i}} \ leq \ sum p_ {i} = 1}

{\ displaystyle \ sum a ^ {- s_ {i}} \ leq \ sum p_ {i} = 1}

și din inegalitatea Kraft, există un cod unic cu cuvinte cod care au acea lungime. Deci minimul $S.$ ${\ displaystyle S}$ $S.$ satisface

{\begin{matrix}\mathbb {E} \left\lbrace S\right\rbrace &=&\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{matrix}}

{\ displaystyle {\ begin {matrix} \ mathbb {E} \ left \ lbrace S \ right \ rbrace & = & \ 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 {matrix}}}

{\ displaystyle {\ begin {matrix} \ mathbb {E} \ left \ lbrace S \ right \ rbrace & = & \ 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 {matrix}}}

Extindere la surse independente non-staționare

Codificare sursă fără pierderi cu rată fixă pentru surse independente discrete și non-staționare

Să definim setul tipic $A_{n}^{\varepsilon }$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ ${\ displaystyle A_ {n} ^ {\ varepsilon}}$ ca

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

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

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

Apoi pentru un dat $\delta >0$ ${\ displaystyle \ delta> 0}$ $\ delta> 0$ , Pentru o $n$ ${\ displaystyle n}$ $n$ suficient de mare, $\Pr(A_{n}^{\varepsilon })>1-\delta$ ${\ displaystyle \ Pr (A_ {n} ^ {\ varepsilon})> 1- \ delta}$ ${\ displaystyle \ Pr (A_ {n} ^ {\ varepsilon})> 1- \ delta}$ Acum ne limităm la codificarea secvențelor din setul tipic, iar metoda obișnuită de codificare arată că cardinalitatea acestui set este mai mică de $2^{n({\bar {H_{n}}}(X)+\varepsilon )}$ ${\ displaystyle 2 ^ {n ({\ bar {H_ {n}}} (X) + \ varepsilon)}}$ ${\ displaystyle 2 ^ {n ({\ bar {H_ {n}}} (X) + \ varepsilon)}}$ . Deci, în medie, ${\bar {H_{n}}}(X)+\varepsilon$ ${\ displaystyle {\ bar {H_ {n}}} (X) + \ varepsilon}$ ${\ displaystyle {\ bar {H_ {n}}} (X) + \ varepsilon}$ bitn sunt suficiente pentru a codifica secvența cu o probabilitate de decodificare corectă mai mare de $1-\delta$ ${\ displaystyle 1- \ delta}$ ${\ displaystyle 1- \ delta}$ , unde este $\varepsilon \;{\mbox{ e }}\;\delta$ ${\ displaystyle \ varepsilon \; {\ mbox {e}} \; \ delta}$ ${\ displaystyle \ varepsilon \; {\ mbox {e}} \; \ delta}$ pot fi făcute cât de mici doriți prin creștere $n$ ${\ displaystyle n}$ $n$ .