Teoría de la información

Es la teoría relacionada con las leyes matemáticas que rige la transmisión y el procesamiento de la información. Más concretamente, la teoría de la información se ocupa de la medición de la información y de la representación de la misma (como, por ejemplo, su codificación) y de la capacidad de los sistemas de comunicación para transmitir y procesar información.

La codificació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.

La teoría de la información fue desarrollada inicialmente, en 1948, por el ingeniero electrónico estadounidense Claude E. Shannon, en su artículo, A Mathematical Theory of Communication (Teoría matemática de la comunicación). La necesidad de una base teórica para la tecnología de la comunicación surgió del aumento de la complejidad y de la masificació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, 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. El término información se refiere a los mensajes transmitidos: voz o música transmitida por teléfono o radio, imágenes transmitidas por sistemas de televisión, información digital en sistemas y redes de computadoras, e incluso a los impulsos nerviosos en organismos vivientes. De forma más general, la teoría de la información ha sido aplicada en campos tan diversos como la cibernética, la criptografía, la lingüística, la psicología y la estadística.

            El tipo de sistema de comunicación más estudiado consta de varios componentes. El primero es una fuente de información (por ejemplo, una persona hablando) que produce un mensaje o información que será transmitida. El segundo es un transmisor (como, por ejemplo, un teléfono y un amplificador, o un micrófono y un transmisor de radio) que convierte el mensaje en señales electrónicas o electromagnéticas. Estas señales son transmitidas a través de un canal o medio, que es el tercer componente, como puede ser un cable o la atmósfera. Este canal es especialmente susceptible a interferencias procedentes de otras fuentes, que distorsionan y degradan la señal. (Algunos ejemplos de interferencias, conocidas como ruido, incluyen la estática en la recepción de radios y teléfonos, y la nieve en la recepción de imágenes televisivas). El cuarto componente es el receptor, como por ejemplo el de radio, que transforma de nuevo la señal recibida en el mensaje original. El último componente es el destinatario, como por ejemplo una persona escuchando el mensaje.

Dos de las principales preocupaciones en la teoría de la información son la reducción de errores por interferencias en los sistema de comunicación, y el uso más eficiente de la capacidad total del canal.

            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 definido y medible. El término cantidad no se refiere 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 refiere 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 0. Si, por ejemplo, se lanza una moneda al aire, el mensaje conjunto cara o cruz que describe el resultado, no tiene cantidad de información. Sin embargo, los dos mensajes por separado cara o cruz tienen probabilidades iguales de valor un medio. Para relacionar la cantidad de información (I) con la probabilidad, Shannon presentó la siguiente fórmula:

I = log21/p

donde p es la probabilidad del mensaje que se transmite y log2 es el logaritmo de 1/p en base 2. (log2 de un número dado X es el exponente Y al que tiene que ser elevado el número 2 para obtener dicho número X. Por ejemplo, log2 de 8 = 3, porque 23 = 8). Utilizando esta fórmula, obtenemos que los mensajes cara y cruz tienen una cantidad de información de log22 = 1.

La cantidad de información de un mensaje puede ser entendida como el número de símbolos posibles que representan el mensaje. En el ejemplo anterior, si cruz está representado por un 0 y cara por un 1, sólo hay una forma de representar el mensaje: 0 o 1. El 0 y el 1 son los dígitos del sistema binario (véase Sistema numérico), y la elección entre estos dos símbolos corresponde a la llamada unidad de información binaria o bit. Si se lanza una moneda tres veces seguidas, los ocho resultados (o mensajes) igualmente probables pueden ser representados como 000,001,010,011,100,101,110 o 111. Estos mensajes corresponden a los números 0,1,...7 escritos en notación binaria. La probabilidad de cada mensaje es de un octavo, y su cantidad de información es log21 ˆ = 3, que es el número de bits que se necesitan para representar cada mensaje.

            En la mayoría de las aplicaciones prácticas, hay que elegir entre mensajes que tienen diferentes probabilidades de ser enviados. El término entropía ha sido tomado prestado de la termodinámica, para designar la cantidad de información media de estos mensajes. La entropía puede ser intuitivamente entendida como el grado de desorden en un sistema. En la teoría de la información la entropía de un mensaje es igual a su cantidad de información media. Si en un conjunto de mensajes, sus probabilidades son iguales, la fórmula para calcular la entropía total sería: H = log2N, donde N es el número de mensajes posibles en el conjunto.

            Si se transmiten mensajes que están formados por combinaciones aleatorias de las 26 letras del alfabeto inglés, el espacio en blanco y cinco signos de puntuación, y si suponemos que la probabilidad de cada mensaje es la misma, la entropía sería: H = log232 = 5. Esto significa que se necesitan 5 bits para codificar cada carácter o mensaje: 00000, 00001, 00010, 11111. Una transmisión y almacenamiento eficiente de la información exige la reducción del número de bits utilizados en su codificación. Esto es posible cuando se codifican textos en español, porque la colocación de las letras no es aleatoria. Así, por ejemplo, la probabilidad de que la letra que suceda a la secuencia informació sea una n es muy alta.

