Pages

jueves, 14 de octubre de 2010

Shannon y la cuantificación de la información en relación con los archivos zip, mp3 y los emoticones

Cuantificación de la Información
 
 Shannon define la cantidad de información producida por una fuente - por ejemplo, la cantidad en un mensaje - por una fórmula similar a la ecuación que define la entropía termodinámica en la física. En sus términos más básicos, la entropía de información de Shannon es el número de dígitos binarios necesarios para codificar un mensaje. Hoy eso suena como una forma sencilla, incluso obvia para definir la cantidad de información es en un mensaje.  En 1948, en los albores de la era de la información, la digitalización de la información de cualquier tipo era un paso revolucionario. Su papel puede haber sido el primero en utilizar la palabra "poco", abreviatura de dígito binario.
Así como la definición de la información, Shannon analizaron la posibilidad de enviar información a través de un canal de comunicaciones. Él encontró que un canal tenía una velocidad máxima de transmisión seguro de que no podía ser superado. Hoy llamamos a que el ancho de banda del canal.Shannon demostró matemáticamente que, incluso en un canal ruidoso, con un ancho de banda bajo, esencialmente perfecto, la comunicación libre de errores se podría lograr mantener la tasa de transmisión dentro del ancho de banda del canal, y mediante el uso de corrección de errores regímenes: la transmisión de bits adicionales que permitan a la datos que se extraen de la señal de ruido-montado.
 Hoy todo de los módems de CDs de música se basan en la corrección de errores para su funcionamiento. Un logro importante de científicos de la información cuántica, ha sido el desarrollo de técnicas para corregir errores introducidos en la información cuántica y para determinar hasta qué punto se puede hacer con un canal de comunicación cuántica ruidosos o con bits cuánticos entrelazados (qubits), cuyo enredo ha sido parcialmente degradadas por el ruido.

También demostró que el tamaño mínimo al que se puede reducir un fichero de datos es igual a su incertidumbre o entropía y mostró la manera de calcular esta entropía en casos sencillos. Uno de los algoritmos de compresión más conocido es el llamado de Lempel-Ziv (LZ), desarrollado por Abraham Lempel and Jacob Ziv. El programa compress del sistema operativo UNIX y todos los programas que generan ficheros .arj, .zip o .gif en Windows utilizan variantes suyas. Lo que hace el algoritmo es aprovechar de forma bastante simple las repeticiones de ciertas “frases” que aparecen en una cadena de bit, es decir, en una cadena de dígitos 0 o 1. Para ello se fragmenta primero la cadena de modo que no aparezca la misma frase dos veces. Esto se consigue colocando comas de forma sucesiva: se coloca una coma después del primer dígito; la siguiente se coloca de modo que el fragmento entre comas resultante sea el más corto posible que no haya aparecido antes.

Por ejemplo, en la cadena de bit:
1011100010101010100

La fragmentación proporcionará:
1,0,11,10,00,101,01,010,100

Se puede observar que cada fragmento es siempre la concatenación de un fragmento aparecido con anterioridad y de un bit 0 o 1. Los llamaremos fragmento prefijo y bit adicional, respectivamente.
Por ejemplo, el tercer fragmento, 11, es el primero seguido de un 1; el sexto fragmento, 101, es el cuarto seguido de un 1; y así sucesivamente. Podemos ahora numerar los fragmentos y sustituir cada uno de ellos por el número del prefijo y por el bit adicional. El 0 indicará por convención la falta de prefijo o “prefijo vacío”. En nuestro ejemplo:
(0,1),(0,0),(1,1),(1,0),(2,0),(4,1),(2,1),(7,0),(4,0) Finalmente se representan en binario los números que indican el prefijo para obtener una nueva cadena de bit. Veamos cómo se realiza este paso en nuestro ejemplo. Como hemos utilizado siete prefijos, se necesitan tres bit para representar cada uno de ellos:
(000,1),(000,0),(001,1),(001,0),(010,0),(100,1),(010,1), (111,0),(100,0)
Ahora se pueden quitar los paréntesis y las comas
y obtener así la cadena de bit comprimida:
000100000011001001001001010111101000.