Shannons källkodssats

I informationsteorin fastställer Shannons källkodningssats (eller noiseless coding theorem ) gränserna för möjlig datakomprimering och den operativa betydelsen av Shannon-entropin .

Uppkallad efter Claude Shannon visar källkodningssatsen att (i gränsen, eftersom längden av en ström av oberoende och identiskt fördelade slumpvariabel (iid) data tenderar till oändligheten ) är det omöjligt att komprimera data så att kodhastigheten (genomsnittligt antal bitar per symbol) är mindre än Shannon-entropin för källan, utan att det är praktiskt taget säkert att information kommer att gå förlorad. Det är dock möjligt att få kodhastigheten godtyckligt nära Shannon-entropin, med försumbar sannolikhet för förlust.

Källkodssatsen för symbolkoder sätter en övre och en nedre gräns för den minsta möjliga förväntade längden av kodord som en funktion av entropin för inmatningsordet (som ses som en slumpmässig variabel ) och av storleken på målalfabetet.

Uttalanden

Källkodning är en mappning från (en sekvens av) symboler från en informationskälla till en sekvens av alfabetssymboler (vanligtvis bitar) så att källsymbolerna exakt kan återställas från de binära bitarna (förlustfri källkodning) eller återställas inom någon förvrängning ( förlustig källkodning). Detta är konceptet bakom datakomprimering .

Källkodssats

I informationsteorin säger källkodningssatsen (Shannon 1948) informellt att (MacKay 2003, sid. 81, Cover 2006, kapitel 5):

$N$ i.id slumpvariabler var och en med entropi $H (X)$ kan komprimeras till mer än $N H (X)$ bitar med försumbar risk för informationsförlust, som $N \to \infty$ ; men omvänt, om de komprimeras till färre än $N H (X)$ bitar är det praktiskt taget säkert att information kommer att gå förlorad.

Den $NH(X)$ kodade sekvensen representerar det komprimerade meddelandet på ett tvåsidigt sätt, under antagandet att avkodaren känner till källan. Ur praktisk synvinkel är denna hypotes inte alltid sann. Följaktligen, när entropikodningen tillämpas är det överförda meddelandet $NH(X)+(inf.source)$ . Vanligtvis infogas informationen som kännetecknar källan i början av det överförda meddelandet.

Källkodssats för symbolkoder

Låt $Σ 1, Σ 2$ beteckna två finita alfabet och låt $Σ * 1$ och $Σ * 2$ beteckna mängden av alla finita ord från dessa alfabet (respektive).

Antag att $X$ är en slumpvariabel som tar värden i $Σ 1$ och låt $f$ vara en unikt avkodningsbar kod från $Σ * 1$ till $Σ * 2$ där $|Σ 2 | = a$ . Låt $S$ beteckna den slumpmässiga variabeln som ges av längden på kodordet $f (X)$ .

Om $f$ är optimal i den meningen att det har den minimala förväntade ordlängden för $X$ , då (Shannon 1948):

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

Där $\mathbb {E}$ anger operatorn förväntat värde .

Bevis: Källkodssats

Givet $X$ är en iid- källa, dess tidsserie $X 1, ..., X n$ är iid med entropin $H (X)$ i det diskreta fallet och differentiell entropi i det kontinuerligt värderade fallet. Källkodningssatsen säger att för vilken som helst $ε > 0$ , dvs för vilken takt $H (X) + ε$ som helst som är större än källans entropi , finns det tillräckligt stort $n$ och en kodare som tar $n$ iid upprepning av källan, $X 1: n$ och mappar det till $n (H (X) + ε)$ binära bitar så att källsymbolerna $X 1: n$ är återvinningsbara från de binära bitarna med en sannolikhet på minst $1 - ε$ .

Bevis på uppnåbarhet. Fixa några $ε > 0$ , och låt

p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].

Den typiska mängden $εn,,$ A definieras enligt följande:

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

Den asymptotiska ekvipartitionsegenskapen (AEP) visar att för tillräckligt stor $n$ närmar sig sannolikheten att en sekvens som genereras av källan ligger i den typiska mängden, $A ε n$ , enligt definition ett. I synnerhet för tillräckligt stor $n$ , $,X_{2},\cdots ,X_{n} )\in A_{n}^{\varepsilon })}$ kan göras godtyckligt nära 1, och specifikt större än $1-\varepsilon$ (Se AEP för ett bevis).

Definitionen av typiska uppsättningar innebär att de sekvenser som ligger i den typiska uppsättningen uppfyller:

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

Anteckna det:

Sannolikheten för att en sekvens $(X_{1},X_{2},\cdots X_{n})$ dras från $A ε n$ är större än $1 - ε$ .
${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}} , vilket följer$ av den vänstra sidan (nedre gränsen) för $p(x_{1},x_{2},\cdots x_{n})$ .
$\left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X) )-\varepsilon )}$ , som följer av övre gränsen för $p(x_{1},x_{2},\cdots x_{n})$ och den nedre gränsen för den totala sannolikheten för hela mängden $A ε n$ .

Sedan $\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X) +\varepsilon )},n(H(X)+\varepsilon )$ bitar är tillräckligt för att peka på vilken sträng som helst i denna uppsättning.

Kodningsalgoritmen: Kodaren kontrollerar om inmatningssekvensen ligger inom den typiska uppsättningen; om ja, matar den ut indexet för inmatningssekvensen inom den typiska uppsättningen; om inte, matar kodaren ut ett godtyckligt $n (H (X) + e)$ siffror. Så länge som ingångssekvensen ligger inom den typiska mängden (med sannolikhet minst $1 - ε$ ), gör kodaren inget fel. Så sannolikheten för fel hos kodaren begränsas ovan av $ε$ .

Bevis på Converse. Det omvända bevisas genom att visa att varje uppsättning av storlek som är mindre än $A ε n$ (i betydelsen exponent) skulle täcka en uppsättning sannolikheter avgränsad från $1$ .

Bevis: Källkodssats för symbolkoder

För $1 \leq i \leq n$ låt $s i$ beteckna ordlängden för varje möjlig $x i$ . Definiera $q_{i}=a^{-s_{i}}/C$ , där $C$ väljs så att $q 1 + ... + q n = 1$ . Sedan

{\begin{aligned}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}}+\summa _{i=1}^{n}p_{i}\log _{2}C\\&=-\summa _{i=1 }^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n} -s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}

där den andra raden följer av Gibbs ojämlikhet och den femte raden följer av Krafts ojämlikhet :

C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1

så $log C \leq 0$ .

För den andra ojämlikheten kan vi sätta

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

så att

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

och så

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

och

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

och så genom Krafts ojämlikhet finns det en prefixfri kod som har dessa ordlängder. Därmed uppfyller det minimala $S$

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

Utvidgning till icke-stationära oberoende källor

Fixed Rate förlustfri källkodning för diskret tid icke-stationära oberoende källor

Definiera typisk mängd $A εn som$ :

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

Sedan, för given $δ > 0$ , för $n$ tillräckligt stor, $Pr(A ε n) > 1 - δ$ . Nu kodar vi bara sekvenserna i den typiska uppsättningen, och vanliga metoder i källkodning visar att kardinaliteten för denna uppsättning är mindre än $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$ . I genomsnitt räcker alltså $H n (X) + ε$ -bitar för kodning med sannolikhet större än $1 - δ$ , där $ε$ och $δ$ kan göras godtyckligt små, genom att göra $n$ större.

Se även