Shannons krypteringskildesætning

I informationsteorien sætter Shannons krypteringskildesætning (eller tavs krypteringssætning) en grænse for den maksimale datakomprimering og en numerisk værdi for Shannons entropi .

Sætningen viser, at (når mængden af data har en tendens til uendelig i en strøm af uafhængige og ligeligt fordelte (IED) stokastiske variabler) er det umuligt at komprimere dataene, så kodeestimatet (gennemsnitligt antal bits pr. symbol) er mindre end Shannon-entropien af de originale data uden tab af informationsnøjagtighed. Det er dog muligt at opnå en kode tæt på Shannon-entropien uden væsentlige tab.

Krypteringskildesætningen for tegnkoder bringer øvre og nedre grænser til den mindst mulige længde af krypterede ord som funktion af inputordets entropi (som er repræsenteret som en tilfældig variabel) og størrelsen af det nødvendige alfabet.

Erklæring

Kildekoden er en mapping (sekvens) fra informationslageret til en sekvens af alfabetiske tegn (normalt bits), således at kildetegnet kan opnås entydigt fra binære cifre (tabsfri kodningskilde) eller opnås med en vis forskel (tabsgivende kodningskilde) . Dette er ideen bag datakomprimering.

Krypteringskilde til tegnkoder

Inden for datalogi siger krypteringskildesætningen (Shannon 1948) at:

En N tilfældig variabel med entropi H ( X ) kan komprimeres til mere end N  H ( X ) bits med ubetydelig risiko for datatab, hvis N går til det uendelige, men hvis komprimeringen er mindre end N  H ( X ) bit, så data, der højst sandsynligt går tabt. (MacKay 2003)."

Krypteringskildesætning for tegnkoder

Lad , betegne to endelige alfabeter, og lad og betegne mængden af alle endelige ord fra disse alfabeter (ordnet). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Antag, at X er en tilfældig variabel, der tager en værdi fra , og f er en dechifrerbar kode fra til , hvor . Lad S repræsentere en stokastisk variabel givet af ordlængden f ( X ). $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Hvis f er optimal i den forstand, at den har den mindste ordlængde for X , så

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

(Shannon 1948).

Bevis for krypteringskildesætningen

Da det er en NOR, er dens tidsserie X 1 , …, Xn også en NOR med entropi H ( X ) i tilfælde af diskrete værdier og med differentiel entropi i tilfælde af kontinuerte værdier. Krypteringskildesætningen siger, at for hvert estimat, der er større end ressourcens entropi, er der et tilstrækkeligt stort n og en kryptering, der tager n NOP-kopier af ressourcen , , , og kortlægger den til binære bits på en sådan måde at det oprindelige tegn kan gendannes fra binære bit, X med en sandsynlighed på mindst . $x$ $\epsilon >0$ $X^{1:n}$ $n.(H(X)+\epsilon )$ $X^{1:n}$ $1-\epsilon$

Bevis

Lad os tage nogle . formlen for, , ser sådan ud: $\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 viser, at for tilstrækkeligt store n er sekvensen genereret fra kilden upålidelig i det typiske tilfælde - , konvergent. I tilfældet for stor nok: n , (se AEP) $A_{n}^{\epsilon }$ $P(A_{n}^{\epsilon })>1-\epsilon$

Definitionen af typiske sæt indebærer, at de sekvenser, der ligger i et typisk sæt, opfylder:

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

Læg mærke til det:

Sandsynligheden for, at sekvensen blev opnået fra $x$

${\displaystyle {A_{\epsilon }}^{(n)))$ mere end $1-\epsilon$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )))$ da den samlede befolkningssandsynlighed er størst. ${\displaystyle {A_{\epsilon }}^{(n)))$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )))$ . Som bevis skal du bruge en øvre sandsynlighedsgrænse for hvert led i det typiske tilfælde og en nedre grænse for det generelle tilfælde . ${\displaystyle {A_{\epsilon }}^{(n)))$

At starte med bits er nok til at skelne enhver streng $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Krypteringsalgoritme: indkoderen kontrollerer, om den indkommende sekvens er falsk, hvis ja, returnerer den derefter indekset for den indgående frekvens i sekvensen, hvis ikke, returnerer den et tilfældigt ciffer. numerisk værdi. Hvis inputsandsynligheden er forkert i sekvensen (med en frekvens på ca ), genererer indkoderen ikke en fejl. Det vil sige, at sandsynligheden for fejl er højere end $n.(H(X)+\epsilon )$ $1-\epsilon$ $\epsilon$

Bevis for reversibilitet Beviset for reversibilitet er baseret på det faktum, at det er nødvendigt at vise, at for enhver sekvens af størrelse mindre end (i betydningen af eksponenten) vil dække frekvensen af sekvensen afgrænset af 1. $A_{n}^{\epsilon }$

Bevis for krypteringskildesætningen for tegnkoder

Lad ordet længde for hver mulig ( ). Lad os definere , hvor C er valgt på en sådan måde, at: . $s_{i}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Derefter

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

hvor den anden linje er Gibbs-uligheden og den femte linje er Kraft - uligheden . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

for den anden ulighed, vi kan sætte

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

så

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

og så

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

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

Således opfylder minimum S

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

Noter

Cover, 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, s. 379-423, 623-656, juli, oktober, 1948