En teoría de la información , el teorema de codificación de canal ruidoso (a veces el teorema de Shannon o el límite de Shannon ), establece que para cualquier grado dado de contaminación por ruido de un canal de comunicación , es posible 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 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 de transmisión de datos aleatorios, 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 .
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 importancia fundamental para el campo moderno de la teoría de la información . Shannon solo dio un resumen de la prueba. La primera prueba rigurosa para el caso discreto se debe a Amiel Feinstein [1] en 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 siexisten códigos que permiten reducir arbitrariamente la probabilidad de error en el receptor. Esto significa que, en teoría, es posible a la información de transmisión casi sin error en todo caso por debajo de una limitación de velocidad, 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 tanto, no se puede garantizar que la información se transmita de forma fiable 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 la velocidad y la capacidad son iguales.
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 .
Los 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 ineficaces de corrección de errores, incapaces de garantizar asintóticamente que un bloque de datos se pueda comunicar 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 a alcanzar el límite teórico de Shannon, pero a un costo de alta complejidad computacional. Usando estos códigos altamente eficientes y con la potencia informática 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 alcanzar dentro de 0.0045 dB del límite de Shannon (para canales binarios de ruido blanco gaussiano aditivo (AWGN), con longitudes de bloque muy largas). [2]
Declaración matemática
El modelo matemático básico para un sistema de comunicación es el siguiente:
Un mensaje W se transmite a través de un canal ruidoso utilizando funciones de codificación y decodificación. Un codificador mapea 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 alimenta a un decodificador que mapea la secuencia en una estimación del mensaje. En esta configuración, la probabilidad de error se define como:
Teorema (Shannon, 1948):
- 1. Para cada canal discreto sin memoria, la capacidad del canal se define en términos de información mutua ,
- tiene la siguiente propiedad. Para cualquier y , para lo suficientemente grande , existe un código de longitud y tasa y un algoritmo de decodificación, tal que la probabilidad máxima de error de bloque es .
- 2. Si existe una probabilidad de error de bit es aceptable, tarifas de hasta son alcanzables, donde
- y es la función de entropía binaria
- 3. Para cualquier , tasas mayores que 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 los otros resultados principales en la teoría de la información, la prueba del teorema de codificación de canal ruidoso incluye un resultado de alcanzabilidad y un resultado inverso coincidente. Estos dos componentes sirven para acotar, en este caso, el conjunto de velocidades posibles a las que uno puede comunicarse a través de un canal ruidoso, y la correspondencia sirve para mostrar que estos límites son límites estrictos.
Los siguientes bosquejos son solo un conjunto de muchos estilos diferentes disponibles para su estudio en textos de teoría de la información.
Alcanzabilidad para canales discretos sin memoria
Esta prueba particular de alcanzabilidad sigue el estilo de las pruebas que hacen uso de la propiedad de equipartición asintótica (AEP). Otro estilo se puede encontrar en los textos de teoría de la información utilizando 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 por debajo capacidad del canal .
Por un argumento relacionado con AEP, dado un canal, la longitud cadenas de símbolos fuente y longitud cadenas de salidas de canal , podemos definir un conjunto típico conjunto de la siguiente manera:
Decimos que dos secuencias y son típicos en conjunto si se encuentran en el conjunto típico en conjunto definido anteriormente.
Pasos
- En el estilo del argumento de codificación aleatoria, generamos aleatoriamente palabras de código de longitud n de una distribución de probabilidad Q.
- Este código se revela al remitente y al receptor. También se asume que uno conoce la matriz de transición para el canal que se está utilizando.
- Se elige un mensaje W de acuerdo con la distribución uniforme en el conjunto de palabras de código. Es decir,.
- El mensaje W se envía a través del canal.
- El receptor recibe una secuencia de acuerdo con
- Al enviar estas palabras en clave a través del canal, recibimos y decodificar a alguna secuencia fuente si existe exactamente 1 palabra de código que es común en Y. Si no hay palabras de 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 de código decodificada no coincide con la palabra de código original. Esto se denomina decodificación de conjuntos típica .
La probabilidad de error de este esquema se divide en dos partes:
- Primero, puede ocurrir un error si no se encuentran secuencias X típicas conjuntas para una secuencia Y recibida
- En segundo lugar, puede ocurrir un error si una secuencia X incorrecta es común a una secuencia Y recibida.
- Por la aleatoriedad de la construcción del código, podemos suponer que la probabilidad promedio de error promediada sobre todos los códigos no depende del índice enviado. Por tanto, sin pérdida de generalidad, podemos asumir W = 1.
- A partir de la AEP conjunta, sabemos que la probabilidad de que no exista una X típica conjunta va a 0 a medida que n crece. Podemos limitar esta probabilidad de error por.
- También a partir del AEP conjunto, conocemos la probabilidad de que un determinado y el resultantes de W = 1 son conjuntamente típicos es.
Definir:
como el caso de que el mensaje i sea común junto con la secuencia recibida cuando se envía el mensaje 1.
Podemos observar que como va al infinito, si para el canal, la probabilidad de error pasará a 0.
Finalmente, dado que el libro de códigos promedio se muestra como "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 de palabras en clave. Sea W uniformemente dibujado sobre este conjunto como un índice. Dejar y ser las palabras de código transmitidas y las palabras de código recibidas, respectivamente.
- usando identidades que involucran entropía e información mutua
- ya que X es una función de W
- por el uso de la Desigualdad de Fano
- por el hecho de que se maximiza la capacidad de información mutua.
El resultado de estos pasos es que . Como la longitud del bloque va al infinito, obtenemos está acotado de 0 si R es mayor que C; podemos obtener tasas de error arbitrariamente bajas solo si R es menor que C.
Conversión fuerte para canales discretos sin memoria
Un fuerte teorema inverso, probado por Wolfowitz en 1957, [4] establece que,
para alguna constante positiva finita . Mientras que el inverso débil establece que la probabilidad de error se limita a cero como va al infinito, el recíproco fuerte establece que el error va a 1. Por lo tanto, es un umbral agudo entre una comunicación perfectamente confiable y una comunicación completamente no confiable.
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 viene dada por
El máximo se alcanza a la capacidad logrando distribuciones para cada canal respectivo. Es decir, dónde es la capacidad del i- ésimo canal.
Esquema de la prueba
La demostración se ejecuta casi de la misma manera que la del teorema de codificación de canales. La posibilidad de lograrlo se deriva de la codificación aleatoria con cada símbolo elegido aleatoriamente de la capacidad que logra la 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 de propiedad de equipartición asintótica .
El tecnicismo de lim inf entra en juego cuando no converge.
Ver también
Notas
- ^ "Un nuevo teorema básico de la teoría de la información". Feinstein, Amiel. 1954. Código bibliográfico : 1955PhDT ........ 12F . hdl : 1721,1 / 4798 . Cite journal requiere
|journal=
( ayuda )CS1 maint: otros ( enlace ) - ^ Sae-Young Chung , G. David Forney, Jr. , Thomas J. Richardson y Rüdiger Urbanke , " 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 ", IEEE Communications Letters , 5: 58-60, febrero de 2001. ISSN 1089-7798
- ^ Para obtener una descripción de la función "sup", consulte Supremum
- ^ Robert Gallager. Teoría de la información y comunicación confiable. Nueva York: John Wiley & Sons , 1968. ISBN 0-471-29048-3
Referencias
- Cover TM , Thomas JA, Elementos de la teoría de la información , John Wiley & Sons , 1991. ISBN 0-471-06259-6
- Fano, RA , Transmisión de información; una teoría estadística de las comunicaciones , MIT Press , 1961. ISBN 0-262-06001-9
- Feinstein, Amiel , "Un nuevo teorema básico de la teoría de la información", IEEE Transactions on Information Theory , 4 (4): 2-22, 1954.
- MacKay, David JC , teoría de la información, inferencia y algoritmos de aprendizaje , Cambridge University Press , 2003. ISBN 0-521-64298-1 [gratis en línea]
- Shannon, CE , una teoría matemática de la comunicación . The Bell System Technical Journal 27,3: 379–423, 1948.
- Shannon, CE , A Mathematical Theory of Communication Urbana, IL: University of Illinois Press, 1948 (reimpreso en 1998).
- Wolfowitz, J. , " La codificación de mensajes sujetos a errores fortuitos ", Illinois J. Math. , 1: 591–606, 1957.
enlaces externos
- Sobre Shannon y la ley de Shannon
- Teorema de codificación de canal ruidoso de Shannon