Teoremas fundamentales de Shannon

JDíaz (2010). Teoremas fundamentales de Shannon. GlossariumBITri, 1(1): 1084.

También disponible como: Shannon's fundamental theorems

Colección	GlossariumBITri
Autor	José María Díaz Nafría
Editor	José María Díaz Nafría
Año	2010
Vol. (núm.)	1(1)
ID	◀ 1084 ▶
Tipo de objeto	Teorema
Dominio	06, MTC
en	Shannon's fundamental theorems
fr	Théorèmes fondamentaux de Shannon
de	Shannon-Grundsätze

Los teoremas fundamentales de Shannon establecen los límites teóricos de la transmisión de información: por un lado, indican la posibilidad de codificar la fuente —caracterizada por su entropía $H$— para transmitir información con máxima eficiencia a través de un canal —caracterizado por su capacidad de canal $C$—; por otro, indican que para transmitirlos con pocos errores la capacidad del canal debe ser suficiente como para añadir redundancia que permita corregir errores.

Teorema fundamental para un canal sin ruido

"Sea una fuente con entropía

$H$

(bits por símbolo) y un canal con capacidad

$C$

(bits por segundo). Entonces es posible codificar la salida de la fuente de tal modo que se pueda transmitir a un régimen de

$C/H-ϵ$

símbolos por segundo sobre el canal, donde

$ϵ$

es tan pequeño como se quiera. No es posible transmitir a un régimen promedio mayor que

$C/H$

." (Shannon, 1948: 16)

Con este teorema Shannon prueba la existencia de un límite a la eficiencia de lo que se ha denominado codificación de fuente (codificador). Si puede determinarse la entropía de una fuente caracterizada por la emisión de un número finito de símbolos, entonces sabemos que $H$ (en bits/símbolo) equivale al mínimo número de dígitos binarios que podrían emplearse para su codificación, traduciéndose todo acercamiento a dicho límite en un aumento de la complejidad (en coste operativo y circuital). Al igual que en otros resultados fundamentales de la TMC, se trata de una conclusión no constructiva, dejando abierto el problema del diseño de la codificación (C.E. Shannon).

En la práctica, la codificación de fuente no se ciñe solo al plano estadístico al que se refiere Shannon (Sklar 2001). Las técnicas más sofisticadas de codificación de fuente consisten en una combinación de:

1. Codificación predictiva: solo se transmite aquello que no puede predecirse a partir de las emisiones previas, logrando óptimos resultados cuando se analiza en profundidad las peculiaridades de la fuente y su contexto pragmático (por ejemplo, para la reproducción de una interpretación de piano solo se registran las pulsaciones sobre el teclado).
2. Codificación transformacional (especialmente aplicable a señales destinadas a órganos sensoriales): a las señales a transmitir se les aplica una transformación lineal (reversible) por medio de la cual se pueden distinguir rangos de diferente sensibilidad, permitiendo así prescindir de datos imperceptibles o que quedan por debajo de ciertos umbrales de calidad (operación que entraña una pérdida irreversible de datos —no necesariamente información, si es que tales datos de ningún modo fueran a informar al destino—). En esta codificación la eficiencia se logra mediante un análisis en profundidad de la percepción sensorial.
3. Codificación estadística: en el sentido apuntado por la TMC, que considera las emisiones de la fuente como procesos ergódicos y estacionarios.

Teorema fundamental para un canal discreto con ruido

"Sea un canal discreto con capacidad

$C$

(bits por segundo) y una fuente discreta con entropía

$H$

(bits por segundo). Si

$H\le C$

entonces hay un sistema de codificación que permitiría transmitir la salida de la fuente sobre el canal con una tasa de errores tan pequeña como se desee (o una equivocación arbitrariamente pequeña). Si

$H>C$

es posible codificar la fuente de modo que la equivocación sea menor que

$H-C+ϵ$

, donde

$ϵ$

es tan pequeño como se quiera. No hay ningún método de codificación que proporcione una equivocación menor que

$H-C$

." (Shannon, 1948: 22)

En cuanto a que aquí la fuente se caracteriza por el régimen o velocidad de transmisión de información —según la definición shannoniana de entropía—, nos advierte este teorema que para su transmisión debe emplearse un canal de capacidad $C$ mayor que $H$. En vano podríamos intentar transmitirlo mediante un canal de menor capacidad, ya que el exceso de entropía de la fuente respecto a la capacidad se traduciría en un aumento de la frecuencia de errores de recepción. Por otra parte, la reducción de la distancia respecto al umbral ($C\approx H$) se traduce en un aumento de la complejidad (operacional y/o circuital).

¿En qué puede emplearse la distancia existente entre la entropía de la fuente $H$ y la capacidad del canal usado $C$? Puede introducirse redundancia que sirva al receptor para la identificación y corrección de errores. A la codificación empleada para esta función se le denomina codificación de canal (codificador). Existen diversas técnicas para introducir dicha redundancia, que se dividen en códigos de bloque y convolucionales. En los primeros se usan bloques de datos consecutivos para la determinación de la redundancia añadida; en los convolucionales se utilizan máquinas de estados cuya salida depende del estado y de los datos de entrada. La corrección de errores consiste en una búsqueda de los bloques válidos más parecidos —para el primer tipo— o de las secuencias de código más verosímiles —en los convolucionales—.

Complementariedad de ambos teoremas

Existe en definitiva una cierta complementariedad práctica entre dichos teoremas: el primero nos indica hasta dónde podemos comprimir el código para expresar los mensajes de la fuente (eliminando al máximo su redundancia); el segundo nos señala la redundancia que puede usar el sistema para que el receptor pueda corregir errores.

A grandes rasgos, la codificación de fuente persigue la igualación de dígitos binarios con bits, maximizando la entropía y prescindiendo de todo aquello que no sea entrópico e inútil para la decodificación, mientras que la codificación de canal añade dígitos no entrópicos que puede reconocer el receptor para poder eliminar errores de transmisión.

Referencias

• SHANNON, C. E. (1948). “A Mathematical Theory of Communication”. The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656.
• SHANNON, C. y WEAVER, W. (1949). The Mathematical Theory of Communication. Urbana: The University of Illinois Press.
• SKLAR, B. (2001). Digital Communications. Fundamentals and Applications. New Jersey: Prentice Hall.