Hispanopedia Wiki
Articulo de referencia

Teorema de codificación de canal ruidoso

En teoría de la información , el teorema de codificación de canal ruidoso (a veces llamado teorema de Shannon o límite de Shannon ) establece que, para cualquier grado de contam...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de la información , el teorema de codificación de canal ruidoso (a veces llamado teorema de Shannon o límite de Shannon ) establece que, para cualquier grado de contaminación por ruido en un canal de comunicación , es posible (en teoría) transmitir datos discretos ( información digital ) prácticamente sin errores hasta una tasa máxima computable a través del canal. Este resultado fue presentado por Claude Shannon en 1948 y se basó en parte en trabajos e ideas previas de Harry Nyquist y Ralph Hartley .

El límite de Shannon o capacidad de Shannon de un canal de comunicación se refiere a la tasa máxima de datos sin errores que teóricamente se pueden transferir a través del canal si el enlace está sujeto a errores aleatorios de transmisión de datos, para un nivel de ruido determinado. Fue descrito por primera vez por Shannon (1948) y publicado poco después en un libro de Shannon y Warren Weaver titulado The Mathematical Theory of Communication (1949). Esto sentó las bases de la disciplina moderna de la teoría de la información .

Descripción general

Enunciado por Claude Shannon en 1948, el teorema describe la máxima eficiencia posible de los métodos de corrección de errores frente a los niveles de interferencia de ruido y corrupción de datos . El teorema de Shannon tiene amplias aplicaciones tanto en comunicaciones como en almacenamiento de datos . Este teorema es de vital importancia para el campo moderno de la teoría de la información . Shannon solo ofreció un esbozo de la demostración. La primera demostración rigurosa para el caso discreto se encuentra en ( Feinstein, 1954 ) .

El teorema de Shannon establece que dado un canal ruidoso con capacidad de canal C e información transmitida a una tasa R , entonces siR<do{\displaystyle R<C}Existen códigos que permiten que la probabilidad de error en el receptor sea arbitrariamente pequeña. Esto significa que, teóricamente, es posible transmitir información casi sin errores a cualquier velocidad por debajo de una velocidad límite , C.

Lo contrario también es importante. SiR>do{\displaystyle R>C}No es posible lograr una probabilidad de error arbitrariamente pequeña. Todos los códigos tendrán una probabilidad de error superior a un cierto nivel mínimo positivo, y este nivel aumenta con la velocidad. Por lo tanto, no se puede garantizar la transmisión fiable de información a través de un canal a velocidades que superen su capacidad. El teorema no contempla la rara situación en la que la velocidad y la capacidad son iguales.

La capacidad del canaldo{\displaystyle C}se puede calcular a partir de las propiedades físicas de un canal; para un canal de ancho de banda limitado con ruido gaussiano, utilizando el teorema de Shannon-Hartley .

Los esquemas simples como "enviar el mensaje 3 veces y usar un esquema de votación de 2 de 3 si las copias difieren" son métodos de corrección de errores ineficientes, incapaces de garantizar asintóticamente que un bloque de datos se pueda comunicar sin errores. Técnicas avanzadas como los códigos Reed-Solomon y, más recientemente, los códigos de verificación de paridad de baja densidad (LDPC) y los códigos turbo , se acercan mucho más al límite teórico de Shannon, pero a costa de una alta complejidad computacional. Usando estos códigos altamente eficientes y con la potencia de cálculo de los procesadores de señales digitales actuales , ahora es posible acercarse mucho al límite de Shannon. De hecho, se demostró que los códigos LDPC pueden alcanzar dentro de 0,0045  dB del límite de Shannon (para canales de ruido blanco gaussiano aditivo binario (AWGN), con longitudes de bloque muy largas). [ 1 ]

Enunciado matemático

Gráfico que muestra la proporción de la capacidad de un canal ( eje y ) que se puede utilizar para la carga útil en función del nivel de ruido del canal (probabilidad de inversión de bits; eje x ).

El modelo matemático básico para un sistema de comunicación es el siguiente:

→MensajeWCodificadorFnorte→minortedoodmidsmiqtúminortedomiincógnitanorteCanalpag(y|incógnita)→RmidomiivmidsmiqtúminortedomiYnorteDescifradorgramonorte→mistimetroatmidmetromissagramomiW^{\displaystyle {\xrightarrow[{\text{Mensaje}}]{W}}{\begin{array}{|c| }\hline {\text{Codificador}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Secuencia \atop codificada} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Canal}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Secuencia \atop recibida} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decodificador}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Mensaje \atop estimado} }]{\hat {W}}}}

