Entropía e información. Criterios de optimización. Entropía de una fuente de mensajes discretos

En el pasado, la humanidad no experimentó la necesidad de medir cuantitativamente la información. Esta necesidad surgió en relación con el desarrollo de comunicaciones, equipos de medición y sistemas informáticos.

La primera métrica cuantitativa fue propuesta por Hartley en 1928 y la llamó capacidad de información.

Considere alguna celda de norte relé. Suponiendo que cada relé puede almacenar dos estados metro= 2, toda la celda puede contener norte= 2norte estados. Hartley introdujo la medida logarítmica binaria, que permite medir la información en unidades binarias: bits. Un bit es la cantidad de información que se puede almacenar en una celda unitaria en dos estados: . Los almacenes de células estatales . La base del logaritmo determina la dimensión de las unidades de medida de información. Dado que se utilizan unidades binarias (bits), se omite la base del logaritmo. La unidad binaria de información “bit” proviene de la “compresión” de las palabras inglesas dígito binario - unidad binaria.

Esta medida es aditivo, le permite realizar suma información en diferentes celdas al combinarlas en una sola.

La medida de Hartley (una métrica estructural de información) no reflejaba la naturaleza probabilística de la información y no podía usarse para evaluar las propiedades de la información de las fuentes de mensajes. En 1948, Shannon propuso una estadística, es decir. medida de probabilidad.

Deje que una fuente discreta genere un mensaje A, perteneciente a algún conjunto finito A(). Determinemos la cantidad de información contenida en este mensaje utilizando tres requisitos naturales (obvios) iniciales:

1) la cantidad de información debe ser una cantidad aditiva, es decir, en dos mensajes independientes, la cantidad de información se determina como la suma de las cantidades de información en cada uno de ellos;

2) la cantidad de información en el mensaje sobre un evento confiable es 0;

3) la cantidad de información no debe depender del contenido cualitativo del mensaje (grado de importancia, posibles consecuencias de su transmisión, color emocional, etc.).

En general, el mensaje A del conjunto A caracterizado por la probabilidad de que la fuente genere o envíe este mensaje, es decir, la cantidad de información I(a) contenido en el mensaje A, debe ser una función de la probabilidad.

,

¿Dónde están las probabilidades de generación de mensajes? A 1 y A 2 respectivamente.

Cantidad total de información I(a 1 , A 2), contenida en estos dos mensajes, según la condición de aditividad se define como la suma de las cantidades de información en cada uno de ellos:

Por lo tanto, necesitamos encontrar una función de probabilidad tal que cuando se multiplican dos argumentos, los valores de la función sumen. Esta condición se cumple únicamente con la función logarítmica.

,

Dónde k– coeficiente arbitrario.

Un logaritmo, en términos generales, se puede llevar a cualquier base. Esta fórmula se puede utilizar para determinar la cantidad de información contenida en un mensaje. y yo. Esta fórmula también satisface el requisito 2): en el caso de un evento confiable, la probabilidad de un mensaje = 1. Entonces la cantidad de información según la fórmula resultante:

Porque< 1, и следовательно, log ≤ 0, то, чтобы измерять количество информации неотрицательными числами, выбираем значение коэффициента k= –1:

.

La base del logaritmo suele elegirse igual a dos en la fórmula para determinar la cantidad de información. La unidad de información resultante se llama unidad binaria, o poco.

Una unidad de este tipo es más conveniente porque en la tecnología informática y de comunicaciones moderna se utilizan ampliamente códigos binarios y dispositivos binarios discretos.

Deje que una fuente discreta de mensajes genere un conjunto completo de mensajes, donde está la probabilidad del enésimo mensaje. Esta fuente se puede caracterizar por la cantidad promedio de información por mensaje:

.

Shannon llamó a esta cantidad entropía de la fuente. El concepto de entropía (del griego "en-tropo" - circulación) existía antes de Shannon y se extendió a varias áreas del conocimiento. En termodinámica, entropía significa la probabilidad del estado térmico de una sustancia; en matemáticas, el grado de incertidumbre de una situación o tarea, caracteriza; capacidad de la fuente para proporcionar información. La cantidad de información transportada por un mensaje fuente. . Esta medida se deriva de la medida Hartley: y es su generalización al caso de probabilidad desigual de mensajes. Se puede observar que cuanto menor es la probabilidad de un mensaje, mayor es la cantidad de información que transporta. La medida de Shannon también es aditiva.

Y la cantidad de información I en mensaje y entropía de fuente h se miden en las mismas unidades, en bits, pero estas cantidades son diferentes. entropía h la fuente determina la capacidad de la fuente para producir información; si hay suficientes estadísticas, se pueden calcular a priori, antes de recibir mensajes. Obteniendo información I elimina parte de la incertidumbre de la fuente y reduce su entropía. Esta disminución de entropía se produce después (a posteriori) de la recepción del mensaje, es decir. I determinado a posteriori. De este modo, cantidad de información puede ser considerado como lo opuesto a la entropía, esto revela la ley dialéctica de la unidad y la lucha de los opuestos.

La entropía de una fuente de mensaje discreta tiene las siguientes propiedades:

1. La entropía es positiva.

2. La entropía de los mensajes deterministas es cero. Si uno de los mensajes de la fuente es confiable, es decir su probabilidad es 1, entonces las probabilidades de otros mensajes son cero.

3. La entropía es máxima si los mensajes de la fuente son igualmente probables.

.

4. En el caso de mensajes igualmente probables, la entropía aumenta con el número de mensajes.

