Segon teorema de Shannon

En teoria de la informació, el segon teorema de Shannon anomenat 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 dades discretes (informació digital) gairebé sense errors sobre un mateix canal sorollós, a un règim màxim computable. Se'l coneix simplement com "teorema de Shannon" (tot i que és el segon), ja que aquest teorema conjuntament amb l'obra de Claude Shannon sobre la teoria de la informació, van tenir una importància fonamental en la teoria de la informació, oferint amples aplicacions en els dominis de les telecomunicacions i en els principis emprat per a l'emmagatzematge d'informació.

El lí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 quantitat de símbols per segon que poden ser transferits a través d'aquesta connexió amb soroll. Aquest enunciat publicat per Claude Shannon el 1948 es va basar sobre treballs anteriors de Harry Nyquist i Ralph Hartley. La primera prova rigorosa va ser establerta per Amiel Feinstein el 1954.

Enunciat

Un dels principals avantatges de la tecnologia dita numèrica és de permetre l'intercanvi de dades sense pèrdua d'informació. Tanmateix, aquestes dades transiten la majoria del temps sobre canals no fiables, patint diverses interferències i per tant barrejades amb el soroll, aleshores, com, es poden eliminar els errors de transmissió? La solució consisteix en introduir una redundància en els missatges emesos per la font amb la finalitat de que el receptor pugui corregir els errors. Es coneix com a codificació de canal mitjançant un codi corrector.

El temps necessari per poder enviat un símbol per la línia, s'anomena temps de símbol. Dins del temps de símbol el senyal segueix sent el mateix.

$N_{bits}=\log _{2}(N_{symbols})$

El nombre de bits transportats guarda relació amb el nombre de símbols definits (P.e. N_symbols = 2), en 8-PSK són tres bits i en QAM-64, sis bits.

La unitat per a mesurar el nombre de símbols per segon és el Baud.

Formulació matemàtica

Teorema (Shannon, 1948):

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

$\ C=\sup _{p_{X}}I(X;Y)\,$

Té la següent propietat. Per a qualsevol ε> 0 i R <C, per a N prou gran, existeix un codi de longitud N i una taxa ≥ R i un algorisme de descodificació, de manera que la probabilitat màxima d'error de bloc és ≤ ε.

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

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

i $H_{2}(p_{b})$ és la funció entropía binària

$H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]$

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

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

Vegeu també

• Entropia de Shannon
• Paradoxa de Freedman
• Propietat d'equipartició asimptòtica (AEP)
• Desigualtat de Jensen
• Teoria de la taxa de distorsió
• Teorema de codificació de fonts de Shannon
• Teorema de Shannon-Hartley
• Codi Turbo

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 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 online]
• Shannon, C. E., A Mathematical Theory of Communication Arxivat 1998-01-31 a 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.

Enllaços externs

• CE Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, vol. 27, pp. 379–423, juliol de 1948.
• On Shannon and Shannon's law Arxivat 2016-03-15 a Wayback Machine.
• Shannon's Noisy Channel Coding Theorem