Se puede demostrar que la entropía del español normal escrito es aproximadamente de un bit por palabra. Esto demuestra que la lengua española (como cualquier otra) tiene una gran cantidad de redundancia incorporada, que se denomina redundancia natural. Esta redundancia permite, por ejemplo, a una persona entender mensajes en los cuales faltan vocales, así como descifrar escritura poco legible. En los sistemas de comunicación modernos, se añade redundancia artificial a la codificación de mensajes, para reducir errores en la transmisión de los mismos.

Teoría de la información

(Redirigido desde Teoría de la Información)

Disciplina científica 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". Como nos indica su nombre esta disciplina estudia la información y todo lo relacionado con ella (canales, compresión, criptografía, etc,...).

La información es tratada como magnitud física y para caracterizar la información de una secuencia de símbolos se utiliza la entropía. Se parte de la idea de que los canales no son ideales, aunque muchas veces se idealicen las no idealidades, para estudiar distintos metodos para enviar información o la cantidad de información útil que se puede enviar a través de un canal.

Claude Shannon

(Redirigido desde Claude E. Shannon)

Claude Elwood Shannon (30 de abril de 1916 (Michigan) - 24 de febrero de 2001) recordado como "el padre de la teoría de la información".

Los primeros años de su vida los pasó en Gaylord, donde se graduó de la secundaria en 1932. Desde joven, Shannon demostró una inclinación hacia las cosas mecánicas. Resaltaba respecto a sus compañeros en las asignaturas de ciencias. Su héroe de la niñez era Edison, a quien luego se acercó bastante en sus investigaciones.

En 1932 ingresó en la Universidad de Michigan, siguiendo a su hermana Catherine, Doctora en matemáticas. En 1936 obtuvo los titulos de ingeniero eléctrico y matemático. Su interés por las matemáticas y la ingeniería continuó durante toda su vida.

En 1936 aceptó la posición de asistente de investigación en el departamento de ingeniería eléctrica en el Instituto de Tecnología de Massachusetts (MIT). Su situación le permitió continuar estudiando mientras trabajaba por horas para el departamento, obteniendo como resultado la calculadora más avanzada de esa era..

En ese momento surgió su interés hacia los circuitos de relevadores complejos , sumado a su gusto por la lógica y álgebra boleana. Estos nuevos interesespudo desarrollarlos durante el verano de 1937, que pasó en los laboratorios Bell en la ciudad de Nueva York.

En su tesis doctoral en el M.I.T., demostró como el álgebra boleana se podía utilizar en el análisis y la síntesis de la conmutación y de los circuitos digitales. La tesis despertó un interés considerable cuando apareció en 1938 en las publicaciones especializadas. En 1940 le fue concedido el Premio Nobel de las sociedades de ingeniería de los Estados Unidos, una concesión dada cada año a una persona de no más de treinta años . Un cuarto de siglo más tarde H. H. Goldstine, en su libro "Las computadoras desde Pascal hasta von Neumann", citó su tesis como una de las más importantes de la historia... que ayudó a cambiar el diseño de circuitos digitales.