Un mensaje W se transmite a través de un canal ruidoso mediante funciones de codificación y decodificación. Un codificador transforma W en una secuencia predefinida de símbolos de canal de longitud n . En su modelo más básico, el canal distorsiona cada uno de estos símbolos independientemente de los demás. La salida del canal —la secuencia recibida— se introduce en un decodificador que transforma la secuencia en una estimación del mensaje. En este contexto, la probabilidad de error se define como:

PAGmi=Pr{W^≠W}.{\displaystyle P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.}

Teorema (Shannon, 1948):

1. Para cada canal discreto sin memoria, la capacidad del canal , definida en términos de la información mutuaI(incógnita;Y){\displaystyle I(X;Y)}como
 do=sorberpagincógnitaI(incógnita;Y){\displaystyle \ C=\sup _{p_{X}}I(X;Y)}[ 2 ]
tiene la siguiente propiedad. Para cualquierϵ>0{\displaystyle \epsilon >0}yR<do{\displaystyle R<C}, para lo suficientemente grandenorte{\displaystyle N}, existe un código de longitudnorte{\displaystyle N}y tasa≥R{\displaystyle \geq R}y un algoritmo de decodificación, de tal manera que la probabilidad máxima de error de bloque sea≤ϵ{\displaystyle \leq \epsilon }.
2. Si existe una probabilidad de error de bitpagb{\displaystyle p_{b}}es aceptable, tarifas hastaR(pagb){\displaystyle R(p_{b})}son alcanzables, donde
R(pagb)=do1−H2(pagb).{\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}
yH2(pagb){\displaystyle H_{2}(p_{b})}es la función de entropía binaria
H2(pagb)=−[pagbregistro2⁡pagb+(1−pagb)registro2⁡(1−pagb)]{\displaystyle H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]}
3. Para cualquierpagb{\displaystyle p_{b}}tasas superiores aR(pagb){\displaystyle R(p_{b})}no son alcanzables.

(MacKay (2003), pág.  162; cf. Gallager (1968), cap. 5; Cover y Thomas (1991), pág.  198; Shannon (1948), teorema 11)

Esquema de la prueba

Al igual que otros resultados importantes en la teoría de la información, la demostración del teorema de codificación de canales ruidosos incluye un resultado de alcanzabilidad y un resultado recíproco equivalente. Estos dos componentes sirven para acotar, en este caso, el conjunto de tasas posibles a las que se puede comunicar a través de un canal ruidoso, y el resultado equivalente demuestra que estos límites son ajustados.

Los siguientes esquemas son solo uno de los muchos estilos diferentes disponibles para el estudio en los textos de teoría de la información.

Posibilidad de lograrlo para canales discretos sin memoria

Esta demostración particular de alcanzabilidad sigue el estilo de las demostraciones que utilizan la propiedad de equipartición asintótica (PEA). Otro estilo se puede encontrar en textos de teoría de la información que utilizan exponentes de error .

Ambos tipos de pruebas utilizan un argumento de codificación aleatoria en el que el libro de códigos utilizado a través de un canal se construye aleatoriamente; esto sirve para simplificar el análisis al tiempo que demuestra la existencia de un código que satisface una baja probabilidad de error deseada a cualquier velocidad de datos inferior a la capacidad del canal .

Mediante un argumento relacionado con AEP, dado un canal, longitudnorte{\displaystyle n}cadenas de símbolos fuenteincógnita1norte{\displaystyle X_{1}^{n}}y longitudnorte{\displaystyle n}cadenas de salidas de canalY1norte{\displaystyle Y_{1}^{n}}Podemos definir un conjunto típico conjunto de la siguiente manera:

Aε(norte)={(incógnitanorte,ynorte)∈incógnitanorte×Ynorte{\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}
2−norte(H(incógnita)+ε)≤pag(incógnita1norte)≤2−norte(H(incógnita)−ε){\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}
2−norte(H(Y)+ε)≤pag(Y1norte)≤2−norte(H(Y)−ε){\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}
2−norte(H(incógnita,Y)+ε)≤pag(incógnita1norte,Y1norte)≤2−norte(H(incógnita,Y)−ε)}{\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}

Decimos que dos secuenciasincógnita1norte{\displaystyle {X_{1}^{n}}}yY1norte{\displaystyle Y_{1}^{n}}son conjuntamente típicos si pertenecen al conjunto conjuntamente típico definido anteriormente.

