Teorema codării sursei
De codificare Teorema sursă (sau prima teorema lui Shannon, sau chiar teorema de codificare fără zgomot) este o teoremă în informații teorie , a declarat de Claude Shannon în 1948, care prevede limita teoretică pentru comprimarea unei surse.
Teorema arată că nu se poate comprima un lanț de variabile aleatoare i.id , când lungimea acesteia tinde spre infinit, astfel încât lungimea medie a codurilor variabilelor este mai mică decât entropia variabilei sursă. Cu toate acestea, putem avea compresie cu o lungime medie a codului arbitrar apropiată de entropie atunci când lungimea lanțului tinde spre infinit.
Enunțuri ale teoremei
Teorema codării sursei
Fie o variabilă aleatorie , să setăm secvența variabilelor aleatorii iid cu distribuție și notând lungimea minimă a unui cod pentru cel mult eroare de probabilitate .
X{\ displaystyle X}Xnu=X1X2...Xnu{\ displaystyle X ^ {n} = X_ {1} X_ {2} ... X_ {n}}nu{\ displaystyle n}X{\ displaystyle X}L(Da,δ){\ displaystyle L (Y, \ delta)}Da{\ displaystyle Y}δ{\ displaystyle \ delta}
Teorema afirmă că , adică, tinde spre infinit, care nu poate fi comprimat în mai puțini biți fără pierderea aproape sigură a informațiilor. Pe de altă parte, putem găsi un cod cu o probabilitate de eroare neglijabilă care se apropie de această limită în mod arbitrar.
leumnu→∞L(Xnu,δ)nu=H(X){\ displaystyle lim_ {n \ rightarrow \ infty} {\ frac {L (X ^ {n}, \ delta)} {n}} = H (X)}nu{\ displaystyle n}Xnu{\ displaystyle X ^ {n}}nu H(X){\ displaystyle n \ H (X)}
Teorema codării sursei pentru codurile simbolului
Considerăm o succesiune de simboluri provenind dintr-o sursă staționară -ary (secvența variabilelor iid ), teorema este simplificată în: cu lungimea unui cod optim pentru .
nu{\ displaystyle n}la{\ displaystyle a}H(X)log2(la)≤E[l(X)]<H(X)log2(la)+1{\ displaystyle {\ frac {H (X)} {log_ {2} (a)}} \ leq \ mathbb {E} [l (X)] <{\ frac {H (X)} {log_ {2} (a)}} + 1}l(X){\ displaystyle l (X)}X{\ displaystyle X}
Dovezi
Dovada teoremei de codare a sursei
Fie deci o variabilă aleatorie, să denotăm succesiunea diferitelor realizări ale ( urmați aceeași lege ca și sunt independenți). Teorema afirmă că , să încadrăm această limită prin două inegalități.
X{\ displaystyle X}Xnu=X1X2...Xnu{\ displaystyle X ^ {n} = X_ {1} X_ {2} ... X_ {n}}nu{\ displaystyle n}X{\ displaystyle X}(Xeu)eu≤nu{\ displaystyle (X_ {i}) _ {i \ leq n}}X{\ displaystyle X}leumnu→∞L(Xnu,δ)nu=H(X){\ displaystyle lim_ {n \ rightarrow \ infty} {\ frac {L (X ^ {n}, \ delta)} {n}} = H (X)}
Dovezi de accesibilitate
Pentru și definește un set de realizări tipice precum: .
nu∈NU{\ displaystyle n \ in \ mathbb {N}}ϵ>0{\ displaystyle \ epsilon> 0}Xnu{\ displaystyle X ^ {n}}Sδ={Xnu∈LAnu/ P(Xnu=Xnu)≥2-nu(H(X)+ϵ)}{\ displaystyle S _ {\ delta} = \ {x ^ {n} \ în A ^ {n} / \ \ mathbb {P} (X ^ {n} = x ^ {n}) \ geq 2 ^ {- n (H (X) + \ epsilon)} \}}
Avem apoi, cu și entropie:
hX(X)=-Buturuga(p(X=X)){\ displaystyle h_ {X} (x) = - \ log (p (X = x))}H{\ displaystyle H}
P(X1...Xnu∈Sδ)=PX{P(Xnu=Xnu)≥2-nu(H(X)+ϵ)}=PX{-ButurugaP(Xnu=Xnu)≤nu(H(X)+ϵ)}=PX{-Buturuga(P(X1=X1)...P(Xnu=Xnu))≤nu(H(X)+ϵ)}=PX{∑eu=1nuhX(Xeu)≤nu(H(X)+ϵ)}=PX{1nu∑eu=1nuhX(X)≤H(X)+ϵ}{\ displaystyle {\ begin {align} \ mathbb {P} (X_ {1} ... X_ {n} \ în S _ {\ delta}) & = \ mathbb {P} _ {X} {\ {\ mathbb {P} (X ^ {n} = x ^ {n}) \ geq 2 ^ {- n (H (X) + \ epsilon)} \}} \\ & = \ mathbb {P} _ {X} \ {- \ log {\ mathbb {P} (X ^ {n} = x ^ {n})} \ leq n (H (X) + \ epsilon) \} \\ & = \ mathbb {P} _ { X} \ {- \ log (\ mathbb {P} (X_ {1} = x_ {1}) ... \ mathbb {P} (X_ {n} = x_ {n})) \ leq n (H ( X) + \ epsilon) \} \\ & = \ mathbb {P} _ {X} \ {\ sum _ {i = 1} ^ {n} h_ {X} (X_ {i}) \ leq n (H (X) + \ epsilon) \} \\ & = \ mathbb {P} _ {X} \ {{\ frac {1} {n}} \ sum _ {i = 1} ^ {n} h_ {X} (X) \ leq H (X) + \ epsilon \} \\\ end {align}}}
Deoarece , legea slabă a numărului mare ne asigură .
H(X)=E(hX(X)){\ displaystyle H (X) = E (h_ {X} (X))}limnu→∞P{X1...Xnu∈Sδ}=1{\ displaystyle \ lim _ {n \ rightarrow \ infty} \ mathbb {P} \ {X_ {1} ... X_ {n} \ în S _ {\ delta} \} = 1}
Pentru suficient de mare și din moment ce putem codifica acest set cu mai puțini biți.
nu{\ displaystyle n}P{X1...Xnu∈Sδ}≥1-δ{\ displaystyle \ mathbb {P} \ {X_ {1} ... X_ {n} \ în S _ {\ delta} \} \ geq 1- \ delta}|Sδ|≤2nu(H(X)+ϵ){\ displaystyle | S _ {\ delta} | \ leq 2 ^ {n (H (X) + \ epsilon)}}nu(H(X)+ϵ){\ displaystyle n (H (X) + \ epsilon)}
Deci, pentru orice și corespunzător destul de mare, prin urmare .
L(Xnu,δ)nu≤H(X)+ϵ{\ displaystyle {\ frac {L (X ^ {n}, \ delta)} {n}} \ leq H (X) + \ epsilon}ϵ{\ displaystyle \ epsilon}nu{\ displaystyle n}leumnu→∞L(Xnu,δ)nu≤H(X){\ displaystyle lim_ {n \ rightarrow \ infty} {\ frac {L (X ^ {n}, \ delta)} {n}} \ leq H (X)}
Dovadă inversă
Căci , să fie așa că , să ne pozăm și astfel încât în acest fel:
ϵ>0{\ displaystyle \ epsilon> 0}S⊆LAnu{\ displaystyle S \ subseteq A ^ {n}}|S|≤2nu(H(X)-ϵ){\ displaystyle | S | \ leq 2 ^ {n (H (X) - \ epsilon)}}Ss{\ displaystyle S_ {s}}Sb{\ displaystyle S_ {b}}S=Ss∪Sb{\ displaystyle S = S_ {s} \ cup S_ {b}}
Ss=S∩{Xnu| P(X=Xnu)≤2-nu(H(X)-ϵ/2)}Sb=S∩{Xnu| P(X=Xnu)>2-nu(H(X)-ϵ/2)}{\ displaystyle {\ begin {align} & S_ {s} = S \ cap \ {x ^ {n} | \ \ mathbb {P} (X = x ^ {n}) \ leq 2 ^ {- n (H (X) - \ epsilon / 2)} \} \\ & S_ {b} = S \ cap \ {x ^ {n} | \ \ mathbb {P} (X = x ^ {n})> 2 ^ { - n (H (X) - \ epsilon / 2)} \} \ end {align}}}
Acum,
P(X1...Xnu∈S)=P(X1...Xnu∈Ss)+P(X1...Xnu∈Sb)≤|S|2-nu(H(X)-ϵ/2)+P{P(Xnu=X1...Xnu)>2-nu(H(X)-ϵ/2)}≤2-nuϵ/2+P{∑eu=1nuhX(Xeu)<nu(H(X)-ϵ/2)}≤2-nuϵ/2+P{1nu∑eu=1nuhX(X)<(H(X)-ϵ/2)}{\ displaystyle {\ begin {align} \ mathbb {P} (X_ {1} ... X_ {n} \ în S) & = \ mathbb {P} (X_ {1} ... X_ {n} \ în S_ {s}) + \ mathbb {P} (X_ {1} ... X_ {n} \ în S_ {b}) \\ & \ leq | S | 2 ^ {- n (H (X) - \ epsilon / 2)} + \ mathbb {P} \ {\ mathbb {P} (X ^ {n} = X_ {1} ... X_ {n})> 2 ^ {- n (H (X) - \ epsilon / 2)} \} \\ & \ leq 2 ^ {- n \ epsilon / 2} + \ mathbb {P} \ {\ sum _ {i = 1} ^ {n} h_ {X} (X_ { i}) <n (H (X) - \ epsilon / 2) \} \\ & \ leq 2 ^ {- n \ epsilon / 2} + \ mathbb {P} \ {{\ frac {1} {n} } \ sum _ {i = 1} ^ {n} h_ {X} (X) <(H (X) - \ epsilon / 2) \} \ end {align}}}
Primul termen care tinde spre 0 și, prin legea slabă a numerelor mari, și al doilea, avem, prin urmare, probabilitatea de a putea codifica cu caractere sau mai puțin tinde spre 0. Astfel, de la un suficient de mare, acesta va merge sub și de aceea pentru tot ce vom avea .
limnu→∞P(X1...Xnu∈S)=0{\ displaystyle \ lim _ {n \ rightarrow \ infty} \ mathbb {P} (X_ {1} ... X_ {n} \ în S) = 0}Xnu{\ displaystyle X ^ {n}}nu(H(X)-ϵ){\ displaystyle n (H (X) - \ epsilon)}nuδ{\ displaystyle n _ {\ delta}}δ{\ displaystyle \ delta}nu>nuδ{\ displaystyle n> n _ {\ delta}}L(Xnu,δ)nu≥H(X)-ϵ{\ displaystyle {\ frac {L (X ^ {n}, \ delta)} {n}} \ geq H (X) - \ epsilon}
Așa cum acest lucru este valabil pentru tot : , care completează încadrarea limitei dorite.
ϵ{\ displaystyle \ epsilon}leumnu→∞L(Xnu,δ)nu≥H(X){\ displaystyle lim_ {n \ rightarrow \ infty} {\ frac {L (X ^ {n}, \ delta)} {n}} \ geq H (X)}
Dovadă pentru coduri prin simboluri
Fie o variabilă aleatorie și un cod optim pentru (adică așteptarea lungimii minime).
X{\ displaystyle X}l{\ displaystyle l}X{\ displaystyle X}
Pentru orice , cu lungimea codului de , definim cu dimensiunea alfabetului pe care X ia valori și o constantă de normalizare, cum ar fi . Deci, în primul rând
eu≤nu{\ displaystyle i \ leq n}l(Xeu){\ displaystyle l (x_ {i})}Xeu{\ displaystyle x_ {i}}qeu=la-l(Xeu)VS{\ displaystyle q_ {i} = {\ frac {a ^ {- l (x_ {i})}} {C}}}la{\ displaystyle a}VS{\ displaystyle C}∑qeu=1{\ displaystyle \ sum q_ {i} = 1}
H(X)=-∑eu=1nupeuButuruga2peu≤-∑eu=1nupeuButuruga2qeu{\ displaystyle {\ begin {align} H (X) & = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} \\ & \ leq - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} q_ {i} \\\ end {align}}}
din Inegalitatea lui Gibbs .
H(X)≤-∑eu=1nupeuButuruga2la-l(Xeu)+∑eu=1nupeuButuruga2VS=-∑eu=1nupeuButuruga2la-l(Xeu)+Buturuga2VS≤-∑eu=1nu-l(Xeu)peuButuruga2la≤E[l(X)]Buturuga2la{\ displaystyle {\ begin {align} H (X) & \ leq - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} a ^ {- l (x_ {i}) } + \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} C \\ & = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ { 2} a ^ {- l (x_ {i})} + \ log _ {2} C \\ & \ leq - \ sum _ {i = 1} ^ {n} -l (x_ {i}) p_ { i} \ log _ {2} a \\ & \ leq \ mathbb {E} [l (X)] \ log _ {2} a \\\ end {align}}}
conform Inegalității Kraft . Prin urmare, avem limita inferioară.
Cum ar fi , avemVS=∑la-l(Xeu)≤1{\ displaystyle C = \ sum a ^ {- l (x_ {i})} \ leq 1}ButurugaVS≤0.{\ displaystyle \ log {C} \ leq 0.}
Putem încerca să reparăm pentru a avea .
l(Xeu)=⌈-Buturugalapeu⌉{\ displaystyle l (x_ {i}) = \ lceil - \ log _ {a} p_ {i} \ rceil}-Buturugalapeu≤l(Xeu)<-Buturugalapeu+1{\ displaystyle - \ log _ {a} p_ {i} \ leq l (x_ {i}) <- \ log _ {a} p_ {i} +1}
Apoi, prin urmare, și inegalitatea Kraft ne oferă existența unui cod de prefix pentru aceste lungimi de cuvinte acolo.
la-l(Xeu)≤peu{\ displaystyle a ^ {- l (x_ {i})} \ leq p_ {i}}∑la-l(Xeu)≤1{\ displaystyle \ sum a ^ {- l (x_ {i})} \ leq 1}X{\ displaystyle X}
In cele din urma,
E[l(X)]=∑peul(Xeu)<∑peu(-Buturugala(peu)+1)=∑-peulog2(peu)log2(la)+1=H(X)log2(la)+1{\ displaystyle {\ begin {align} E [l (X)] & = \ sum p_ {i} l (x_ {i}) \\ & <\ sum p_ {i} (- \ log _ {a} ( p_ {i}) + 1) \\ & = \ sum -p_ {i} {\ frac {log_ {2} (p_ {i})} {log_ {2} (a)}} + 1 \\ & = {\ frac {H (X)} {log_ {2} (a)}} + 1 \ end {align}}}
Ceea ce ne dă limita superioară și completează dovada.
Vezi și tu
Bibliografie
- CE Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , vol. 27, pp. 379-423, iulie 1948.
- O. Fawzi, curs de teoria informației , ENS de Lyon, toamna 2018.
- D. MacKay, Teoria informației, inferență și algoritmi de învățare , Cambridge University Press, 2005, ( ISBN 0-521-64298-1 ) .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">