Shannons krypteringskällsats

Inom informationsteorin sätter Shannons krypteringskällsats (eller tyst krypteringssats) en gräns för maximal datakomprimering och ett numeriskt värde för Shannons entropi .

Satsen visar att (när mängden data tenderar till oändlighet i en ström av oberoende och jämnt fördelade (IED) slumpvariabler) är det omöjligt att komprimera data så att koduppskattningen (genomsnittligt antal bitar per symbol) är mindre än Shannon-entropin av originaldata, utan förlust av informationsnoggrannhet. Det är dock möjligt att få en kod nära Shannon-entropin utan betydande förlust.

Krypteringskällsatsen för teckenkoder bringar övre och nedre gränser till minsta möjliga längd av krypterade ord som en funktion av entropin för inmatningsordet (som representeras som en slumpmässig variabel) och storleken på det önskade alfabetet.

Uttalande

Källkoden är en mappning (sekvens) från informationslagret till en sekvens av alfabetiska tecken (vanligtvis bitar) så att källtecknet kan erhållas unikt från binära siffror (förlustfri kodningskälla) eller erhållas med någon skillnad (förlustkodningskälla) . Detta är tanken bakom datakomprimering.

Krypteringskälla för teckenkoder

Inom datavetenskap säger krypteringskällsatsen (Shannon 1948) att:

En N slumpvariabel med entropi H ( X ) kan komprimeras till mer än N  H ( X ) bitar med försumbar risk för dataförlust om N går till oändlighet, men om komprimeringen är mindre än N  H ( X ) bitar, då data som mest sannolikt går förlorade. (MacKay 2003)."

Krypteringskällsats för teckenkoder

Låt , beteckna två finita alfabet, och låt och beteckna mängden av alla finita ord från dessa alfabet (ordnade). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Antag att X är en slumpmässig variabel som tar ett värde från , och f är en dechiffrerbar kod från till , där . Låt S representera en slumpvariabel som ges av ordlängden f ( X ). $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Om f är optimal i den meningen att den har den minsta ordlängden för X , då

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

(Shannon 1948).

Bevis på krypteringskällans sats

Givet att det är ett NOR, är dess tidsserie X 1 , …, Xn också ett NOR med entropi H ( X ) i fallet med diskreta värden och med differentiell entropi i fallet med kontinuerliga värden. Krypteringskällsatsen säger att det för varje uppskattning som är större än resursens entropi finns ett tillräckligt stort n och en kryptering som tar n NOP-kopior av resursen , , , och mappar den till binära bitar på ett sådant sätt att det ursprungliga tecknet kan återställas från binära bitar, X med en sannolikhet på minst . $X$ $\epsilon >0$ $X^{1:n}$ $n.(H(X)+\epsilon )$ $X^{1:n}$ $1-\epsilon$

Bevis

Låt oss ta några . formeln för, , ser ut så här: $\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 visar att för tillräckligt stort n är sekvensen som genereras från källan opålitlig i det typiska fallet - , konvergent. I fallet för tillräckligt stor: n , (se AEP) $A_{n}^{\epsilon }$ $P(A_{n}^{\epsilon })>1-\epsilon$

Definitionen av typiska uppsättningar innebär att de sekvenser som ligger i en typisk uppsättning uppfyller:

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

Anteckna det:

Sannolikheten att sekvensen erhölls från $X$

${\displaystyle {A_{\epsilon }}^{(n)))$ mer än $1-\epsilon$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )))$ eftersom den totala befolkningssannolikheten är störst. ${\displaystyle {A_{\epsilon }}^{(n)))$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )))$ . Som bevis använder du en övre sannolikhetsgräns för varje term i typfallet och en nedre gräns för det allmänna fallet . ${\displaystyle {A_{\epsilon }}^{(n)))$

Att börja med bitar är tillräckligt för att särskilja vilken sträng som helst $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Krypteringsalgoritm: kodaren kontrollerar om den inkommande sekvensen är falsk, om ja, returnerar sedan indexet för den inkommande frekvensen i sekvensen, om inte, returnerar sedan ett slumpmässigt nummer. numeriskt värde. Om ingångssannolikheten är felaktig i sekvensen (med en frekvens på ca ), så genererar kodaren inget fel. Det vill säga sannolikheten för fel är högre än $n.(H(X)+\epsilon )$ $1-\epsilon$ $\epsilon$

Bevis på reversibilitet Beviset för reversibilitet är baserat på det faktum att det krävs att visa att för varje sekvens av storlek som är mindre än (i betydelsen av exponenten) kommer att täcka frekvensen av sekvensen avgränsad av 1. $A_{n}^{\epsilon }$

Bevis på krypteringskällans sats för teckenkoder

Låt ordet längd för varje möjlig ( ). Låt oss definiera , där C väljs på ett sådant sätt att: . $si}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Sedan

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

där den andra linjen är Gibbs ojämlikhet och den femte linjen är Kraft ojämlikheten , . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

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

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

så

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

och då

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

och

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

Sålunda uppfyller minimum 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}}

Anteckningar

Omslag, Thomas M. Kapitel 5: Datakomprimering // Elements of Information Theory (neopr.) . - John Wiley & Sons , 2006. - ISBN 0-471-24195-4 .
C.E. Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , vol. 27, sid. 379-423, 623-656, juli, oktober 1948