Pasos

  1. Al estilo del argumento de codificación aleatoria, generamos aleatoriamente2norteR{\displaystyle 2^{nR}}palabras clave de longitud n de una distribución de probabilidad Q.
  2. Este código se revela al emisor y al receptor. También se supone que se conoce la matriz de transición.pag(y|incógnita){\displaystyle p(y|x)}para el canal que se está utilizando.
  3. Se elige un mensaje W de acuerdo con la distribución uniforme en el conjunto de palabras clave. Es decir,PAGr(W=w)=2−norteR,w=1,2,…,2norteR{\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}}.
  4. El mensaje W se envía a través del canal.
  5. El receptor recibe una secuencia segúnPAG(ynorte|incógnitanorte(w))=∏i=1nortepag(yi|incógnitai(w)){\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}
  6. Al enviar estas palabras clave a través del canal, recibimosY1norte{\displaystyle Y_{1}^{n}}y decodificar a alguna secuencia fuente si existe exactamente 1 palabra clave que sea conjuntamente típica con Y. Si no hay palabras clave conjuntamente típicas, o si hay más de una, se declara un error. También se produce un error si una palabra clave decodificada no coincide con la palabra clave original. Esto se denomina decodificación de conjunto típico .

La probabilidad de error de este esquema se divide en dos partes:

  1. En primer lugar, puede producirse un error si no se encuentran secuencias X típicas conjuntas para una secuencia Y recibida.
  2. En segundo lugar, puede producirse un error si una secuencia X incorrecta es típica conjuntamente con una secuencia Y recibida.
  • Debido a la aleatoriedad de la construcción del código, podemos suponer que la probabilidad promedio de error, calculada sobre todos los códigos, no depende del índice enviado. Por lo tanto, sin pérdida de generalidad , podemos suponer que W = 1.
  • A partir del AEP conjunto, sabemos que la probabilidad de que no exista un X conjuntamente típico tiende a 0 a medida que n crece. Podemos acotar esta probabilidad de error medianteε{\displaystyle \varepsilon }.
  • También a partir del AEP conjunto, conocemos la probabilidad de que un evento en particular ocurra.incógnita1norte(i){\displaystyle X_{1}^{n}(i)}y elY1norte{\displaystyle Y_{1}^{n}}resultantes de W = 1 son conjuntamente típicos es≤2−norte(I(incógnita;Y)−3ε){\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}}.

Definir:mii={(incógnita1norte(i),Y1norte)∈Aε(norte)},i=1,2,…,2norteR{\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}

como el evento de que el mensaje i es conjuntamente típico con la secuencia recibida cuando se envía el mensaje 1.

PAG(error)=PAG(error|W=1)≤PAG(mi1do)+∑i=22norteRPAG(mii)≤PAG(mi1do)+(2norteR−1)2−norte(I(incógnita;Y)−3ε)≤ε+2−norte(I(incógnita;Y)−R−3ε).{\displaystyle {\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}}

Podemos observar que comonorte{\displaystyle n}va al infinito, siR<I(incógnita;Y){\displaystyle R<I(X;Y)}Para el canal, la probabilidad de error tenderá a 0.

Recíproco débil para canales discretos sin memoria

Supongamos que un código de2norteR{\displaystyle 2^{nR}}palabras clave. Sea W un índice dibujado uniformemente sobre este conjunto.incógnitanorte{\displaystyle X^{n}}yYnorte{\displaystyle Y^{n}}sean las palabras clave transmitidas y las palabras clave recibidas, respectivamente.

  1. norteR=H(W)=H(W|Ynorte)+I(W;Ynorte){\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})}utilizando identidades que involucran entropía e información mutua
  2. ≤H(W|Ynorte)+I(incógnitanorte(W);Ynorte){\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}ya que X es una función de W
  3. ≤1+PAGmi(norte)norteR+I(incógnitanorte(W);Ynorte){\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}mediante el uso de la desigualdad de Fano.
  4. ≤1+PAGmi(norte)norteR+nortedo{\displaystyle \leq 1+P_{e}^{(n)}nR+nC}por el hecho de que la capacidad se maximiza mediante la información mutua.

El resultado de estos pasos es quePAGmi(norte)≥1−1norteR−doR{\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}. A medida que aumenta la longitud del bloquenorte{\displaystyle n}va al infinito, obtenemosPAGmi(norte){\displaystyle P_{e}^{(n)}}está acotado lejos de 0 si R es mayor que C; podemos obtener tasas de error arbitrariamente bajas solo si R es menor que C.

Fuerte recíproco para canales discretos sin memoria

Un fuerte teorema recíproco, demostrado por Wolfowitz en 1957, [ 3 ] establece que,

PAGmi≥1−4Anorte(R−do)2−mi−norte(R−do)2{\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}