5. La entropía de la fuente de mensajes binarios (binarios) varía de cero a uno dependiendo de la probabilidad de los mensajes y tiene un máximo en . En este caso, la medida de Shannon coincide con la medida de Hartley. Una fuente con una entropía de 1 bit es completamente consistente con un canal, por ejemplo, un relé, que tiene una capacidad de información de 1 bit. Si los mensajes no son igualmente probables, el canal estará subcargado. La dependencia de la entropía de la probabilidad de una fuente binaria a veces se denomina función de Shannon (Fig. 40). Si la cantidad de mensajes fuente es grande y los mensajes son igualmente probables, se pueden transmitir utilizando un código binario uniforme. Así, se codifican ocho mensajes: 000, 001, 010, 011, 100, 101, 110, 111. La entropía de origen es igual a tres: esto es lo mismo que el número promedio de caracteres por mensaje. A veces se utiliza el concepto entropía específica, esta es la entropía por carácter. Esta fuente tiene una entropía de 3 bits por mensaje también podemos decir que su entropía es de 1 bit/símbolo; Esta evaluación es conveniente al comparar diferentes fuentes.

Consideremos cómo se pueden utilizar los conceptos introducidos para revelar la incertidumbre de la fuente.

Ejemplo 1. Suponga que necesita adivinar el número deseado del 1 al 32 haciendo preguntas binarias de origen. Dado que el número deseado puede ser cualquier número con igual probabilidad, la entropía de la fuente norte= log 32 = 5 bits/número. Hacemos la primera pregunta: ¿Está el número en la mitad inferior? Respuesta: sí. Cantidad de información recibida de la fuente. I= 1 bit. La entropía de la fuente disminuyó y se volvió norte= 4 bits/número. Al volver a hacer una pregunta similar y obtener cualquier respuesta, reducimos el rango de búsqueda a la mitad y reducimos la incertidumbre de la fuente en un bit. Habrá exactamente cinco preguntas y respuestas de este tipo, después de lo cual la entropía de la fuente será cero.

Ejemplo 2. Supongamos que entre 25 monedas, una es falsa, más ligera. ¿Cuál es el número mínimo de pesajes en una báscula de palanca que se deben realizar para encontrar una moneda falsa?

En primer lugar, determinamos la entropía de la fuente. Dado que la balanza puede estar en tres estados, cada pesaje reduce la entropía de la fuente en una unidad ternaria de información. Por lo tanto, las monedas deben dividirse en tres montones aproximadamente iguales: 8, 8 y 9 monedas. Colocando el mismo número de monedas de 8 y 8 en la balanza, determinamos si hay alguna moneda falsa entre ellas y, de ser así, en qué vaso. Supongamos que la primera pila es más ligera que la segunda. Entonces la moneda está aquí. Dividimos este montón en tres partes 3, 3 y 2. Pesamos partes idénticas. Digamos que son iguales. Esto significa que la moneda deseada se encuentra entre las dos restantes. En el tercer pesaje se encontró la moneda.

El número caracteriza la cantidad de características del código utilizadas al transmitir mensajes. Este número define el alfabeto fuente. Cuando aumenta la entropía específica de la fuente. En principio, dicha fuente es más eficiente; permite transmitir más información por unidad de tiempo. Entonces, si el alfabeto fuente tiene 32 letras, entonces la entropía fuente es 5 bits/letra; si el idioma chino utiliza alrededor de 2000 caracteres, entonces la entropía de dicha fuente es de 11 bits/carácter, es decir 11 bits/símbolo. Está claro que el uso de un alfabeto grande conlleva dificultades técnicas, de ahí que el más extendido en tecnología sea el alfabeto binario con letras o símbolos 0 y 1. Una fuente que opere con dicho alfabeto no puede tener una entropía superior a 1 bit/carácter. .

La cantidad y calidad de la información, además de la teoría estadística, también se puede caracterizar en términos de la teoría estructural, que considera la estructura de los conjuntos de información, así como de la teoría semántica, que tiene en cuenta la conveniencia, utilidad y valor de la información.

La cuestión de la conexión entre entropía e información se ha discutido durante mucho tiempo, de hecho, desde la formulación de la paradoja del "demonio de Maxwell". Durante algún tiempo el problema pareció abstracto. Ahora, sin embargo, está adquiriendo relevancia, ya que resulta estar relacionado con cuestiones muy concretas: cuál es el pago de entropía (y energía) por la información, cuáles son los tamaños mínimos de una celda de información, etc.

Estas preguntas se vuelven especialmente agudas debido a la especificidad biológica. En primer lugar, los sistemas de información de la naturaleza viva son de tamaño pequeño (microscópico). En segundo lugar, funcionan a temperatura normal, es decir, en condiciones en las que las fluctuaciones térmicas no son despreciables. En tercer lugar, en biología, memorizar y almacenar información es de particular importancia. Tenga en cuenta que en tecnología los problemas de transferencia de información son más relevantes; Utilizando el ejemplo de la optimización de la transmisión, se desarrollaron los principios básicos de la teoría de la información. Se prestó menos atención a las cuestiones de recepción y almacenamiento de información. En biología, por el contrario, estas cuestiones se vuelven primordiales.

