Teorema de codificación de canales ruidosos

Límite en la tasa de transferencia de datos

En teoría de la información , el teorema de codificación de canales ruidosos (a veces teorema de Shannon o límite de Shannon ), establece que para cualquier grado dado de contaminación acústica de un canal de comunicación, es posible (en teoría) comunicar datos discretos ( información digital ) casi con error. -Gratis hasta una tarifa 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 la 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 particular. Fue descrita por primera vez por Shannon (1948) y poco después publicada 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 .

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 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 capacidad de canal C e información transmitida a una velocidad R , entonces, si existen códigos que permiten que la probabilidad de error en el receptor se haga 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. ${\displaystyle R<C}$

Lo contrario 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 tasa. Por lo tanto, no se puede garantizar que la información se transmita de manera confiable a través de un canal a velocidades superiores a la capacidad del canal. El teorema no aborda la rara situación en la que tasa y 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}$

Esquemas simples como "enviar el mensaje 3 veces y usar el mejor esquema de votación 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. 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 a alcanzar el límite teórico de Shannon, pero a un costo de alta complejidad computacional. Utilizando 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 el límite de Shannon (para canales de ruido blanco gaussiano aditivo binario (AWGN), con longitudes de bloque muy largas). ^[1]

declaración matemática

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

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 utilizando 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 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 lo suficientemente grande , 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 sea . ${\displaystyle \epsilon >0}$ ${\displaystyle R<C}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle \geq R}$ ${\displaystyle \leq \epsilon }$

2. Si una 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 tarifa, no se pueden alcanzar tarifas superiores . ${\displaystyle p_{b}}$ ${\displaystyle R(p_{b})}$

(MacKay (2003), p. 162; cf. Gallager (1968), capítulo 5; Cover y Thomas (1991), p. 198; Shannon (1948) thm. 11)

Esquema de la prueba

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

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

Posibilidad de alcanzar canales discretos sin memoria

Esta prueba particular de alcanzabilidad sigue el estilo de las pruebas que utilizan la propiedad de equipartición asintótica (AEP). 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 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 inferior a la capacidad del canal .

Mediante un argumento relacionado con AEP, dado un canal, cadenas de longitud de símbolos fuente 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. En el estilo del argumento de codificación aleatoria, generamos aleatoriamente palabras en código de longitud n a partir de una distribución de probabilidad Q. ${\displaystyle 2^{nR}}$
2. Este código se revela al remitente y al destinatario. También se supone que se conoce la matriz de transición del canal que se utiliza. ${\displaystyle p(y|x)}$
3. Se elige un mensaje W según la distribución uniforme en el conjunto de palabras de código. Eso es, . ${\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 en código a través del canal, recibimos y decodificamos en alguna secuencia fuente si existe exactamente 1 palabra en código que sea conjuntamente típica con Y. Si no hay palabras en código típicas en conjunto, 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 llama decodificación de conjuntos típicos . ${\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 típicas conjuntas para una secuencia Y recibida.
2. En segundo lugar, puede producirse un error si una secuencia X incorrecta es común con una secuencia Y recibida.

• Por la aleatoriedad de la construcción del código, podemos suponer que la probabilidad promedio de error promediada entre todos los códigos no depende del índice enviado. Por tanto, sin pérdida de generalidad, podemos suponer W = 1.
• A partir del AEP conjunto, sabemos que la probabilidad de que no exista un X típico conjunto llega a 0 a medida que n crece. Podemos limitar esta probabilidad de error a . ${\displaystyle \varepsilon }$
• También 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 caso de que el mensaje i sea conjuntamente típico de 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 cuando se llega al infinito, si es 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 rendimiento es mejor que el promedio y, por lo tanto, satisface nuestra necesidad de una probabilidad de error arbitrariamente baja en la comunicación a través del canal ruidoso.

Conversación débil para canales discretos sin memoria

Supongamos un código de palabras clave. Sea W uniformemente dibujado sobre este conjunto como índice. Sean y las palabras en código 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})}$Usar 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 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 ese . A medida que la longitud del bloque llega 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)}}$

Conversación fuerte para canales discretos sin memoria

Un fuerte teorema inverso, 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 el recíproco débil establece que la probabilidad de error está acotado desde cero cuando llega al infinito, el recíproco fuerte establece que el error llega a 1. Por lo tanto, existe un umbral agudo entre una comunicación perfectamente confiable y una comunicación completamente no confiable. ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle C}$

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

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 está 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, ¿dónde está la capacidad del iésimo canal ? ${\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$ ${\displaystyle C_{i}}$

Esquema de la prueba

La demostración se desarrolla casi de la misma manera que la del teorema de codificación de canales. La viabilidad se deriva de la codificación aleatoria en la que cada símbolo se elige aleatoriamente de la capacidad de distribución para ese canal en particular. Los argumentos de tipicidad utilizan la definición de conjuntos típicos para fuentes no estacionarias definidas en el artículo sobre la propiedad de equipartición asintótica .

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

Ver también

• Propiedad de equipartición asintótica (AEP)
• La desigualdad de Fano
• Teoría de la distorsión de la tasa
• Teorema de codificación fuente de Shannon
• Teorema de Shannon-Hartley
• código turbo

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) . Cartas de comunicaciones del IEEE . 5 (2): 58–60. doi : 10.1109/4234.905935. S2CID  7381972.
2. Para obtener una descripción de la función "sup", consulte Supremum
3. Gallager, Robert (1968). Teoría de la información y comunicación confiable . Wiley. ISBN 0-471-29048-3.

Referencias

• Aazhang, B. (2004). "Teorema de codificación de canales ruidosos 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 . Prensa del MIT. 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 IRE de Teoría de la Información . 4 (4): 2–22. Código bibliográfico : 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. Prensa de la Universidad de Cambridge. ISBN 0-521-64298-1. [Gratis en línea]
• Shannon, CE (1948). "Una teoría matemática de la comunicación". Revista técnica del sistema Bell . 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 fortuitos". Illinois J. Matemáticas . 1 (4): 591–606. doi : 10.1215/ijm/1255380682 .