para alguna constante positiva finitaA{\displaystyle A}Mientras que el recíproco débil establece que la probabilidad de error está acotada lejos de cero comonorte{\displaystyle n}va al infinito, el recíproco fuerte establece que el error tiende a 1. Por lo tanto,do{\displaystyle C}Existe una marcada diferencia entre una comunicación perfectamente fiable y una comunicación completamente poco fiable.

Refinamientos de longitud de bloque finita

Los refinamientos de longitud de bloque finita del teorema de codificación de canal ruidoso estudian la mejor tasa de codificación a una longitud de bloque fija, en lugar de solo la capacidad límite. Masahito Hayashi utilizó el método del espectro de información para derivar fórmulas de tasa de codificación de segundo orden para la codificación de canal, incluyendo canales estacionarios sin memoria y canales markovianos aditivos. [ 4 ]

Teorema de codificación de canal para canales no estacionarios sin memoria

Partimos de la base de que el canal no tiene memoria, pero sus probabilidades de transición cambian con el tiempo, de una forma conocida tanto por el transmisor como por el receptor.

Entonces, la capacidad del canal viene dada por

do=límiteinfmáximopag(incógnita1),pag(incógnita2),...1norte∑i=1norteI(incógnitai;Yi).{\displaystyle C=\lim \inf \max _{p^{(X_{1})},p^{(X_{2})},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).}

El máximo se alcanza en la capacidad que logra las distribuciones para cada canal respectivo. Es decir, do=límiteinf1norte∑i=1nortedoi{\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}} dóndedoi{\displaystyle C_{i}}es la capacidad del i- ésimo canal.

Esquema de la prueba

La demostración se desarrolla de forma casi idéntica a la del teorema de codificación de canales. La alcanzabilidad se deduce de la codificación aleatoria, donde cada símbolo se elige al azar de la distribución de capacidad para ese canal en particular. Los argumentos de tipicidad utilizan la definición de conjuntos típicos para fuentes no estacionarias, tal como se define en el artículo sobre la propiedad de equipartición asintótica .

La tecnicidad de lim inf entra en juego cuando1norte∑i=1nortedoi{\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}no converge.

Véase también

Notas

  1. ↑ Sae-Young Chung; Forney, GD ; Richardson, TJ; Urbank, R. (febrero de 2001). "Sobre el diseño de códigos de verificación de paridad de baja densidad dentro de 0,0045 dB del límite de Shannon" (PDF) . IEEE Communications Letters . 5 (2): 58– 60. Bibcode : 2001IComL...5...58C . doi : 10.1109/4234.905935 . S2CID 7381972 . 
  2. ↑ Para una descripción de la función "sup", consulte Supremo.
  3. ↑ Gallager, Robert (1968). Teoría de la información y comunicación fiable . Wiley. ISBN 0-471-29048-3.
  4. ↑ Hayashi, Masahito (noviembre de 2009). "Enfoque del espectro de información para la tasa de codificación de segundo orden en la codificación de canal". IEEE Transactions on Information Theory . 55 (11): 4947– 4966. arXiv : 0801.2242 . doi : 10.1109/TIT.2009.2030478 .

Referencias

  • Aazhang, B. (2004). "Teorema de codificación de canal ruidoso de Shannon" (PDF) . Connections .
  • Cover, TM ; Thomas, JA (1991). Elementos de la teoría de la información . Wiley. ISBN 0-471-06259-6.
  • Fano, RM (1961). Transmisión de información; una teoría estadística de las comunicaciones . MIT Press. ISBN 0-262-06001-9.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
  • Feinstein, Amiel (septiembre de 1954). "Un nuevo teorema básico de la teoría de la información". Transactions of the IRE Professional Group on Information Theory . 4 (4): 2– 22. Bibcode : 1955PhDT........12F . doi : 10.1109/TIT.1954.1057459 . hdl : 1721.1/4798 .
  • Lundheim, Lars (2002). "Sobre Shannon y la fórmula de Shannon" (PDF) . Telektronik . 98 (1): 20–29 .
  • MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge University Press. ISBN 0-521-64298-1. [gratis en línea]
  • Shannon, CE (1948). "Una teoría matemática de la comunicación". Bell System Technical Journal . 27 (3): 379– 423. Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x .
  • Shannon, CE (1998) [1948]. Una teoría matemática de la comunicación . University of Illinois Press.
  • Wolfowitz, J. (1957). "La codificación de mensajes sujetos a errores aleatorios" . Illinois J. Math . 1 (4): 591– 606. doi : 10.1215/ijm/1255380682 .