Durante el verano de 1938 efectuó trabajos de investigación en el M.I.T.y le fue concedida la beca Bolles cuando trabajaba como ayudante de enseñanza mientras realizaba un doctorado en matemáticas.

En 1940 estudió un master en ingeniería eléctrica y se doctoró en filosofía matemática.

Shannon pasó quince años en los laboratorios Bell, una asociación muy fructífera con muchos matemáticos y científicos de primera línea como Harry Nyquist, Brattain, Bardeen y Shockley, inventores del transistor; George Stibitz, quien construyó computadoras basadas en relevadores y muchos otros más.

Durante este período Shannon trabajó en muchas áreas, siendo lo mas notable todo lo referente a la teoría de la información, un desarrollo que fue publicado en 1948 bajo el nombre de "Una Teoría Matemática de la Comunicación". En este trabajo se demostró que todas las fuentes de información (telégrafo, teléfono, radio, la gente que habla, las cámaras de televisión, etc, ... )se pueden medir y que los canales de comunicaciones tienen una unidad de medida similar. Mostró también que la información se puede transmitir sobre un canal si y solamente si la magnitud de la fuente no excede la capacidad de transmisión del canal que la conduce y sentó las bases de la corrección de errores, supresión de ruidos y redundancia.

En el área de las computadoras y de la inteligencia artificial, publicó en 1950 un trabajo que describía la programación de una computadora para jugar ajedrez, convirtiéndose en la base de posteriores desarrollos.

A lo largo de su vida recibió numerosas condecoraciones y reconocimientos de universidades e instituciones de todo el mundo.

Shannon debe ser considerado dentro de los personajes mas importantes del siglo XX, aunque su nombre es desconocido para el público en general.

Claude Shannon falleció el 24 de febrero del año 2001, a la edad de 84 años, después de una larga lucha en contra del Alzheimer.

Entropía

De Wikipedia, la enciclopedia libre.

1| entropía (Física) Magnitud termodinámica que mide la parte de la energía que no puede utilizarse para producir un trabajo. En un sentido más amplio se interpreta como la medida del desorden de un sistema.

2| entropía (Teoría de la información) Magnitud que mide la información contenida en un flujo de datos, es decir, lo que nos aporta sobre un dato o hecho concreto.

Por ejemplo, que nos digan que las calles están mojadas, sabiendo que acaba de llover, nos aporta poca información, porque es lo habitual. Pero si nos dicen que las calles están mojadas y sabemos que no ha llovido, aporta mucha información (porque no las riegan todos los días).

Nótese que en el ejemplo anterior la cantidad de información es diferente, pese a tratarse del mismo mensaje: Las calles están mojadas. En ello se basan las técnicas de compresión de datos, que permiten empaquetar la misma información en mensajes más cortos.

La medida de la entropía puede aplicarse a información de cualquier naturaleza, y nos permite codificarla adecuadamente, indicándonos los elementos de código necesarios para transmitirla, eliminando toda redundancia. (Para indicar el resultado de una carrera de caballos basta con transmitir el código asociado al caballo ganador, no hace falta contar que es una carrera de caballos ni su desarollo).

La entropía nos indica el límite teórico para la compresión de datos.

Su cálculo se realiza mediante la siguiente fórmula:

H = p1*log(1/p1)+p2*log(1/p2)+ .. pm*log(1/pm)

donde H es la entropía, las p son las probabilidades de que aparezcan los diferentes códigos y m el número total de códigos. Si nos referimos a un sistema, las p se refieren a las probabilidades de que se encuentre en un determinado estado y m el número total de posibles estados

Se utiliza habitualmente el logaritmo en base 2, y entonces la entropía se mide en bits.

Por ejemplo: El lanzamiento de una moneda al aire para ver si sale cara o cruz (dos estados con probabilidad 0,5) tiene una entropía:

H = 0,5*log2(1/0,5)+0,5*log2(1/0,5) = 0,5*log2(2)+0,5*log2(2) = 0,5+0,5 = 1 bit

A partir de esta definición básica se pueden definir otras entropías.

Canal de comunicaciones

De Wikipedia, la enciclopedia libre.

En telecomunicación, el término canal tiene los siguientes significados:

1. Una conexión entre los puntos de inicio y terminación de un circuito.

2. Un camino único facilitado mediante un medio de transmisión que puede ser:

a) Con separación física, tal como un par de un cable multipares
b) Con separación eléctrica, tal como la multiplexación por división de frecuencia (MDF) o por división de tiempo (MDT).

3. Un camino para el transporte de señales eléctricas o electromagnéticas, usualmente distinguido de otros caminos paralelos mediante alguno de los métodos señalados en el punto anterior.

4. En conjunción con una predeterminada letra, número o código hace referencia a una radiofrecuencia específica

5. Porción de un medio de almacenamiento, tal como una pista o banda, que es accesible a una cabeza o estación de lectura o escritura.

6. En un sistema de comunicaciones, es la parte que conecta una fuente (generador) a un sumidero (receptor) de datos

Fuente: Federal Standard 1037C y MIL-STD-188

Capacidad

De Wikipedia, la enciclopedia libre.

En el estudio de la Electricidad, se denomina Capacidad de un conductor a la propiedad de adquirir carga eléctrica cuando es sometido a una diferencia de potencial con respecto a otro en estado neutro.

La capacidad queda definida numéricamente por la carga que adquiere por cada unidad de potencial.

En el Sistema internacional de unidades la capacidad se mide en Faradios (F), siendo un faradio la capacidad de un conductor que sometido a una diferencia de potencial de 1 voltio, adquiere una carga eléctrica de 1 culombio.

Compresión de datos

De Wikipedia, la enciclopedia libre.

Operaciones que se realizan sobre la información de una fuente con el objetivo de eliminar la redundancia de información.

Código fuente

(Redirigido desde Códigos fuente)

Etapas en la realización de programas:

A diferencia del código objeto, el código fuente es texto simple, capaz de ser leído por cualquier editor de textos. En él están escritas las instrucciones que deberá realizar la computadora, según la sintaxis de un lenguaje de programación. Tener el código fuente es de gran importancia si se necesita modificar un programa.

Códigos no-singulares

De Wikipedia, la enciclopedia libre.

Códigos cuyo alfabeto contiene una palabra código distinta para cada palabra fuente.

Códigos Unívocamente Decodificables

(Redirigido desde Códigos unívocamente decodificables)

Código cuya extensión es no-singular

Extensión de código

De Wikipedia, la enciclopedia libre.

La extensión de un código está formada por las posibles concatenaciones de las diferentes palabras código.

Códigos Prefijo O Instantáneos

(Redirigido desde Códigos prefijo o instantáneos)

Es un código en el que ninguna palabra código sea prefijo de otra palabra código.

FEC

De Wikipedia, la enciclopedia libre.

El FEC (Frecuent Error Correction) es un protocolo utilizado para corregir errores en una transmisión. Este se utiliza en sistemas sin retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión para mostrar los datos

El funcionamiento consiste en evaluar el sindrome del vector recibido (si no existe error el sindrome es el vector cero). Asociado a éste síndrome tenemos varios errores (para un código C(n,k) 2^k diferentes) de entre todos ellos tomaremos el más probable según las características del canal (en general el de menor peso). Para recuperar el vector original enviado sumamos el error calculado a el vector recibido de forma que si hemos acertado al suponer el error concreto de todos los asociados al síndrome cancelaremos su efecto.

Esta técnica tiene sus limitaciones ya que la interpretación del vector error asociado al síndrome calculado no es exacta.

ARQ

De Wikipedia, la enciclopedia libre.

El ARQ (del inglés Automatic repeat request) es un protocolo utilizado para el control de errores en la transmisión de datos, garantizando la integridad de los mismos. Éste suele utilizarse en sistemas que no actúan en tiempo real ya que el tiempo que se pierde en el reenvío puede ser considerable y ser más útil emitir mal en el momento que correctamente un tiempo después. Esto se puede ver muy claro con una aplicación de videoconferencia donde no resulta de utilidad emitir el pixel correcto de la imagen 2 segundos después de haber visto la imagen.

Esta técnica de control de errores se basa en el reenvio de los paquetes de información que se detecten como erróneos (Esto quiere decir que no todos los paquetes de información se detectan como erroneos).

