Teorema de codificación de canales ruidosos

En teoría de la información, el teorema de codificación del canal ruidoso (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 sin errores hasta una velocidad 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 La teoría matemática de la comunicación (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 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 y la información transmitida a un ritmo R, entonces si ${\displaystyle R:$ 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 tipo por debajo de una tasa de limitación, C.

El contrario también es importante. Si ${\displaystyle R confíaC}$, una probabilidad arbitrariamente pequeña de error no es alcanzable. 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 forma fiable a través de un canal a tasas más allá de la capacidad del canal. El teorema no aborda la rara situación en la que la tasa y la capacidad son iguales.

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

Esquemas simples como "enviar el mensaje 3 veces y utilizar 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 informática 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).

Declaración matemática

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

${\begin{\begin{}{\begin{\i}}{\begin{\i}{\i} {\fnMissssage}} {\fn}}}} {\fncip}}} {\fncipi}}}{\m\fnMissstri}}}} {\fnMisssssss}}}}}} {\f}}}}}}}}}}}} {\b}} {\f}}}}}}}}}} {\b}}}}} {\b}}}}} {\b}}} {\b}}}}}}}}}} {\b} {\b}}}}} {\b}}}}}}}}}}} {\b\b}}}}}}}}}}}}}}}}}}}}}}\b}}}}}\b\b}}}\b\b}}}}\b\b}}}}}}}} }\hline {\text{Encoder}\f_{n}\\hline {\fnK}{\xrightarrow[{\mathrm] {Encoded \atop sequence}} {X^{n}} {\begin{array}{Principio}\hline {\text{Channel}}\\p(y sometidax)\\\\\hline \end{array}{\xrightarrow[{\mathrm}}}\ {Recibido \atop sequence} {}} {\begin{array}{ }\hline {\text{Decoder}\g_{n}\\\\hline \end{array}{\xrightarrow[{\mathrm] Estimated \atop message} {\hat {W}}} {\f} {\f}} {\f}} {\f}} {\f}}}} {\f}} {\f}}} {\f}}}} {\f}}}}$

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 ¿Por qué? {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 ${\displaystyle I(X;Y)}$ como

${\displaystyle \ C=\sup Yo...$

tiene la siguiente propiedad. Para cualquier ${\displaystyle \epsilon }$ y ${\displaystyle R:$, por lo suficientemente grande ${\displaystyle N}$, existe un código de longitud ${\displaystyle N}$ y tasa ${\displaystyle \geq R}$ y un algoritmo de decodificación, tal que la probabilidad máxima de error de bloque es ${\displaystyle \leq \epsilon }$.

2. Si una probabilidad de error de bits ${\displaystyle P_{b}$ es aceptable, tasas hasta ${\displaystyle R(p_{b}}$ son alcanzables, donde

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

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

${\displaystyle H_{2}(p_{b}=-\left[p_{b}\log ¿Por qué?$

3. Para cualquier ${\displaystyle P_{b}$, tasas superiores a ${\displaystyle R(p_{b}}$ no son alcanzables.

(MacKay (2003), p. 162; cf. Gallager (1968), cap.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.

Alcanzabilidad de 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). Se puede encontrar otro estilo en los 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 en cualquier dato. velocidad por debajo de la capacidad del canal.

Por un argumento relacionado con la AEP, dado un canal, longitud ${\displaystyle n}$ cadenas de símbolos fuente ${\displaystyle ¿Qué?$, y longitud ${\displaystyle n}$ cadenas de salidas de canales ${\displaystyle Y...$, podemos definir un conjunto típico by the following:

${\displaystyle A_{\varepsilon } {n)}=\{(x^{n},y^{n}\in {\mathcal {X}} {\n}\times {\mathcal {}}} {\n}} {\n} {\n}}} {\n}}}}\n}}}\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}\leq 2^{-n(H(Y)-\varepsilon)}$

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

Decimos que dos secuencias ${\displaystyle {X_{1} {}}}$ y ${\displaystyle Y...$ son típico si se encuentran en el conjunto común típico definido anteriormente.

Pasos

1. Al estilo del argumento de codificación al azar, generamos aleatoriamente ${\displaystyle 2^{nR}$ codewords de longitud n de una distribución de probabilidad Q.
2. Este código se revela al remitente y receptor. También se supone que uno conoce la matriz de transición ${\displaystyle p(y WordPressx)}$ para el canal que se utiliza.
3. Un mensaje W es elegido según la distribución uniforme en el conjunto de palabras clave. Eso es, ${\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots2^{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} ¿Por qué?$
6. Enviando estas palabras clave a través del canal, recibimos ${\displaystyle Y...$, y decodificar a alguna secuencia de origen si existe exactamente 1 palabra clave que es comúnmente típica con Y. Si no hay códigos comunes, o si hay más de uno, se declara un error. Un error también ocurre si una palabra clave decodificada no coincide con la palabra clave original. Esto se llama típico juego.

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

1. En primer lugar, el error puede ocurrir si no se produce conjuntamente X secuencias se encuentran para una secuencia Y recibida
2. Segundo, el error puede ocurrir si un error es incorrecto X secuencia es comúnmente típica con una secuencia Y recibida.

• Por la aleatoriedad de la construcción de códigos, podemos asumir que la probabilidad promedio de error promediado sobre todos los códigos no depende del índice enviado. Así, sin pérdida de generalidad, podemos asumir W = 1.
• Desde la articulación AEP, sabemos que la probabilidad de que no exista una X comúnmente típica va a 0 a medida que crece grande. Podemos vincular esta probabilidad de error por ${\displaystyle \varepsilon }$.
• También desde el AEP conjunto, sabemos la probabilidad de que un particular ${\displaystyle X_{1}{n}(i)}$ y el ${\displaystyle Y...$ resultantes W = 1 son comunes ${\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon)}$.

Define: ${\displaystyle ¿Qué?$

como el evento que mensaje es comúnmente típico con la secuencia recibida cuando el mensaje 1 es enviado.

${\displaystyle {\begin{aligned}P({\text{error}}} {}=P({\text{error} sobrevivirW=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-3\vaend]$

Podemos observarlo como ${\displaystyle n}$ va al infinito, si ${\displaystyle R realizadasI(X;Y)}$ para el canal, la probabilidad de error irá a 0.

Por último, dado que se ha demostrado 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

Suponga un código ${\displaystyle 2^{nR}$ Palabras clave. Deje que W sea dibujado uniformemente sobre este conjunto como un índice. Vamos. ${\displaystyle X^{n}$ y ${\displaystyle Y.$ sean las palabras clave transmitidas y recibidas, respectivamente.

1. ${\displaystyle nR=H(W)=H(W habitY^{n})+I(W;Y^{n}$ usando identidades que implican entropía e información mutua
2. ${\displaystyle \leq H(W habitY^{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}}$ por el uso de la desigualdad de Fano
4. ${\displaystyle \leq 1+P_{(n)}nR+nC}$ por el hecho de que la capacidad se maximice la información mutua.

El resultado de estas medidas es que ${\displaystyle P_{e} { n)}\geq 1-{\frac {1}{nR}-{\frac} {C} {R}}$. Como la longitud del bloque ${\displaystyle n}$ va al infinito, obtenemos ${\displaystyle P_{e} { n)}$ está atado de 0 si R es mayor que C - podemos obtener tasas arbitrariamente bajas de error sólo si R es menos que C.

Conversación fuerte para canales discretos sin memoria

Un fuerte teorema inverso, demostrado por Wolfowitz en 1957, establece que,

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

para una constante positiva finita ${\displaystyle A}$. Mientras que el débil revés afirma que la probabilidad de error está atada de cero como ${\displaystyle n}$ va a la infinidad, el fuerte revés afirma que el error va a 1. Así, ${\displaystyle C}$ es un umbral afilado entre comunicación perfectamente fiable y completamente inconfiable.

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

Asumimos 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 _{(X_{1}},p^{(X_{2}}}},...}{\frac {1}{n}}\sum} ¿Por qué?$

El máximo se alcanza en la capacidad de conseguir distribuciones para cada canal respectivo. Eso es, ${\displaystyle C=\lim \inf {\frac {1}{n}\sum ¿Qué?$Donde ${\displaystyle C_{i}$ es la capacidad del iT canal.

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 ${\displaystyle {\frac {\fn} {\fnK}}}}\sum} ¿Qué?$ no converge.