Sin pretender dar una definición estricta del concepto de “información”, enfatizamos dos de sus atributos necesarios: 1) la información implica elegir una (o varias) opciones entre muchas posibles, 2) la elección realizada debe ser recordada. Destaquemos: la segunda condición, memorizar información, es muy importante. Kastler [P26] llamó la atención sobre esto por primera vez en 1960. En los procesos de transferencia de información, la “memorabilidad” juega un papel menor que en la recepción, procesamiento y almacenamiento de información. De hecho, el sistema transmisor debe recordar información sólo durante la duración de la transmisión, que en principio puede ser breve. En biología, por el contrario, la condición de memorización a largo plazo juega un papel importante.

La cantidad de información es la cantidad.

donde está el número total de opciones posibles, el número de opciones seleccionadas. La cantidad de información es distinta de cero si se sabe que por alguna razón se realizó una de las opciones a priori (pero no se sabe cuál). Esta cantidad es máxima si, es decir, se sabe que se implementó (seleccionó) una opción específica. Valor si

No se sabe nada. La base del logaritmo (es decir, binaria) se elige por conveniencia; La unidad de información en este sistema es un bit; corresponde a la elección de una opción entre dos posibles.

La expresión (12.8) se generaliza fácilmente al caso en el que N opciones a priori se pueden realizar con probabilidades y se realizan a posteriori con probabilidades, entonces

La selección o implementación de opciones posteriores se puede realizar de dos formas diferentes; ya sea como resultado de la acción de fuerzas externas - en este caso se habla de la recepción de información de otro sistema (de terceros), o de forma espontánea, como resultado del comportamiento inestable del propio sistema - en este caso el nacimiento (aparición) de nueva información tiene lugar.

Un sistema de información debe ser capaz de: a) recibir información, b) almacenar o, lo que es lo mismo, recordar información, c) proporcionar información al interactuar con otro sistema aceptor en relación con el sistema considerado. De ello se deduce que el sistema de información debe ser multiestacionario.

El número de estados estacionarios estables determina la capacidad de información, es decir, la cantidad máxima de información que el sistema puede recibir:

El sistema debe ser disipativo. Esto significa que las partes reales de todos los números característicos de estados estacionarios son negativas; esta es una condición necesaria para recordar información. Un ejemplo de este sistema es el billar chino. Es una bola sobre un tablero con lados, agujeros y alfileres. La pertenencia de la bola a un hoyo específico es información sobre el estado del sistema.

A nivel microscópico (molecular), el problema del diseño de sistemas de información deja de ser trivial. En primer lugar, en un sistema multiestacionario, cada una de las trayectorias de fase está ubicada solo en una determinada parte del espacio de fase (en la región de atracción de un estado determinado). El volumen de fase completo no está disponible para cada una de las trayectorias. Esto significa que el sistema de información no está completamente en equilibrio geométrico y termodinámico. Deben seleccionarse grados de libertad que conserven sus valores durante mucho tiempo y no pasen por todos los posibles.

Expliquemos esto usando el ejemplo del billar chino. Los grados de libertad seleccionados aquí son las coordenadas de la pelota. El cambio en xey se limita a los bordes de los pocillos; la bola no puede moverse a otro hoyo sin intervención externa. Al mismo tiempo

Otros grados de libertad asociados con las vibraciones de los átomos tanto de la pelota como del tablero pueden (y además deben) ser ergódicos.

En segundo lugar, la condición de disipación, como hemos visto, está asociada con la inestabilidad (y por tanto con el caos) de los movimientos microscópicos. Esto significa que los grados de libertad correspondientes deben ser ergódicos. Por tanto, el espacio de fases del sistema de información debe estratificarse en subsistemas ergódicos y dinámicos. Sin embargo, esta separación no puede realizarse de forma absolutamente estricta; los diferentes grados de libertad siempre están relacionados entre sí. Esto se manifiesta en el hecho de que los grados de libertad dinámicos (de información) fluctúan y existe cierta probabilidad de que cambien radicalmente (por ejemplo, lanzar una pelota a otro hoyo) bajo la influencia del subsistema ergódico (es decir, fluctuaciones térmicas).

En sistemas de información macroscópicos esta probabilidad es insignificante, pero en sistemas microscópicos debe tenerse en cuenta. Por tanto, las condiciones de multiestacionariedad y disipación no pueden satisfacerse simultáneamente de forma absolutamente estricta; son opcionales. Esto significa que la condición de “memorización” no puede ser absoluta; sólo podemos hablar de memorización con una cierta probabilidad durante un tiempo determinado (no infinitamente largo). En otras palabras, un sistema de información no puede recordar para siempre. En los sistemas de información reales, el tiempo de almacenamiento característico depende de su diseño, temperatura y energía libre.

La cuestión de la conexión entre entropía e información a la luz de lo anterior no resulta trivial. La entropía física es el logaritmo del volumen de fase disponible para el sistema (teniendo en cuenta las convenciones de este concepto, ver arriba), medido en unidades donde es el número de grados de libertad y el tamaño de la celda mínima (cuántica) del espacio de fase. Formalmente, la entropía se puede representar como

La cantidad es entropía medida en bits; número de celdas del espacio de fase. Por otro lado, la capacidad de información se puede escribir en la forma

¿Dónde está el tamaño del espacio de fase de una celda de información? Una comparación de las fórmulas (12.11) y (12.12) muestra que la entropía y la información difieren tanto en el coeficiente como en el tamaño de celda.

La coincidencia de (12.11) y (12.12) en la forma sirvió de base para la afirmación sobre la identidad de los conceptos de información y entropía. Más precisamente, se afirma que la entropía es la información que falta sobre el estado del sistema y (o) la información es la entropía que falta, es decir, la diferencia entre la entropía máxima, que

