Primera teorema de Shannon

En teoria de l'informació, la teorema de codificació de fonts, primera teorema de Shannon o, menys utilisat, teorema de codificació sense soroll és un teorema enunciat per Claude Shannon en 1948 que establix el llímit teòric per a la compressió d'una font de senyes, aixina com el significat operacional de l'entropía de Shannon.

La primera teorema de Shannon demostra que, en el llímit d'una cadena de variables aleatòries independents i idénticamente distribuïdes de senyes que tendix a infinit, és impossible comprimir l'informació de manera que la relació de codificació (número mig de bits per símbol) siga menor que la entropía de Shannon de la font, si es garantisa que no hi haja pèrdua d'informació. No obstant, sí és possible conseguir una relació de codificació arbitrariamente prop del valor de la entropía de Shannon.

La primera teorema de Shannon establix una cota inferior i superior de la llongitut mínima possible de bits d'informació com a funció de l'entropía.

Enunciat

La codificació d'una font és una correspondència entre una seqüència de símbols d'una font d'informació i una seqüència de símbols d'un alfabet (generalment bits) de manera que els símbols de la font poden ser recuperats posteriorment de forma exacta des dels bits binaris (codificació sense pèrdues) o recuperar-la en alguna distorsió (codificació en pèrdues), pero que seguixquen sent entendibles. Est és el concepte darrere de la compressió de senyes.

Primera teorema de Shannon

En la Teoria de l'Informació, la primera teorema de Shannon (Shannon 1948) informalmente expressa que: (MacKay 2003, p. 81. Cover 2006, Capítul 5.):

N i.i.d. variables aleatòries cada una en una entropía H(X) pot ser comprimida en més de N H(X) bits en un risc despreciable de pèrdua d'informació , segonsN → ∞; pero a l'inversa, si són comprimits en menys de N H(X) bits és pràcticament segur que es produïx pèrdua d'informació.

Primera teorema de Shannon per a còdics simbòlics

Sean Σ₁, Σ₂ dos alfabets finitos i siguen ΣPlantilla:La seua i ΣPlantilla:La seua els conjunts finitos de paraules d'eixos alfabets (respectivament).

Suponga que X és una variable aleatòria prenent valors en Σ₁ i siga  f  un còdic singularment decodificable des deΣPlantilla:La seua aΣPlantilla:La seua a on|Σ₂| = a. Siga S la variable aleatòria donada per la llongitut de la paraula clau f (X).

Si f  és òptim en el sentit de que té la llongitut de paraula clau mínima esperada per a X, llavors (Shannon 1948):

$\frac{H(X)}{{\log }_{2}a}\le 𝔼S<\frac{H(X)}{{\log }_{2}a}+1$

Demostració: Teorema de codificació de la font

Siga X una font de variables aleatòries independents idénticamente distribuïdes (i.i.d.), la seua série temporal X₁,…,X_n és també i.i.d. en entropía H(X) en el cas discret i entropía diferencial en el cas continu.

La teorema de codificació font establix que per a qualsevol ε>0 hi ha una cantitat suficientment gran n i un codificador que pren n i.i.d repeticions de la font, X^1:n, i ho du a $n\left(H\right(X)+\epsilon )$bits binaris de tal manera que els símbols font X^1:n són recuperables dels bits binaris en provabilitat d'a lo manco 1-ε.

Demostració de la seua accessibilitat: Arregla alguns  i deixa

$p(x_1,\mathrm{...},x_n)=P_r[X_1=x_1,\mathrm{...},X_n=x_n]$

El conjunt típic $A_n^{\epsilon }$es definix com:

$A_n^{\epsilon }=\{(x_1,\mathrm{...},x_n):|-\frac{1}{n}logp(x_1,\mathrm{...},x_n)-H_n(X)|<\epsilon \}$

La propietat de equipartición asintòtica mostra que per a cantitats suficientment grans de n, la provabilitat de que una seqüència generada per la font es trobe en dit conjunt s'acosta a un.

La definició de conjunts típics implica que aquelles seqüències que es troben en dit conjunt satisfan:

$2^{n(H(X)+\epsilon }\le p(x_1,\mathrm{...},x_n)\le 2^{n(H(X)-\epsilon }$

Note's que:

• La provabilitat de que una seqüència  $(X_1,\mathrm{...},X_n)$ siga extreta de $A_n^{\epsilon }$ és major que 1-ε.
• $|A_n^{\epsilon }|\le 2^{-n(H(X)+\epsilon )}$
• $|A_n^{\epsilon }|\le (1-\epsilon )2^{-n(H(X)-\epsilon )}$   

Ya que $|A_n^{\epsilon }|\le 2^{-n(H(X)+\epsilon )}$, $n(H(X)+\epsilon )$ bits són suficients per a senyalar qualsevol cadena en este conjunt. La demostració inversa es realisa mostrant que qualsevol conjunt menor que $A_n^{\epsilon }$ (en el sentit d'exponent), cobriria un conjunt de provabilitats llimitades des de 0.

Vore també

• Paradoxa de Freedman
• Desigualtat de Jensen
• Segona teorema de Shannon
• Teorema de Shannon-Hartley

Bibliografia

• Cover T. M., Thomas J. A., Elements of Information Theory, John Wiley & Sons, 1991. ISBN 0-471-06259-6
• Fano, R. A., Transmission of information; a statistical theory of communications, MIT Press, 1961. ISBN 0-262-06001-9
• Feinstein, Amiel, "A New basic theorem of information theory", IEEE Transactions a on Information Theory, 4(4): 2-22, 1954.
• MacKay, David J. C., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003. ISBN 0-521-64298-1 [disponible en llínea]
• Shannon, C. E., A Mathematical Theory of Communication
• Archivat el 31 de giner de 1998 archivat en Wayback Machine. Urbana, IL: University of Illinois Press, 1949 (reprinted 1998).
• Wolfowitz, J., "The coding of messages subject to chance errors", Illinois J. Math., 1: 591–606, 1957.