Teoremas fundamentales de Shannon

Colección
glossariumBITri
Curador
José María Díaz Nafría
Autor(es)
José María Díaz Nafría
Fecha de publicación
2010
Identificador
1: 87
Tipo de artículo
teorema

José María Díaz Nafría (2010). Teoremas fundamentales de Shannon. glossariumBITri, 1: 87.

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 Teoría Matemática de la Comunicación (TMC), se trata de una conclusión no constructiva, dejando abierto el problema del diseño de la codificación (v. 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. Las técnicas más sofisticadas de codificación de fuente consisten en una combinación de:

• 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).
• 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í el 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.
• Codificación estadística, en el sentido apuntado por la TMC que considera las emisiones de la fuente como procesos ergódigos 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 ≤ 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 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 ≈ H) se traduce en aumento de la complejidad (operacional y/o circuital).

¿En que 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 de 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 donde 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

Las siguientes obras ofrecen información complementaria acerca de lo que sucintamente se ha considerado en este artículo:

• SHANNON, C. y WEAVER, W. (1949). The mathematical theory of communication. Urbana: The University of Illinois Press.
• SKLAR, Bernard (2001). Digital Communications. Fundamentals and Applications. New Jersey: Prentice Hall.