Teorema de codificación de canal ruidoso

Information theory
Entropy Differential entropy Conditional entropy Joint entropy Mutual information Directed information Conditional mutual information Relative entropy Entropy rate Limiting density of discrete points
Asymptotic equipartition property Rate–distortion theory
Shannon's source coding theorem Channel capacity Noisy-channel coding theorem Shannon–Hartley theorem
v t e

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 dado de contaminación por ruido de un canal de comunicación, es posible (en teoría) comunicar datos discretos ( información digital ) casi 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 anteriores 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 libres de 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 particular. Fue descrito por primera vez por Shannon (1948), y poco después publicado en un libro de Shannon y Warren Weaver titulado The Mathematical Theory of Communication (1949). Esto fundó la disciplina moderna de la teoría de la información .

El teorema, enunciado por Claude Shannon en 1948, 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 una amplia gama de aplicaciones tanto en comunicaciones como en almacenamiento de datos . Este teorema es de importancia fundamental para el campo moderno de la teoría de la información . Shannon sólo dio un esbozo de la prueba. La primera prueba rigurosa para el caso discreto se da en (Feinstein 1954).

El teorema de Shannon establece que, dado un canal ruidoso con una capacidad de canal C y una velocidad de transmisión de información R , existen códigos que permiten que la probabilidad de error en el receptor sea arbitrariamente pequeña. Esto significa que, en teoría, es posible transmitir información casi sin errores a cualquier velocidad por debajo de una velocidad límite, C .${\displaystyle R<C}$

La inversa también es importante. Si , no se puede lograr una probabilidad de error arbitrariamente pequeña. Todos los códigos tendrán una probabilidad de error mayor que un cierto nivel mínimo positivo, y este nivel aumenta a medida que aumenta la velocidad. Por lo tanto, no se puede garantizar que la información se transmita de manera confiable a través de un canal a velocidades que superen la capacidad del canal. El teorema no aborda la situación poco común en la que la velocidad y la capacidad son iguales.${\displaystyle R>C}$

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

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 pueda comunicarse sin errores. Las 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 computacional de los procesadores de señales digitales actuales , ahora es posible llegar muy cerca del límite de Shannon. De hecho, se demostró que los códigos LDPC pueden llegar 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]

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

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

Un mensaje W se transmite a través de un canal ruidoso mediante funciones de codificación y decodificación. Un codificador asigna W a 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 asigna la secuencia a una estimación del mensaje. En este contexto, la probabilidad de error se define como:

${\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 mutua como${\displaystyle I(X;Y)}$

${\displaystyle \ C=\sup _{p_{X}}I(X;Y)}$^[2]

tiene la siguiente propiedad. Para cualquier y , para valores suficientemente grandes , existe un código de longitud y velocidad y un algoritmo de decodificación, de modo que la probabilidad máxima de error de bloque es .${\displaystyle \epsilon >0}$${\displaystyle R<C}$${\displaystyle N}$${\displaystyle N}$${\displaystyle \geq R}$${\displaystyle \leq \epsilon }$

2. Si la probabilidad de error de bit es aceptable, se pueden alcanzar tasas de hasta , donde${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

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

y es la función de entropía binaria${\displaystyle H_{2}(p_{b})}$

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

3. Para cualquier , no se pueden alcanzar tasas mayores que .${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

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

Al igual que con otros resultados importantes de la teoría de la información, la prueba del teorema de codificación de canal ruidoso incluye un resultado de viabilidad y un resultado inverso coincidente. Estos dos componentes sirven para limitar, en este caso, el conjunto de velocidades posibles a las que se puede comunicar a través de un canal ruidoso, y la coincidencia sirve para mostrar que estos límites son estrictos.

Los siguientes esquemas son sólo un conjunto de muchos estilos diferentes disponibles para estudiar textos de teoría de la información.

Esta prueba particular de viabilidad sigue el estilo de las pruebas que utilizan la propiedad de equipartición asintótica (AEP). Se puede encontrar otro estilo 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 donde el libro de códigos utilizado en un canal se construye aleatoriamente: esto sirve para simplificar el análisis y al mismo tiempo demostrar la existencia de un código que satisface una baja probabilidad de error deseada a cualquier velocidad de datos por debajo de la capacidad del canal .

Mediante un argumento relacionado con AEP, dado un canal, cadenas de longitud de símbolos de origen y cadenas de longitud de salidas de canal , podemos definir un conjunto típico conjunto de la siguiente manera:${\displaystyle n}$${\displaystyle X_{1}^{n}}$${\displaystyle n}$${\displaystyle Y_{1}^{n}}$

${\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}$

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}$

${\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}$

${\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 secuencias y son conjuntamente típicas si se encuentran en el conjunto conjuntamente típico definido anteriormente.${\displaystyle {X_{1}^{n}}}$${\displaystyle Y_{1}^{n}}$

Pasos

1. Al estilo del argumento de codificación aleatoria, generamos aleatoriamente palabras de código de longitud n a partir de una distribución de probabilidad Q.${\displaystyle 2^{nR}}$
2. Este código se revela al emisor y al receptor. También se supone que se conoce la matriz de transición del canal que se está utilizando.${\displaystyle p(y|x)}$
3. Se elige un mensaje W según la distribución uniforme en el conjunto de palabras de código. Es decir, .${\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ún${\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}$
6. Al enviar estas palabras de código a través del canal, recibimos , y decodificamos en alguna secuencia de origen si existe exactamente 1 palabra de código que sea típica conjuntamente con Y. Si no hay palabras de código típicas conjuntamente, o si hay más de una, se declara un error. También se produce un error si una palabra de código decodificada no coincide con la palabra de código original. Esto se denomina decodificación de conjunto típico .${\displaystyle Y_{1}^{n}}$

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 conjuntamente típicas para una secuencia Y recibida
2. En segundo lugar, puede producirse un error si una secuencia X incorrecta es conjuntamente típica con una secuencia Y recibida.

• Por la aleatoriedad de la construcción del código, podemos suponer que la probabilidad media de error promediada 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 ningún X común típico tiende a 0 a medida que n aumenta. Podemos limitar esta probabilidad de error mediante .${\displaystyle \varepsilon }$
• Además, a partir del AEP conjunto, sabemos que la probabilidad de que un particular y el resultante de W = 1 sean conjuntamente típicos es .${\displaystyle X_{1}^{n}(i)}$${\displaystyle Y_{1}^{n}}$${\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}}$

Definir:${\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.

${\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 a medida que se tiende al infinito, si para el canal, la probabilidad de error irá a 0.${\displaystyle n}$${\displaystyle R<I(X;Y)}$

Finalmente, dado que se demuestra que el libro de códigos promedio es "bueno", sabemos que existe un libro de códigos cuyo desempeño es mejor que el promedio y por lo tanto satisface nuestra necesidad de una probabilidad de error arbitrariamente baja al comunicarse a través del canal ruidoso.

Supóngase un código de palabras clave. Sea W el que se dibuja uniformemente sobre este conjunto como índice. Sean y las palabras clave transmitidas y recibidas, respectivamente.${\displaystyle 2^{nR}}$${\displaystyle X^{n}}$${\displaystyle Y^{n}}$

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

El resultado de estos pasos es que . A medida que la longitud del bloque tiende al infinito, obtenemos que está acotado desde 0 si R es mayor que C; podemos obtener tasas de error arbitrariamente bajas solo si R es menor que C.${\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}$${\displaystyle n}$${\displaystyle P_{e}^{(n)}}$

Un teorema inverso fuerte, demostrado por Wolfowitz en 1957, ^[3] establece que,

${\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}$

para alguna constante positiva finita . Mientras que la inversa débil establece que la probabilidad de error está limitada a partir de cero y tiende al infinito, la inversa fuerte establece que el error tiende a 1. Por lo tanto, es un umbral claro entre una comunicación perfectamente confiable y una completamente no confiable.${\displaystyle A}$${\displaystyle n}$${\displaystyle C}$

Suponemos que el canal no tiene memoria, pero sus probabilidades de transición cambian con el tiempo, de una manera conocida tanto en el transmisor como en el receptor.

Entonces la capacidad del canal viene dada por

${\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 de lograr distribuciones para cada canal respectivo, es decir, donde es la capacidad del i- ésimo canal.${\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$${\displaystyle C_{i}}$

La prueba se desarrolla de forma prácticamente similar a la del teorema de codificación de canal. La viabilidad se deriva de una codificación aleatoria en la que cada símbolo se elige aleatoriamente de la distribución de capacidad de logro para ese canal en particular. Los argumentos de tipicidad utilizan la definición de conjuntos típicos para fuentes no estacionarias definida en el artículo sobre la propiedad de equipartición asintótica .

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

• Propiedad de equipartición asintótica (AEP)
• Desigualdad de Fano
• Teoría de la tasa de distorsión
• Teorema de codificación de fuentes de Shannon
• Teorema de Shannon-Hartley
• Código turbo

• Aazhang, B. (2004). "Teorema de codificación de canal ruidoso de Shannon" (PDF) . Conexiones .
• Portada, 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.
• Feinstein, Amiel (septiembre de 1954). "Un nuevo teorema básico de la teoría de la información". Transacciones del Grupo Profesional de Teoría de la Información del IRE . 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. doi :10.1002/j.1538-7305.1948.tb01338.x.
• Shannon, CE (1998) [1948]. Una teoría matemática de la comunicación. Prensa de la Universidad de Illinois.
• Wolfowitz, J. (1957). "La codificación de mensajes sujetos a errores aleatorios". Illinois J. Math . 1 (4): 591–606. doi : 10.1215/ijm/1255380682 .