Glosario (sp)‎ > ‎

Teoremas fundamentales de Shannon || Shannon's fundamental theorems

Artículo
 
 Editor
Díaz Nafría, José María  jnafria@uax.es
 Contribuciones incorporadas
Díaz (09/01/09)
 Ámbito de uso
TMC, TIC, codificación
 Tipo
teorema
 Francés
Théorème fondamental de Shannon
 Alemán Shannon-Grundsatz
 

Contenidos

  1. Teorema fundamental para un canal sin ruido
  2. Teorema fundamental para un canal discreto con ruido
  3. Complementariedad de ambos teoremas

1. 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. 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í 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.

3)   Codificación estadística, en el sentido apuntado por la TMC que considera las emisiones de la fuente como procesos ergódigos y estacionarios.

 

2. 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-.

3. 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 digitos 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, July, October.
  • 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.
Entradas
Nueva entrada. Cuando se introduzca una nueva entrada copiar este párrafo y las siguientes líneas y pegarlas al final de la columna. A continuación, borrar el párrafo azul superior y sustituir los campos 'nombre', 'fecha' y 'texto'.
nombre (dd/mm/aaaa)
 
[Texto de entrada] 



Entradas incorporadas
Díaz Nafría (09/01/2009)
 
[Corresponde con la primera versión del artículo, ahora recogido en la columna de la izquierda.]
 

Comments