Tendríamos un sistema sin información, y la entropía real que tiene el sistema al poseer la información recibida. En este sentido se utiliza el término neentropía, que se considera idéntico a información.

Sin embargo, muchos no están satisfechos con estas afirmaciones y la cuestión de la conexión entre información y entropía sigue siendo controvertida.

Analicemos el tema con más detalle.

En primer lugar, llama la atención la gran diferencia cuantitativa entre la información contenida en el sistema y su entropía.

Blumenfeld (ver [P61), utilizando varios ejemplos biológicos (células, organismos, etc.), demostró que la entropía contenida en un objeto es muchas veces (varios órdenes de magnitud) mayor que la información disponible en él. La diferencia es aún mayor en los sistemas de información modernos no vivos (por ejemplo, en el texto impreso, la entropía excede la información en aproximadamente 1010 veces).

Una diferencia cuantitativa tan grande no es accidental. Se debe a que el volumen del espacio de fase de la celda de información es grande en comparación con el valor de Este último se debe a que la celda de información debe contener un subsistema ergódico y, por lo tanto, ocupar un gran (en comparación con la celda elemental) volumen.

Por tanto, la diferencia en las escalas de entropía y de información no es accidental, sino que está asociada a su diferencia fundamental. La entropía es una medida del conjunto de aquellos estados de un sistema en los que el sistema debería olvidarse de estar; La información es una medida del conjunto de estados en los que el sistema debe recordar estar.

Veamos cómo se relacionan los cambios de entropía y de información usando el ejemplo del billar chino. Limitemos nuestra consideración a la vida útil del sistema. El hecho es que cualquier sistema de información, al no estar en equilibrio, se relaja y colapsa según sus grados estructurales de libertad, es decir, deja de ser informativo.

El tiempo de relajación estructural es mayor (o igual) al tiempo de memorización. En nuestro ejemplo estamos hablando de la destrucción espontánea de barreras entre agujeros; El tiempo característico de este proceso es bastante largo. Durante este tiempo, los grados de libertad estructurales no cambian y, por tanto, no contribuyen a la entropía. (La parte del espacio de fase asociada con estos grados de libertad es inaccesible en este momento). En este caso, la entropía está asociada sólo con grados de libertad que se relajan rápidamente. Su comportamiento no depende de en cuál de los hoyos se encuentre la bola y de si está colocada en algún hoyo o se encuentra cerca. La entropía física del sistema es la misma en todos los casos, pero la cantidad de información es diferente: es igual a cero si la bola no se coloca en un agujero, e igual si está en un agujero determinado.

El proceso de recepción de información (en nuestro caso, colocar una bola en un determinado agujero) requiere un gasto de trabajo, que se convierte en calor (de lo contrario la recepción no sería irreversible). En consecuencia, durante la recepción, la entropía física del sistema aumenta (en la cantidad y al mismo tiempo

la información aumenta (en la cantidad Por lo general, pero por lo demás no están conectados de ninguna manera. Por lo tanto, al recibir información, no se observa la proporción.

La situación se complica algo más cuando surge nueva información. Un sistema capaz de generar información debe tener todas las propiedades de un sistema de información y, además, cumplir la condición: una determinada capa de su espacio de fase debe ser esférica, incluidos los grados de libertad seleccionados (informativos). Es en este caso que se establecen las condiciones iniciales para el surgimiento espontáneo de información.

Un ejemplo es el mismo billar chino con bolos. Si al principio la energía cinética de la bola es lo suficientemente alta (más barreras entre los agujeros), entonces la bola se mueve por todo el tablero sin quedarse atrapada en los agujeros. Debido a la inestabilidad de la reflexión de las horquillas (desempeñan el papel de superficies cóncavas en el billar del Sinaí, figura 12.2), el movimiento de la bola es estocástico y las condiciones iniciales se olvidan rápidamente. Cuando la energía cinética disminuye (debido a la disipación del sistema, en este caso por rozamientos y colisiones) hasta un valor del orden de la altura de la barrera, la bola entra en la zona de atracción de uno de los agujeros y permanece en ello. Así, se “recuerda” el estado seleccionado, que es el nacimiento de la información. El mismo principio se utiliza en la ruleta y otras máquinas de juego.

En todos estos casos, el criterio para separar la capa ergódica de condiciones iniciales de la capa de información es el valor de la energía libre inicial (en billar, esta es la energía cinética de la bola). También determina el aumento de la entropía del sistema en el proceso de generación de información. Estimemos el valor Si la capacidad de información del sistema es pequeña: entonces la principal limitación desde abajo es la condición donde se encuentra la barrera entre los agujeros. Las barreras determinan el tiempo de “memorización” según la proporción

Para un valor c suficientemente grande (macroscópico), la barrera es

Así, en este caso, el aumento de entropía por bit de información es igual a

o en unidades de información:

En el caso de que la capacidad de información sea grande (es decir, se debe tener en cuenta otra condición: antes de “seleccionar” un determinado estado, el sistema debe visitar al menos una vez el área de influencia de cada uno de los posibles estados.

Deje que la energía se disipe durante el paso de cada uno de los estados. El valor mínimo es del orden de la energía de las fluctuaciones térmicas: en este caso, está limitado desde abajo por la condición.

El aumento de entropía por cada bit de información es igual a

Así, en el caso de que surja información, hay que “pagarla” con un aumento de entropía, de modo que, sin embargo, relaciones como “el aumento de información es igual a la disminución de entropía” tampoco se cumplen en este caso.

Analicemos la situación que surge si rechaza la condición de recordar información. En este caso, podemos hablar de información sobre los valores instantáneos de las coordenadas y momentos de todos los átomos del sistema. Para distinguir esta “información” de la real (memorizada), Laizer propuso el término microinformación; la información memorizada se denomina macroinformación.

Si se sabe que en este momento el sistema se encuentra en una (de las posibles) celda específica del espacio de fase, entonces la cantidad de microinformación es máxima e igual a

En este caso, la entropía del sistema es cero, ya que todas las demás células pueden considerarse "inaccesibles" en este momento.

Si se sabe que en este momento el sistema se encuentra en alguna de las celdas posibles, pero no se sabe cuál, entonces la microinformación es cero y la entropía es máxima e igual a

Si se sabe que el sistema se encuentra actualmente en una (cualquiera) de las celdas, entonces

y entre microinformación y entropía existe una relación simple:

La microinformación, en principio, puede transformarse en macroinformación recibiéndola mediante otro sistema de información. Por ejemplo, al fotografiar un patrón de movimiento browniano, se pueden capturar (recordar) las coordenadas instantáneas de las partículas en una película fotográfica. Esta información luego se puede utilizar para cualquier (incluso no relacionado con el movimiento de partículas)

objetivos. Es importante que en este caso, en el proceso de recepción (transformación de microinformación en macroinformación), se deba gastar trabajo y aumentar la entropía de todo el sistema en una cantidad que obviamente exceda la cantidad de información almacenada.

Es este proceso -la transformación de la microinformación en macroinformación y su uso para la gestión- el que está en el centro de la paradoja del "demonio de Maxwell". Su solución es que el proceso de recibir microinformación y utilizarla para el control vaya acompañado de un aumento de la entropía de todo el sistema/información superada.

En relación con una diferencia tan significativa entre micro y macroinformación, también se utilizan dos conceptos de entropía. Junto con la entropía física, se utiliza la entropía de la información, que se define como

¿Dónde está el número de macroestados estacionarios estables de los cuales se sabe que el sistema está en uno de ellos (pero no se sabe cuál)?

Según la definición, la entropía de la información está relacionada con la información por la relación

Un aumento de la información (mientras se mantiene) siempre va acompañado de una disminución igual de la entropía de la información. El término entropía de la información es conveniente de utilizar cuando se habla del surgimiento de la información y del ordenamiento de un sistema. Es en este sentido que se utiliza en el Capítulo 2. Destacamos que con la entropía física esta cantidad, en general, no está relacionada.

Entonces, la base para la diferencia entre entropía física e información (tanto cualitativa como cuantitativamente) es la condición de almacenamiento y el gran volumen resultante del espacio de fase de la celda de información en comparación con la elemental.

Es interesante estimar el tamaño de la “reserva”. Ahora es difícil hacer esto en términos generales. Se podría pensar, sin embargo, que en la naturaleza viva se ha alcanzado un tamaño óptimo (es decir, mínimo, pero que satisface los requisitos). Se puede evaluar utilizando datos reales.

En una molécula de ADN, una unidad que contiene dos bits de información es un par de nucleótidos complementarios. Contiene sobre átomos. La entropía asociada con los grados de libertad vibratorios es un bit, o la entropía por bit de información es aproximadamente 60 bits. Por tanto, el volumen del espacio de fase por bit es igual a

Anotación: Se introduce el concepto de entropía. Varios ejemplos muestran cómo se calcula la entropía de una variable aleatoria discreta. Se introduce el concepto de codificación de prefijos. Las tareas de trabajo independiente mejoran la comprensión del material. También muchos estudios matemáticos diferentes.

entropía d.s.v. - este es el número promedio mínimo de bits que deben transmitirse a través del canal de comunicación sobre el valor actual de un d.s.v determinado.

Veamos un ejemplo (carreras de caballos). En la carrera participan 4 caballos con las mismas posibilidades de ganar, es decir. La probabilidad de que cada caballo gane es 1/4. Presentemos d.r.v. , igual al número del caballo ganador. Aquí . Después de cada carrera, bastará con transmitir dos bits de información sobre el número del caballo ganador a través de los canales de comunicación. Codificamos el número del caballo de la siguiente manera: 1-00, 2-01, 3-10, 4-11. Si introduce una función que devuelve la longitud de un mensaje que codifica un valor determinado, entonces m.o. es la longitud promedio de la codificación de un mensaje. Se puede definir formalmente a través de dos funciones, donde cada valor está asociado con un determinado código de bits, además, uno a uno, y devuelve la longitud en bits para cualquier código específico. En este ejemplo .

Vamos ahora d.s.v. tiene la siguiente distribución

Aquellos. el caballo número 1 es el favorito. Entonces

Codifiquemos los números de los caballos: 1-0, 2-10, 3-110, 4-111, es decir. de modo que cada código no sea un prefijo de otro código (dicha codificación se llama prefijo). En promedio, en 16 carreras, el primer caballo debería ganar 12 de ellas, el segundo - 2, el tercero - 1 y el 4º - 1. Por tanto, la longitud media del mensaje ganador es bits/sim o m.o. . De hecho, ahora viene dada por la siguiente distribución de probabilidad: , , . Por eso,

Entonces, .

Se puede demostrar que no existe codificación más eficiente para los dos casos considerados.

Qué Entropía de Shannon Corresponde a la idea intuitiva de la cantidad de información, se puede demostrar experimentalmente determinando el tiempo medio de las reacciones mentales. El experimento consiste en encender una de las bombillas delante de la persona que se está probando, lo que éste deberá indicar. Se realiza una gran serie de pruebas en las que cada bombilla se enciende con una determinada probabilidad. , donde está el número de la bombilla. Resulta que el tiempo medio necesario para que un sujeto responda correctamente es proporcional al valor de la entropía , y no el número de bombillas, como podría pensarse. En este experimento, se supone que cuanta más información reciba una persona, más tiempo le llevará procesarla y, en consecuencia, reaccionar ante ella.

Ejercicio 13 Encuentre la entropía de d.s.v. y la longitud promedio de cada uno de los códigos dados para este d.s.v.

Ejercicio 14 d.s.v. igual al número de “escudos” que recaían en dos monedas perfectas. Encuentra la entropía. Cree un código mínimo para , calcule su longitud promedio y justifique su minimalidad.

Ejercicio 15 d.s.v. dado por la distribución, Encuentre la entropía de este d.r.v. Cree un código mínimo para , calcule su longitud promedio y justifique su minimalidad.

Ejercicio 16 Acerca de d.s.v. se sabe que sus significados son letras cirílicas. Se realizaron una serie de mediciones secuenciales cuyo resultado fue la “TEORÍA DE LA INFORMACIÓN”. Con base en este resultado, redacte una ley de distribución de probabilidad aproximada para este d.s.v. y estimar la longitud promedio mínima de los códigos para .

Información semántica

En los años 50 del siglo XX aparecieron los primeros intentos de determinar el contenido informativo absoluto de las oraciones en lenguaje natural. Vale la pena señalar que el propio Shannon señaló una vez que el significado de los mensajes no tiene nada que ver con su teoría de la información, que se basa enteramente en los principios de la teoría de la probabilidad. Pero su forma de medir la información con precisión sugirió que podría haber formas de medir con precisión información de un tipo más general, como la información de oraciones en lenguaje natural. Un ejemplo de una de esas medidas es la función , donde está la oración cuyo contenido semántico se mide, -

Entropía de origen del mensaje

Para la mayoría de las fuentes reales, los mensajes tienen diferentes probabilidades. Por ejemplo, en el texto las letras A, O, E se encuentran con relativa frecuencia y Ш, И, rara vez. Según datos experimentales, las letras del alfabeto ruso se caracterizan por probabilidades incondicionales, resumidas en la tabla. 4.1.

Tabla 4.1 Probabilidades incondicionales de letras del alfabeto ruso

	probabilidad		probabilidad		probabilidad

Con diferentes probabilidades, los mensajes transportan diferentes cantidades de información. Al resolver la mayoría de los problemas prácticos, es necesario conocer la cantidad promedio de información por elemento del mensaje. Esta cantidad promedio de información con el número total de elementos del mensaje fuente n y el número de caracteres alfabéticos m es igual a:

(bit/mensaje).

La cantidad se llama entropía de la fuente del mensaje. El término "entropía" proviene de la termodinámica, donde caracteriza la incertidumbre promedio del estado de un sistema de moléculas de una sustancia. En la teoría de la información, este término fue introducido en 1948 por el científico estadounidense K. Shannon y definido aún más estrictamente por los matemáticos soviéticos A.Ya. Khinchin y A.N. Kolmogórov. Físicamente, la entropía expresa la incertidumbre promedio del estado de la fuente del mensaje y es una información objetiva característica de la fuente. La entropía siempre es positiva y toma su valor máximo para mensajes igualmente probables:

.

El valor mínimo de entropía corresponde al caso en que una de las probabilidades es , y el resto son iguales a cero, es decir hay total certeza.

Para una fuente con mensajes dependientes, la entropía también se calcula como la expectativa matemática de la cantidad de información por elemento de estos mensajes. Cabe señalar que el valor de entropía obtenido en este caso será menor que para una fuente de mensajes independientes. Esto se desprende del hecho de que, en presencia de dependencia del mensaje, la incertidumbre de elección disminuye y, en consecuencia, la entropía disminuye. Entonces, en el texto después de la combinación "cht", lo más probable es que la tercera letra sea "o" y es poco probable que "zh" o "b" aparezcan como tercera letra. En promedio, la combinación de "qué" transmite menos información que estas letras individualmente.

Las fuentes binarias se utilizan más ampliamente en sistemas de transmisión de información discreta. Las fuentes binarias se caracterizan por la transmisión de sólo dos mensajes posibles. Además, si la probabilidad de transmisión de uno de ellos es , entonces la probabilidad de transmisión del otro .

Determinemos la entropía de la fuente binaria. De la fórmula (4.2) obtenemos:

El gráfico de dependencia (4.4) se presenta en la Fig. 4.1. Como se desprende del gráfico, la entropía de una fuente binaria varía de cero a uno. La entropía es cero cuando la probabilidad de transmitir uno de los símbolos es cero o uno, es decir sólo se transmite un mensaje. Recibir un único mensaje posible no proporciona ninguna información nueva. La entropía de una fuente binaria será máxima si existe la mayor incertidumbre, es decir . Al mismo tiempo .

Redundancia de fuentemensajes

Los mensajes de origen redundante son mensajes que contienen una cantidad pequeña, a veces nula, de información. La presencia de redundancia significa que algunos mensajes pueden no transmitirse a través de un canal de comunicación, pero pueden restaurarse en la recepción utilizando conexiones estadísticas conocidas. Esto es lo que hacen al transmitir telegramas, excluyendo del texto conjunciones, preposiciones y signos de puntuación, ya que se reconstruyen fácilmente según el significado del telegrama basándose en las reglas conocidas de construcción de frases.

La redundancia se cuantifica mediante el coeficiente de redundancia:

,

¿Dónde está la entropía de la fuente? – máxima entropía de una fuente con un alfabeto de mensajes.

La redundancia en la mensajería tiene sus lados positivos y negativos. Un aumento de la redundancia conduce a un aumento del tiempo de transmisión de mensajes y a una carga excesiva en los canales de comunicación. Durante un cierto período de tiempo, se transmite por el canal menos información de la posible; Por tanto, una de las tareas de la teoría de la información y la tecnología de codificación es la tarea de reducir la redundancia.

Sin embargo, al aumentar la redundancia, resulta posible aumentar la inmunidad al ruido de la transmisión de mensajes. Así, la redundancia de texto le permite corregir errores individuales o restaurar letras o incluso palabras faltantes en un telegrama. En ruso y en todos los idiomas europeos, la redundancia, teniendo en cuenta todas las dependencias estadísticas de las letras, es aproximadamente la misma. Se formó como resultado de una práctica social a largo plazo basada en los requisitos para corregir la distorsión de palabras y frases bajo la influencia de diversos factores que interfieren. Para los sistemas de comunicación, se establece un valor de redundancia de compromiso que garantiza la velocidad y confiabilidad especificadas en la transmisión de mensajes.

Rendimiento del origen del mensaje

Para fuentes de mensajes de tarifa fija, un parámetro importante es su rendimiento, definido por la expresión:

[bits/s],

¿Dónde está el intervalo de tiempo para transmitir un mensaje elemental?

El significado físico de productividad es la cantidad de información producida por una fuente en promedio por unidad de tiempo (un segundo) de su funcionamiento continuo.

¿Cómo podemos medir la información en un evento? ¿Cuánta información nos proporciona un evento? Respondamos estas preguntas con ejemplos.

Ejemplo F.1

Imagínese una persona sentada en una habitación. Mirando por la ventana, puede ver claramente el sol brillando. Si en este momento recibe un mensaje (evento) de un vecino que le dice "Que tengas un buen día", ¿este mensaje contiene alguna información? ¡Por supuesto que no! La persona ya está segura de que es de día y hace buen tiempo. El mensaje no reduce la incertidumbre de su conocimiento.

Ejemplo F.2

Imaginemos que una persona compró un billete de lotería. Si un amigo llama para decir que ganó el primer premio, ¿ese mensaje (evento) contiene información? ¡Por supuesto que sí! El mensaje contiene mucha información porque la probabilidad de ganar el primer premio es muy pequeña. El receptor del mensaje se sorprende.

Los dos ejemplos anteriores muestran que existe una relación entre la utilidad de un evento y las expectativas del receptor. Si el receptor está distante del evento cuando ocurre el evento, el mensaje contiene mucha información; de lo contrario no es así. En otras palabras, el contenido informativo de un mensaje está inversamente relacionado con la probabilidad de que ese mensaje ocurra. Si un evento es muy probable, no contiene ninguna información (Ejemplo F.1); si es poco probable, contiene mucha información (Ejemplo F.2).

F.2. entropía

Supongamos que S es la distribución de probabilidad de un número finito de eventos (consulte el "Apéndice D"). La entropía o incertidumbre en S se puede definir como:

¿Dónde está el posible resultado de una prueba? Tenga en cuenta que si. P(s) = 0, entonces asumiremos que P(S) x es igual a 0 para evitar dividir por 0.

Ejemplo F.3

Supongamos que lanzamos una moneda justa. Los resultados son "cara" y "cruz", cada uno con una probabilidad de 1/2, y esto significa

H (S) = P(caras) x + P (cruces) x H (S) = (1/2) x = 1 bit

Este ejemplo muestra que el resultado de lanzar una moneda justa nos da 1 bit de información (incertidumbre). Con cada lanzamiento, no sabemos cuál será el resultado porque las dos posibilidades son igualmente probables.

Ejemplo F.4

Supongamos que lanzamos una moneda incorrecta (dañada). Los resultados de cara y cruz son P (cara) = 3/4 y P (cruz) = 1/4. Esto significa que

H(S) = (3/4) x + (1/4) x = 0,8 bits

Este ejemplo muestra que el resultado de lanzar una moneda equivocada nos da sólo 0,8 bits de información (incertidumbre). cantidad de información hay menos que cantidad de información en el ejemplo F.3 porque esperamos obtener cara más veces que cruz.

Ejemplo F.5

Ahora supongamos que lanzamos una moneda completamente injusta en la que el resultado siempre es cara, P (cara) = 1 y P (cruz) = 0. Entropía en este caso

H (S) = (1) x + (0) x = (1) x (0) + (0) = 0

No hay información (incertidumbre) en este experimento. Sabemos que el resultado siempre será cara; entropía - 0.

Entropía máxima

Se puede demostrar que para una distribución de probabilidad con norte posibles resultados, la entropía máxima sólo se puede lograr si todas las probabilidades son iguales (todos los resultados son igualmente probables). En este caso, la entropía máxima

H máx = log 2 n bits

En otras palabras, la entropía de cualquier conjunto de probabilidades tiene un límite superior, que está determinado por esta fórmula.

Ejemplo F.6

Supongamos que se lanza un dado de seis caras. La entropía de la prueba es igual a

Entropía mínima

Se puede demostrar que para una distribución de probabilidad con norte resultados posibles, la entropía mínima se obtiene si y sólo si siempre se obtiene uno de los resultados. En este caso, la entropía mínima

H mín (S) = 0 bits

En otras palabras, esta fórmula define un límite inferior de entropía para cualquier conjunto de probabilidades.

La entropía de cualquier conjunto de probabilidades está entre 0 poco y log2n poco donde norte - número de resultados posibles.

Interpretación de la entropía

Se puede considerar la entropía como el número de bits que pueden representar cada resultado de un conjunto de probabilidades cuando los resultados son igualmente probables. Por ejemplo, cuando una posible distribución aleatoria tiene ocho resultados posibles, cada resultado se puede representar como tres bits (000 a 111). Cuando obtenemos el resultado de un experimento, podemos decir que hemos obtenido 3 bits de información. La entropía de este conjunto de probabilidades también es de 3 bits (ln 2 8 = 3).

Entropía conjunta

Cuando tenemos dos conjuntos de distribuciones de probabilidad, S 1 y S 2 , podemos definir la entropía conjunta H (S 1 , S 2 ) como

Entropía condicional

A menudo necesitamos conocer la incertidumbre de la distribución de probabilidad S 1, sujeto a obtener un resultado que esté determinado por la incertidumbre de la distribución de probabilidad S 2. Se llama entropía condicional H (S 1 | S 2). Se puede demostrar que

H (S 1 | S 2) = H (S 1, S 2) - H (S 2) bit

Otras proporciones

Presentamos aquí sin pruebas algunas otras relaciones de entropía:

1. H (S 1, S 2) = H (S2 | S 1) + H (S 1) = H (S 1 | S 2) + H (S2)
2. H (S1, S2)<= H (S 1) + H (S2)
3. H (S1 | S2)<= H (S 1)
4. H (S1, S2, S3) = H (S1 | S2, S3) + H (S1, S3)

La segunda y tercera relaciones son válidas si S 1 y S 2 son estadísticamente independientes.

Ejemplo F.7

En criptografía, si P es la distribución de probabilidad del texto plano, C es la distribución de probabilidad del texto cifrado y K es la distribución de probabilidad de las claves, entonces H(K|C) puede interpretarse como la dificultad de un ataque de texto cifrado en qué conocimiento de C puede conducir al conocimiento de K.

Ejemplo F.8

En criptografía, dado un texto plano y una clave, un algoritmo de cifrado determinista produce un texto cifrado único, lo que significa H(C | K, P) = 0. Además, dado el texto cifrado y el algoritmo de descifrado de claves, se crea un texto sin formato único, lo que significa H(P | K, C) = 0. Si se le da el texto cifrado y el texto sin formato, la clave también se define de forma única: H(K|P,C) = 0.

Secreto perfecto

En criptografía, si P, K y C son los espacios de muestreo de probabilidad del texto sin formato, el texto cifrado y la clave respectivamente, entonces tenemos H(P|C)<=H (P) . Это может быть интерпретировано так: неопределенность P данного C меньше или равна неопределенности P . В большинстве криптографических систем, справедливо отношение H (P|C)< H (P) , что означает, что перехват зашифрованного текста уменьшает знание, которое требуется для того, чтобы найти исходный текст. Криптографическая система обеспечивает secreto perfecto, si se observa la relación H (P|C)=H (P), esto significa que la incertidumbre del texto fuente y el texto cifrado dado es la misma incertidumbre del texto fuente. En otras palabras, Eve no obtiene ninguna información al interceptar el texto cifrado; todavía tiene que explorar todas sus opciones.

Un sistema criptográfico proporciona un secreto perfecto si H (P | C) = H (P) .

Ejemplo F.9

En conferencias anteriores dijimos que desechable cifrar bloc garantiza un secreto perfecto. Demostremos este hecho utilizando las relaciones de entropía anteriores. Supongamos que el alfabeto es solo 0 y 1. Si la longitud del mensaje es L, se puede demostrar que la clave y el texto cifrado constan de 2 L caracteres, donde cada carácter es igualmente probable. Por lo tanto, H(K) = H(C) = log 2 2 L = L. Usando las relaciones obtenidas en el ejemplo F.8 y el hecho de que H(P, K) = H(P) + H(K) porque P y K son independientes, tenemos

H (P, K, C) = H (C|P, K) + H (P, K) = H (P, K) = H (P) + H (K) H (P, K, C) = H (K|P, C) + H (P, C) = H (P, C) = H (P|C) + H (C)

Esto significa que H(P|C) = H(P)

Ejemplo F.10

Shannon demostró que en un sistema criptográfico, si (1) las claves ocurren con la misma probabilidad y (2) hay una clave única para cada texto sin formato y cada texto cifrado, entonces el sistema criptográfico proporciona un secreto perfecto. La prueba utiliza el hecho de que en este caso las distribuciones de probabilidad de las claves, el texto plano y el texto cifrado son del mismo tamaño.

F.3. Entropía del lenguaje

Es interesante relacionar el concepto de entropía con lenguajes naturales como el inglés. En este apartado tocamos algunos puntos relacionados con la entropía del lenguaje.

Entropía de un lenguaje arbitrario.

Supongamos que un idioma usa N letras y todas las letras tienen la misma probabilidad de aparecer. Podemos decir que la entropía de este lenguaje es H L = log 2 N . Por ejemplo, si utilizamos veintiséis letras mayúsculas (de la A a la Z) para transmitir nuestro mensaje, entonces