Teoría de la información La teoría de la información, también conocida como teoría matemática de la comunicación (mathematical theory of communication) o teoría matemática de la información, es una propuesta teórica presentada por Claude E. Shannon y Warren Weaver a ﬁnales de la década de los años 1940. Esta teoría está relacionada con las leyes matemáticas que rigen la transmisión y el procesamiento de la información y se ocupa de la medición de la información y de la representación de la misma, así como también de la capacidad de los sistemas de comunicación para transmitir y procesar información.[1] La teoría de la información es una rama de la teoría matemática y de las ciencias de la computación que estudia la información y todo lo relacionado con ella: canales, compresión de datos y criptografía, entre otros. 1 incluyendo la televisión y los impulsos eléctricos que se transmiten en las computadoras y en la grabación óptica de datos e imágenes. La idea es garantizar que el transporte masivo de datos no sea en modo alguno una merma de la calidad, incluso si los datos se comprimen de alguna manera. Idealmente, los datos se pueden restaurar a su forma original al llegar a su destino. En algunos casos, sin embargo, el objetivo es permitir que los datos de alguna forma se conviertan para la transmisión en masa, se reciban en el punto de destino y sean convertidos fácilmente a su formato original, sin perder ninguna de la información transmitida.[2] Historia 2 Desarrollo de la teoría La teoría de la información surgió a ﬁnales de la Segunda Guerra Mundial, en los años cuarenta. Fue iniciada por Claude E. Shannon a través de un artículo publicado en el Bell System Technical Journal en 1948, titulado Una teoría matemática de la comunicación (texto completo en inglés). En esta época se buscaba utilizar de manera más eﬁciente los canales de comunicación, enviando una cantidad de información por un determinado canal y midiendo su capacidad; se buscaba la transmisión óptima de los mensajes. Esta teoría es el resultado de trabajos comenzados en la década 1910 por Andrei A. Markovi, a quien le siguió Ralp V. L. Hartley en 1927, quien fue el precursor del lenguaje binario. A su vez, Alan Turing en 1936, realizó el esquema de una máquina capaz de tratar información con emisión de símbolos, y ﬁnalmente Claude Elwood Shannon, matemático, ingeniero electrónico y criptógrafo estadounidense, conocido como “el padre de la teoría de la información”, junto a Warren Weaver, contribuyó en la culminación y el asentamiento de la Teoría Matemática de la Comunicación de 1949 –que hoy es mundialmente conocida por todos como la Teoría de la Información-. Weaver consiguió darle un alcance superior al planteamiento inicial, creando un modelo simple y lineal: Fuente/codiﬁcador/mensaje canal/decodiﬁcador/destino. La necesidad de una base teórica para la tecnología de la comunicación surgió del aumento de la complejidad y de la masiﬁcación de las vías de comunicación, tales como el teléfono, las redes de teletipo y los sistemas de comunicación por radio. La teoría de la información también abarca todas las restantes formas de transmisión y almacenamiento de información, El modelo propuesto por Shannon es un sistema general de la comunicación que parte de una fuente de información desde la cual, a través de un transmisor, se emite una señal, la cual viaja por un canal, pero a lo largo de su viaje puede ser interferida por algún ruido. La señal sale del canal, llega a un receptor que decodiﬁca la información convirtiéndola posteriormente en mensaje que pasa a un destinatario. Con el modelo de la teoría de la información se trata de llegar a determinar la forma más económica, rápida y segura de codiﬁcar un mensaje, sin que la presencia de algún ruido complique su transmisión. Para esto, el destinatario debe comprender la señal correctamente; el problema es que aunque exista un mismo código de por medio, esto no signiﬁca que el destinatario va a captar el signiﬁcado que el emisor le quiso dar al mensaje. La codiﬁcación puede referirse tanto a la transformación de voz o imagen en señales eléctricas o electromagnéticas, como al cifrado de mensajes para asegurar su privacidad. Un concepto fundamental en la teoría de la información es que la cantidad de información contenida en un mensaje es un valor matemático bien deﬁnido y medible. El término cantidad no se reﬁere a la cuantía de datos, sino a la probabilidad de que un mensaje, dentro de un conjunto de mensajes posibles, sea recibido. En lo que se reﬁere a la cantidad de información, el valor más alto se le asigna al mensaje que menos probabilidades tiene de ser recibido. Si se sabe con certeza que un mensaje va a ser recibido, su cantidad de información es cero.[3] 1 2 3 5 ELEMENTOS DE LA TEORÍA Finalidad mentales de cada país que forma parte de Internet, lo que proporciona un servicio prácticamente gratuito. A principios de 1994 comenzó a darse un crecimiento explosivo de las compañías con propósitos comerciales en Internet, dando así origen a una nueva etapa en el desarrollo de la red. Descrito a grandes rasgos, TCP/IP mete en paquetes la información que se quiere enviar y la saca de los paquetes para utilizarla cuando se recibe. Estos paquetes pueden compararse con sobres de correo; TCP/IP guarda la información, cierra el sobre y en la parte exterior pone la dirección a la cual va dirigida y la dirección de quien la envía. Mediante este sistema, los paquetes viajan a través de la red hasta que llegan al destino deseado; una vez ahí, la computadora de destino quita el sobre y procesa la información; en caso de ser necesario envía una respuesta a la computadora de origen usando el mismo procedimiento. Cada máquina que está conectada a Internet tiene una dirección única; esto hace que la información que se envía no equivoque el destino. Existen dos formas de dar direcciones, con letras o con números. Realmente, las computadoras utilizan las direcciones numéricas para mandar paquetes de información, pero las direcciones con letras fueron implementadas para facilitar su manejo a los seres humanos. Una dirección con letras consta de dos a cuatro partes. Una dirección numérica está compuesta por cuatro partes. Cada una de estas partes está dividida por puntos. Otro aspecto importante dentro de esta teoría es la resistencia a la distorsión que provoca el ruido, la facilidad de codiﬁcación y descodiﬁcación, así como la velocidad de transmisión. Es por esto que se dice que el mensaje tiene muchos sentidos, y el destinatario extrae el sentido que debe atribuirle al mensaje, siempre y cuando haya un mismo código en común. La teoría de la información tiene ciertas limitaciones, como lo es la acepción del concepto del código. El signiﬁcado que se quiere transmitir no cuenta tanto como el número de alternativas necesario para deﬁnir el hecho sin ambigüedad. Si la selección del mensaje se plantea únicamente entre dos alternativas diferentes, la teoría de Shannon postula arbitrariamente que el valor de la información es uno. Esta unidad de información recibe el nombre de bit. Para que el valor de la información sea un bit, todas las alternativas deben ser igual de probables y estar disponibles. Es importante saber si la fuente de información tiene el mismo grado de libertad para elegir cualquier posibilidad o si se halla bajo alguna inﬂuencia que la induce a una cierta elección. La cantidad de información crece cuando todas las alternativas son igual de probables o cuanto mayor sea el número de alternativas. Pero en la práctica comunicativa real no todas las alternativas son igualmente probables, lo cual constituye un tipo de proceso estocástico denominado Markoﬀ. El subtipo de Markoﬀ dice que la cadena Ejemplo: sedet.com.mx 107.248.185.1 de símbolos está conﬁgurada de manera que cualquier seUna de las aplicaciones de la teoría de la información son cuencia de esa cadena es representativa de toda la cadena los archivos ZIP, documentos que se comprimen para su completa. transmisión a través de correo electrónico o como parte de los procedimientos de almacenamiento de datos. La compresión de los datos hace posible completar la transmisión en menos tiempo. En el extremo receptor, un soft4 Teoría aplicada a la tecnología ware se utiliza para la liberación o descompresión del archivo, restaurando los documentos contenidos en el arLa Teoría de la Información se encuentra aún hoy en día chivo ZIP a su formato original. La teoría de la informaen relación con una de las tecnologías en boga, Internet. ción también entra en uso con otros tipos de archivo; por Desde el punto de vista social, Internet representa unos ejemplo, los archivos de audio y vídeo que se reproducen signiﬁcativos beneﬁcios potenciales, ya que ofrece opor- en un reproductor de MP3 se comprimen para una fácil tunidades sin precedentes para dar poder a los individuos descarga y almacenamiento en el dispositivo. Cuando se y conectarlos con fuentes cada vez más ricas de informa- accede a los archivos se amplían para que estén inmediación digital. Internet fue creado a partir de un proyecto tamente disponibles para su uso.[4] del departamento de defensa de los Estados Unidos llamado DARPANET (Defense Advanced Research Project Network) iniciado en 1969 y cuyo propósito principal era 5 Elementos de la teoría la investigación y desarrollo de protocolos de comunicación para redes de área amplia para ligar redes de transmisión de paquetes de diferentes tipos capaces de resistir las 5.1 Fuente condiciones de operación más difíciles, y continuar funcionando aún con la pérdida de una parte de la red (por Una fuente es todo aquello que emite mensajes. Por ejemejemplo en caso de guerra). Estas investigaciones dieron plo, una fuente puede ser una computadora y mensajes como resultado el protocolo TCP/IP (Transmission Con- sus archivos; una fuente puede ser un dispositivo de transtrol Protocol/Internet Protocol), un sistema de comunica- misión de datos y mensajes los datos enviados, etc. Una ciones muy sólido y robusto bajo el cual se integran to- fuente es en sí misma un conjunto ﬁnito de mensajes: todas las redes que conforman lo que se conoce actualmen- dos los posibles mensajes que puede emitir dicha fuente. te como Internet. El enorme crecimiento de Internet se En compresión de datos se tomará como fuente el archivo debe en parte a que es una red basada en fondos guberna- a comprimir y como mensajes los caracteres que confor- 5.5 Información 3 casos, representarse con un código de menor longitud que el mensaje original. Supongamos que a cualquier mensaje S lo codiﬁcamos usando un cierto algoritmo de forma tal que cada S es codiﬁcado en L(S) bits; deﬁnimos entonces la información contenida en el mensaje S como la cantidad mínima de bits necesarios para codiﬁcar un mensaje. 5.5 Información Esquema de la comunicación ideado por Claude E. Shannon. man dicho archivo. 5.2 Tipos de fuente Por la naturaleza generativa de sus mensajes, una fuente puede ser aleatoria o determinista. Por la relación entre los mensajes emitidos, una fuente puede ser estructurada o no estructurada (o caótica). Existen varios tipos de fuente. Para la teoría de la información interesan las fuentes aleatorias y estructuradas. Una fuente es aleatoria cuando no es posible predecir cuál es el próximo mensaje a emitir por la misma. Una fuente es estructurada cuando posee un cierto nivel de redundancia; una fuente no estructurada o de información pura es aquella en que todos los mensajes son absolutamente aleatorios sin relación alguna ni sentido aparente. Este tipo de fuente emite mensajes que no se pueden comprimir; un mensaje, para poder ser comprimido, debe poseer un cierto grado de redundancia; la información pura no puede ser comprimida sin que haya una pérdida de conocimiento sobre el mensaje.[5] La información contenida en un mensaje es proporcional a la cantidad de bits que se requieren como mínimo para representar al mensaje. El concepto de información puede entenderse más fácilmente si consideramos un ejemplo. Supongamos que estamos leyendo un mensaje y hemos leído “cadena de c"; la probabilidad de que el mensaje continúe con “aracteres” es muy alta. Así, cuando efectivamente recibimos a continuación “aracteres” la cantidad de información que nos llegó es muy baja pues estábamos en condiciones de predecir qué era lo que iba a ocurrir. La ocurrencia de mensajes de alta probabilidad de aparición aporta menos información que la ocurrencia de mensajes menos probables. Si luego de “cadena de c” leemos “himichurri” la cantidad de información que estamos recibiendo es mucho mayor. 6 Entropía e información La información es tratada como magnitud física, caracterizando la información de una secuencia de símbolos utilizando la entropía. Se parte de la idea de que los canales no son ideales, aunque muchas veces se idealicen las no linealidades, para estudiar diversos métodos de envío de información o la cantidad de información útil que se pueda enviar a través de un canal. La información necesaria para especiﬁcar un sistema físico tiene que ver con su entropía. En concreto, en ciertas 5.3 Mensaje áreas de la física, extraer información del estado actual de un sistema requiere reducir su entropía, de tal manera que Un mensaje es un conjunto de ceros y unos. Un archivo, la entropía del sistema ( S ) y la cantidad de información un paquete de datos que viaja por una red y cualquier cosa ( I ) extraíble están relacionadas por: que tenga una representación binaria puede considerarse un mensaje. El concepto de mensaje se aplica también a S ≥S−I ≥0 alfabetos de más de dos símbolos, pero debido a que tratamos con información digital nos referiremos casi siempre 6.1 Entropía de una fuente a mensajes binarios. 5.4 Código Un código es un conjunto de unos y ceros que se usan para representar un cierto mensaje de acuerdo a reglas o convenciones preestablecidas. Por ejemplo, al mensaje 0010 lo podemos representar con el código 1101 usando para codiﬁcar la función (NOT). La forma en la cual codiﬁcamos es arbitraria. Un mensaje puede, en algunos De acuerdo a la teoría de la información, el nivel de información de una fuente se puede medir según la entropía de la misma. Los estudios sobre la entropía son de suma importancia en la teoría de la información y se deben principalmente a C. E. Shannon. Existe, a su vez, un gran número de propiedades respecto de la entropía de variables aleatorias debidas a A. Kolmogorov. Dada una fuente F que emite mensajes, resulta frecuente observar que los mensajes emitidos no resulten equiprobables sino 4 7 OTROS ASPECTOS DE LA TEORÍA que tienen una cierta probabilidad de ocurrencia dependiendo del mensaje. Para codiﬁcar los mensajes de una fuente intentaremos pues utilizar menor cantidad de bits para los mensajes más probables y mayor cantidad de bits para los mensajes menos probables, de forma tal que el promedio de bits utilizados para codiﬁcar los mensajes sea menor a la cantidad de bits promedio de los mensajes originales. Esta es la base de la compresión de datos. A este tipo de fuente se la denomina fuente de orden-0, pues la probabilidad de ocurrencia de un mensaje no depende de los mensajes anteriores. A las fuentes de orden superior se las puede representar mediante una fuente de orden-0 utilizando técnicas de modelización apropiadas. Deﬁnimos la probabilidad de ocurrencia de un mensaje en una fuente como la cantidad de apariciones de dicho mensaje dividido entre el total de mensajes. Supongamos que Pi es la probabilidad de ocurrencia del mensaje-i de una fuente, y supongamos que Li es la longitud del código utilizado para representar a dicho mensaje. La longitud promedio de todos los mensajes codiﬁcados de la fuente se puede obtener como: H= ∑n i=0 Pi Li • Promedio ponderado de las longitudes de los códigos de acuerdo a sus probabilidades de ocurrencia, al número H se lo denomina “Entropía de la fuente” y tiene gran importancia. La entropía de la fuente determina el nivel de compresión que podemos obtener como máximo para un conjunto de datos, si consideramos como fuente a un archivo y obtenemos las probabilidades de ocurrencia de cada carácter en el archivo podremos calcular la longitud promedio del archivo comprimido, se demuestra que no es posible comprimir estadísticamente un mensaje/archivo más allá de su entropía. Lo cual implica que considerando únicamente la frecuencia de aparición de cada carácter la entropía de la fuente nos da el límite teórico de compresión, mediante otras técnicas no-estadísticas puede, tal vez, superarse este límite. • El objetivo de la compresión de datos es encontrar los Li que minimizan a H, además los Li se deben determinar en función de los Pi, pues la longitud de los códigos debe depender de la probabilidad de ocurrencia de los mismos (los más ocurrentes queremos codiﬁcarlos en menos bits). Se plantea pues: H= ∑n i=0 Pi f (Pi ) A partir de aquí y tras intrincados procedimientos matemáticos que fueron demostrados por Shannon oportunamente se llega a que H es mínimo cuando f(Pi) = log2 (1/Pi). Entonces: H= ∑n i=0 Pi (− log2 Pi ) La longitud mínima con la cual puede codiﬁcarse un mensaje puede calcularse como Li=log2 (1/Pi) = -log2 (Pi). Esto da una idea de la longitud a emplear en los códigos a usar para los caracteres de un archivo en función de su probabilidad de ocurrencia. Reemplazando Li podemos escribir H como: H= ∑n i=0 −Pi log2 Pi De aquí se deduce que la entropía de la fuente depende únicamente de la probabilidad de ocurrencia de cada mensaje de la misma, por ello la importancia de los compresores estadísticos (aquellos que se basan en la probabilidad de ocurrencia de cada carácter). Shannon demostró, oportunamente que no es posible comprimir una fuente estadísticamente más allá del nivel indicado por su entropía. [6][7] 7 Otros aspectos de la teoría • Fuentes de información • Teorema de muestreo de Nyquist-Shannon • Entropía • Neguentropía • Información mutua • Canales • Capacidad • Compresión de datos • Codiﬁcación de fuente • Códigos no-singulares • Códigos unívocamente decodiﬁcables • Extensión de código • Códigos preﬁjo (o códigos instantáneos) • Control de errores • FEC • ARQ • Parada y espera • Rechazo múltiple • Rechazo selectivo • Técnicas híbridas • Concatenación de códigos • Tipo 1 • Tipo 2 • Detección de errores 5 • Bits de redundancia • Métodos de control de errores • Paridad • Códigos autochequeo y autocorrectores • Códigos de bloque • Distancia Hamming • Paridad horizontal y vertical • Códigos lineales • Códigos cíclicos • CRC16 • CRC32 8 Véase también • Información • Teoría algorítmica de la información 9 Referencias [1] Teoría matemática de la comunicación [2] Teoría Matemática de la Comunicación [3] Teoría de la Información [4] Teoría Matemático-informacional [5] Teoría de la Información | Textos Cientíﬁcos [6] Teoría de la Información [7] Teoría Matemática de la Información 6 10 10 10.1 TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES Text and image sources, contributors, and licenses Text • Teoría de la información Fuente: http://es.wikipedia.org/wiki/Teor%C3%ADa%20de%20la%20informaci%C3%B3n?oldid=80080605 Colaboradores: AstroNomo, PACO, ManuelGR, Interwiki, Sms, Ivan.Romero, Loco085, Yurik, Edub, Rembiapo pohyiete (bot), LP, RobotQuistnix, Sebasg37, Chobot, Jesuja, Eloy, Er Komandante, Chlewbot, Paintman, Fercufer, BOTpolicia, ULIF050020014, Valdrik, Davius, CaesarExcelsus, Thijs!bot, JAnDbot, Gbsuar, TXiKiBoT, Lalaconyforever, Elisardojm, Humberto, Cinevoro, VolkovBot, Urdangaray, Technopat, Muro Bot, SieBot, Pompilio Zigrino, Correogsk, Estirabot, BetoCG, Nerika, Julian leonardo paez, Ucevista, AVBOT, Diegusjaimes, Arjuno3, Luckas-bot, Nallimbot, Barnacaga, SuperBraulio13, Xqbot, Jkbw, Botarel, Execoot, Rcamacho, Frandzi.rangel, Velual, EmausBot, ChessBOT, WikitanvirBot, Loekiller, Earnaor, MerlIwBot, Nicoletis, Invadibot, Acratta, RosenJax, Addbot, JacobRodrigues, Egis57 y Anónimos: 63 10.2 Images • Archivo:Esquema_de_comunicación_Shannon.png Fuente: http://upload.wikimedia.org/wikipedia/commons/b/b6/Esquema_de_ comunicaci%C3%B3n_Shannon.png Licencia: CC BY-SA 3.0 Colaboradores: Trabajo propio Artista original: Nicoletis 10.3 Content license • Creative Commons Attribution-Share Alike 3.0