Para controlar la correcta recepción de un paquete se utilizan ACK's (acknowledge) y NACK´s de forma que cuando el receptor recibe un paquete correctamente el receptor asiente con un ACK y si no es correcto responde con un NACK.Durante el protocolo que controla recepción de paquetes pueden surgir múltiples problemas (perdida de ACK, recibir un ACK incorrecto, etc,...) complicandose así elcontenido del ACK y surgiendo nuevos conceptos como el de timeout.

Si el emisor no recibe información sobre la recepción del paquete durante un tiempo fijado (timeout) éste se reenvía automaticamente.

Esencialmente existen tres tipos de ARQ aunque en la práctica se combinen buscando el sistema óptimo para cada canal o estado de tráfico concreto.

·                    Parada y espera

·                    Parada y espera

·                    Rechazo selectivo

Parada y espera

De Wikipedia, la enciclopedia libre.

En este tipo de respuesta ARQ no se envia el siguiente paquete hasta que no se recibe el correspondiente ACK y en caso de recibir un NACK se reenvia el paquete anterior.

Rechazo múltiple

De Wikipedia, la enciclopedia libre.

En este tipo de respuesta ARQ no se dejan de enviar paquetes hasta que se recibe un NACK en ese momento se interrumpe la transmisión y se empieza la transmisión continua a partir del paquete que tenía errores desperdiciando así toda la información transmitida entre el primer envío y la detección del error.

Este tipo de ARQ exige una memoria en el transmisor que sea capaz de almacenar tantos datos como los que puedan enviarse en un timeout, ya que será el tiempo máximo de espera y esos datos deben reenviarse tras detectar un error.

Otra de las exigencias de este tipo de ARQ es la numeración de los ACK's para poder distinguir a que paquete de información estan asintiendo.

Rechazo selectivo

De Wikipedia, la enciclopedia libre.

El rechazo selectivo es un tipo de respuesta usado en control de errores.

En este tipo de respuesta ARQ no se dejan de enviar paquetes hasta que se recibe un NACK en ese momento se termina de enviar el paquete que estábamos transmitiendo y se reenvia el paquete que tenía errores inmediatamente depués se sigue enviando la información a partir del último paquete que se había enviado.

Este tipo de ARQ exige una memoria en el transmisor que sea capaz de almacenar tantos datos como los que puedan enviarse en un timeout, ya que será el tiempo máximo de espera y esos datos deben reenviarse tras detectar un error.

Otra de las exigencias de este tipo de ARQ es la numeración de los ACK's para poder distinguir a que paquete de información estan asintiendo.

Quizá el más molesto de todos los inconvenientes sea la recepción desordenada de la información lo que nos obliga a ordenarla en el emisor o tener una memoria que nos permita al macenar los datos mientras tenemos un paquete erróneo.

Técnicas híbridas

De Wikipedia, la enciclopedia libre.

La mayoría de las veces el resultado óptimo no se consigue con una de las técnicas "puras" ya sea por las características de la fuente o por las exigencias del receptor. En estos casos utilizamos la combinación de sistemas de protección/detección/corrección complementarios.

Concatenación de códigos

De Wikipedia, la enciclopedia libre.

La idea es muy simple e intuitiva consiste en codificar simultaneamente de códigos adecuados ante distintos tipos de errores (ruido blanco, ráfagas,...)

Control de errores tipo 1

De Wikipedia, la enciclopedia libre.

Esta técnica híbrida consiste en combinar las capacidades correctoras y detectoras de los códigos. De esta forma en el receptor si podemos corregir el error lo corregimos y si no pedimos retransmisión (ARQ).

Control de errores tipo 2

De Wikipedia, la enciclopedia libre.

En el caso anterior híbrida Tipo 1 en caso de corregir estamos desperdiciando información ya que no hemos utilizado la información relativa a la detección de errores. Con esta técnica buscamos optimizar por esa vía. Ahora transmitimos la información mas la redundancia para detectar errores. Si se produce se pide al transmisor que nos envie la redundancia de un código invertible que permita repara los errores que pueden ser detectados.