Segon teorema de Shannon

En teoria de la informació, el segon teorema de Shannon anomenat també de "teorema de codificació de canal", é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 de 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

L'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. llavors , 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 parla de codificació de canal mitjançant un codi corrector.

El temps necessari per enviar un símbol per la línia r, el símbols anomenat. Dins de la símbols el senyal segueix sent el mateix.

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

Amb dos símbols definits (N_símbols = 2), per tant, símbols transportats, en 8-PSK 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é

• 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 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
• Shannon's Noisy Channel Coding Theorem

Portal: Informàtica