Shannon titkosítási forrástétele

Az információelméletben Shannon titkosítási forrástétele (vagy csendes titkosítási tétel) határt szab a maximális adattömörítésnek és számértéket a Shannon- entrópiának .

A tétel azt mutatja, hogy (amikor az adatok mennyisége a végtelenbe hajlik a független és egyenlő eloszlású (IED) valószínűségi változók folyamában) lehetetlen az adatokat úgy tömöríteni, hogy a kódbecslés (átlagos bitek száma szimbólumonként) kisebb legyen, mint az eredeti adatok Shannon-entrópiája, az információpontosság elvesztése nélkül. A Shannon-entrópiához közeli kódot azonban jelentős veszteség nélkül lehet kapni.

A karakterkódok titkosítási forrástétele a bemeneti szó entrópiájának (amelyet véletlenszerű változóként ábrázol) és a szükséges ábécé méretének függvényében felső és alsó határokat hoz a titkosított szavak lehetséges minimális hosszához.

Nyilatkozat

A forráskód egy leképezés (sorozat) az információtárolóból alfabetikus karakterek sorozatába (általában bitekbe), így a forráskarakter egyedileg kinyerhető bináris számjegyekből (veszteségmentes kódolási forrás), vagy valamilyen eltéréssel (veszteséges kódolási forrás) . Ez az ötlet az adattömörítés mögött.

Karakterkódok titkosítási forrása

A számítástechnikában a titkosítási forrástétel (Shannon 1948) kimondja, hogy:

Egy N valószínűségi változó H ( X ) entrópiájú N H ( X  ) bitnél többre tömöríthető, az adatvesztés kockázata elhanyagolható, ha N a végtelenbe megy, de ha a tömörítés kisebb, mint N  H ( X ) bit, akkor a az adatok nagy valószínűséggel elvesznek. (MacKay 2003)."

A karakterkódok titkosítási forrástétele

Legyen , jelölje két véges ábécét, és jelölje az összes véges szó halmazát ezekből az ábécékből (rendezett). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Tegyük fel, hogy X egy valószínűségi változó, amely értéket vesz fel -tól , és f egy megfejthető kód -tól -ig , ahol . Legyen S egy valószínűségi változó, amelyet az f ( X ) szóhossz adja . $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Ha f optimális abban az értelemben, hogy megvan a minimális szóhossza X -hez , akkor

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

(Shannon 1948).

A titkosítási forrástétel bizonyítása

Mivel NOR-ról van szó, az X 1 , …, X n idősora diszkrét értékek esetén H ( X ), folytonos értékek esetén pedig differenciális entrópiájú NOR . A titkosítási forrástétel kimondja, hogy mindegyikhez, minden egyes, az erőforrás entrópiájánál nagyobb becsléshez van egy kellően nagy n és egy titkosító, amely n NOP másolatot készít a , , erőforrásból, és bináris bitekre képezi le oly módon. hogy az eredeti karakter bináris bitekből, X legalább . valószínűséggel visszaállítható . $x$ $\epsilon >0$ $X^{1:n}$ $n.(H(X)+\epsilon )$ $X^{1:n}$ $1-\epsilon$

Bizonyíték

Vegyünk néhányat . a, , képlete így néz ki: $\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)\jobbra|<\epszilon \jobbra\}$

Az AEP azt mutatja, hogy kellően nagy n esetén a forrásból generált sorozat tipikus - , konvergens esetben megbízhatatlan. Elég nagy esetén: n , (lásd AEP) $A_{n}^{\epsilon }$ $P(A_{n}^{\epsilon })>1-\epsilon$

A tipikus halmazok meghatározása azt jelenti, hogy azok a sorozatok, amelyek egy tipikus halmazban vannak, megfelelnek:

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

Vegye figyelembe, hogy:

Annak a valószínűsége, hogy a sorozatot a következőből kaptuk $x$

${\displaystyle {A_{\epsilon }}^{(n)))$ több mint $1-\epsilon$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )))$ hiszen a teljes populáció valószínűsége a legnagyobb. ${\displaystyle {A_{\epsilon }}^{(n)))$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )))$ . Bizonyításhoz használjon felső valószínűségi korlátot minden tagra tipikus esetben, alsó korlátot pedig általános esetre . ${\displaystyle {A_{\epsilon }}^{(n)))$

Bármely karakterlánc megkülönböztetéséhez elegendő a bitekkel kezdeni $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Titkosító algoritmus: a kódoló ellenőrzi, hogy a bejövő szekvencia hamis-e, ha igen, akkor visszaadja a sorozat bejövő frekvenciájának indexét, ha nem, akkor véletlenszerű számjegyet ad vissza. numerikus érték. Ha a bemeneti valószínűség hibás a sorozatban (kb. gyakorisággal ), akkor a kódoló nem generál hibát. Vagyis a hiba valószínűsége nagyobb, mint $n.(H(X)+\epsilon )$ $1-\epsilon$ $\epsilon$

A reverzibilitás bizonyítása A reverzibilitás bizonyítása azon a tényen alapszik, hogy be kell mutatni, hogy minden (a kitevő értelmében) kisebb méretű sorozat esetén lefedi az 1-gyel határolt sorozat gyakoriságát. $A_{n}^{\epsilon }$

A karakterkódok titkosítási forrástételének bizonyítása

Legyen a szó hossza minden lehetségesnél ( ). Határozzuk meg , ahol C úgy van kiválasztva, hogy: . $s_{i}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Akkor

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

ahol a második sor a Gibbs-egyenlőtlenség , az ötödik pedig a Kraft-egyenlőtlenség , . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

a második egyenlőtlenséghez, amelyet beállíthatunk

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

így

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

és akkor

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

és

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

Így a minimum S teljesül

{\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{igazított}}

Jegyzetek

Cover, Thomas M. 5. fejezet: Adattömörítés // Az információelmélet elemei (neopr.) . - John Wiley & Sons , 2006. - ISBN 0-471-24195-4 .
C. E. Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , vol. 27, pp. 379-423, 623-656, 1948. július, október