Segona teorema de Shannon

En teoria de l'informació, la segona teorema de Shannon denominat també de «teorema de codificació de canal», o simplement teorema de Shannon, és un teorema, matemàtic enunciat per Claude Shannon , que mostra que és possible transmetre senyes discretes (informació digital) casi sense errors sobre un mateix canal sorollós, a un règim màxim computable. Se li coneix simplement com a «teorema de Shannon» (a pesar de que és el segon) posat que esta teorema conjuntament en l'obra de Claude Shannon sobre la teoria de l'informació, varen tindre una importància fonamental en la teoria de l'informació, oferint amples aplicacions en els dominis de les telecomunicacions i del almagasenament d'informació.

El llímit de Shannon o la capacitat de Shannon d'un canal de comunicacions és la velocitat teòrica màxima de transferència d'informació del canal, per a un nivell de soroll determinat, que és el màxim fixat en la cantitat de símbols per segon que poden ser transferits a través d'esta conexió en soroll. Este enunciat publicat per Claude Shannon el 1948 es va basar sobre treballs anteriors d'Harry Nyquist i Ralph Hartley. La primera prova rigorosa va ser establida per Amiel Feinstein el 1954.

Enunciat

Una de les principals ventages de la tecnologia digital és que permet l'intercanvi de senyes sense pèrdua d'informació. Aixina i tot, estes senyes transiten la majoria del temps sobre canals no fiables, sofrint vàries interferències i per lo tant es mesclen en el soroll. Llavors, ¿cóm es poden eliminar els errors de transmissió? La solució consistix en introduir certa redundància en els mensages emesos per la font en la finalitat de que el receptor puga corregir els errors, de tal forma que el mensage siga compost per $n+k$ símbols, en a on $n$ és la cantitat de símbols que aporten informació sobre el mensage original (aquell que l'emissor va transmetre), i $k$ és la cantitat de símbols de redundància, mateixos que li serviran al receptor per a corregir els errors que el canal sorollós haja introduït en el mensage, cal recordar que estos $k$ símbols de redundància també estan subjectes a deformacions pel soroll del canal. A este tipo de còdic se li crida còdic corrector.

La Segona Teorema de Shannon demostra l'existència d'un còdic corrector que el seu $k$ complix lo dit anteriorment, en una provabilitat d'interpretar un mensage de forma errada molt menuda, i en una velocitat de transmissió que s'aproxima a la capacitat del canal.

El temps necessari per a enviar un símbol per la llínea r, el símbols cridat. Dins de la símbols la senyal seguix sent el mateix.

$N_{bits}={\log }_2(N_{symbols})$

En dos símbols definits (Nsymbols = 2), per lo tant, _Nsymbols transportats, en 8-PSK tres bits i en QAM-64, sis bits.

L'unitat per a medir el número de símbols per segon és el baut.

Formulació matemàtica

Teorema (Shannon, 1948):

1. Per a qualsevol canal discret sense memòria, la capacitat de canal.

$C=\underset{p_X}{\sup }I(X;Y)$.

Té la següent propietat. Per a qualsevol ε> 0 i R <C, per a N prou gran, existix un còdic de llongitut N i una taxa ≥ R i un algoritme de descodificació, de manera que la provabilitat màxima d'error de bloc és ≤ ε.

2. Si la provabilitat d'error de bits pb és acceptable, les taxes de transmissió fins a R (pb) són alcanzables, a on

$R(p_b)=\frac{C}{1-H_2(p_b)}.$

i $H_2(p_b)$ és la funció entropía binaria

$H_2(p_b)=-[p_b{\log }_2{p}_b+(1-p_b){\log }_2(1-p_b)]$

3. Per a qualsevol pb, les taxes de transmissió més grans que R (pb) no són alcanzables.

(MacKay (2003), p. 162; de Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11)

Vore també

• Paradoxa de Freedman
• Desigualtat de Jensen
• Teorema de codificació de fonts 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 [free on-line]
• 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.