Shannonin salauslähdelause

Tietoteoriassa Shannonin salauslähdelause (tai hiljainen salauslause) asettaa rajan datan enimmäispakkaukselle ja numeerisen arvon Shannonin entropialle .

Lause osoittaa, että (kun datan määrä pyrkii äärettömään itsenäisesti ja tasaisesti jakautuneiden (IED) satunnaismuuttujien virrassa) on mahdotonta pakata dataa niin, että koodiestimaatti (keskimääräinen bittien määrä symbolia kohti) on pienempi kuin alkuperäisen tiedon Shannonin entropia ilman tietojen tarkkuuden menetystä. Shannonin entropiaa lähellä oleva koodi on kuitenkin mahdollista saada ilman merkittäviä häviöitä.

Merkkikoodien salauslähdelause tuo ylä- ja alarajat salattujen sanojen minimipituuteen syötesanan entropian (joka esitetään satunnaismuuttujana) ja vaaditun aakkoston koon funktiona.

Lausunto

Lähdekoodi on kartoitus (sekvenssi) tietovarastosta aakkosmerkkien (yleensä bittien) sekvenssiin siten, että lähdemerkki voidaan saada yksiselitteisesti binäärinumeroista (häviötön koodauslähde) tai jollain erolla (häviöinen koodauslähde) . Tämä on tietojen pakkaamisen idea.

Merkkikoodien salauslähde

Tietojenkäsittelytieteessä salauslähdelause (Shannon 1948) sanoo, että:

N satunnaismuuttuja, jolla on entropia H ( X ) , voidaan pakata useammaksi kuin N  H ( X ) bitiksi ilman mitätöntä datan menetyksen riskiä, jos N menee äärettömään, mutta jos pakkaus on pienempi kuin N  H ( X ) bittiä, tiedot todennäköisesti menetetään. (MacKay 2003).

Merkkikoodien salauslähdelause

Olkoon , tarkoittaa kahta äärellistä aakkostoa ja anna ja merkitse kaikkien näiden aakkosten äärellisten sanojen joukkoa (järjestyksessä). $\Sigma_1$ $\Sigma _{2}$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$

Oletetaan, että X on satunnaismuuttuja, joka saa arvon kohdasta , ja f on purettavissa oleva koodi kohdasta , jossa . Olkoon S sanan pituuden f ( X ) antama satunnaismuuttuja . $\Sigma_1$ $\Sigma _{1}^{*}$ $\Sigma _{2}^{*}$ $|\Sigma _{2}|=a$

Jos f on optimaalinen siinä mielessä, että sillä on minimisanan pituus X :lle , niin

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

(Shannon 1948).

Todistus salauslähdelauseesta

Koska se on NOR, sen aikasarja X 1 , …, X n on myös NOR, jonka entropia on H ( X ) diskreettien arvojen tapauksessa ja differentiaalisen entropian kanssa jatkuvien arvojen tapauksessa. Salauslähdelause sanoo, että jokaiselle, jokaiselle resurssin entropiaa suuremmalle arviolle on riittävän suuri n ja salaaja, joka ottaa n NOP-kopiota resurssista , , ja kartoittaa sen binääribitteihin sellaisella tavalla. että alkuperäinen merkki voidaan palauttaa binääribitistä, X todennäköisyydellä vähintään . $X$ $\epsilon >0$ $X^{1:n}$ ${\näyttötyyli n.(H(X)+\epsilon )}$ $X^{1:n}$ $1-\epsilon$

Todiste

Otetaan vähän . kaava, , näyttää tältä: $\epsilon >0$ ${\displaystyle 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)\oikea|<\epsilon \oikea\}$

AEP osoittaa, että riittävän suurella n :llä lähteestä generoitu sekvenssi on epäluotettava tyypillisessä tapauksessa - , konvergentti. Jos kyseessä on riittävän suuri: n , (katso AEP) ${\displaystyle A_{n}^{\epsilon ))$ $P(A_{n}^{\epsilon })>1-\epsilon$

Tyypillisten joukkojen määritelmä tarkoittaa, että ne sekvenssit, jotka sijaitsevat tyypillisessä joukossa, täyttävät:

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

Huomaa, että:

Todennäköisyys, josta sekvenssi saatiin $X$

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

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )))$ koska väestön kokonaistodennäköisyys on suurin. ${\displaystyle {A_{\epsilon }}^{(n)))$

${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )))$ . Käytä todisteeksi ylätodennäköisyysrajaa jokaiselle termille tyypillisessä tapauksessa ja alarajaa yleisessä tapauksessa . ${\displaystyle {A_{\epsilon }}^{(n)))$

Biteillä aloittaminen riittää erottamaan minkä tahansa merkkijonon $\left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon ) \;$

Salausalgoritmi: kooderi tarkistaa, onko saapuva sekvenssi epätosi, jos on, palauttaa sekvenssin saapuvan taajuuden indeksin, jos ei, palauttaa satunnaisen numeroluvun. numeerinen arvo. Jos syötteen todennäköisyys on väärä sekvenssissä (taajuudella noin ), kooderi ei tuota virhettä. Eli virheen todennäköisyys on suurempi kuin ${\näyttötyyli n.(H(X)+\epsilon )}$ $1-\epsilon$ $\epsilon$

Todiste kääntyvyydestä Käänteisyyden todistaminen perustuu siihen tosiasiaan, että vaaditaan osoittamaan, että jokaiselle sekvenssille, jonka koko on pienempi kuin (eksponentin merkityksessä), kattaa 1:n rajoittaman sekvenssin taajuuden. ${\displaystyle A_{n}^{\epsilon ))$

Todistus merkkikoodien salauslähdelauseesta

Olkoon sanan pituus jokaiselle mahdolliselle ( ). Määritellään , missä C valitaan siten, että: . $si}$ $x_{i}$ $i = 1, \ldots, n$ $q_{i}=a^{-s_{i}}/C$ $\sum q_{i}=1$

Sitten

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

jossa toinen rivi on Gibbsin epäyhtälö ja viides rivi on Kraft-epäyhtälö , . $C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ $\log C\leq 0$

toiselle epätasa-arvolle, jonka voimme asettaa

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

niin

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

ja sitten

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

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

Näin ollen minimi S täyttää

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

Muistiinpanot

Kansi, Thomas M. Luku 5: Tietojen pakkaus // Tietoteorian elementit (uuspr.) . - John Wiley & Sons , 2006. - ISBN 0-471-24195-4 .
C. E. Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , voi. 27, s. 379-423, 623-656, heinäkuu, lokakuu, 1948