¡Muchas gracias!
"El propósito de este curso es prepararlo para su futuro técnico".
Hola Habr. Recuerda el fantástico artículo. (+219, 2588 marcadores, 429k lecturas)?
Entonces Hamming (sí, sí, autocontrol y autocorrección) ) hay un todo , escrito a partir de sus conferencias. Lo traducimos, porque el hombre dice lo que piensa.
Este es un libro no sólo sobre TI, es un libro sobre el estilo de pensamiento de personas increíblemente geniales. “No es sólo un impulso al pensamiento positivo; describe las condiciones que aumentan las posibilidades de realizar un gran trabajo”.
Gracias a Andrey Pakhomov por la traducción.
La teoría de la información fue desarrollada por C. E. Shannon a finales de los años 1940. La dirección de Bell Labs insistió en que la llamara "Teoría de la comunicación" porque... este es un nombre mucho más preciso. Por razones obvias, el nombre "Teoría de la Información" tiene un impacto mucho mayor en el público, razón por la cual Shannon lo eligió, y es el nombre que conocemos hasta el día de hoy. El nombre en sí sugiere que la teoría trata sobre la información, lo que la hace importante a medida que nos adentramos en la era de la información. En este capítulo, abordaré varias conclusiones principales de esta teoría, no proporcionaré evidencia estricta, sino más bien intuitiva, de algunas disposiciones individuales de esta teoría, para que comprenda qué es realmente la "teoría de la información" y dónde puede aplicarla. y donde no.
En primer lugar, ¿qué es “información”? Shannon equipara información con incertidumbre. Eligió el logaritmo negativo de la probabilidad de un evento como medida cuantitativa de la información que se recibe cuando ocurre un evento con probabilidad p. Por ejemplo, si te digo que el clima en Los Ángeles está nublado, entonces p está cerca de 1, lo que realmente no nos da mucha información. Pero si digo que en Monterey llueve en junio, habrá incertidumbre en el mensaje y contendrá más información. Un evento confiable no contiene ninguna información, ya que log 1 = 0.
Veamos esto con más detalle. Shannon creía que la medida cuantitativa de información debería ser una función continua de la probabilidad de un evento p, y para eventos independientes debería ser aditiva: la cantidad de información obtenida como resultado de la ocurrencia de dos eventos independientes debería ser igual a la cantidad de información obtenida como resultado de la ocurrencia de un evento conjunto. Por ejemplo, el resultado de una tirada de dados y de una moneda generalmente se tratan como eventos independientes. Traduzcamos lo anterior al lenguaje de las matemáticas. Si I (p) es la cantidad de información contenida en un evento con probabilidad p, entonces para un evento conjunto que consta de dos eventos independientes x con probabilidad p1 e y con probabilidad p2 obtenemos
(x e y son eventos independientes)
Esta es la ecuación funcional de Cauchy, verdadera para todos los p1 y p2. Para resolver esta ecuación funcional, suponga que
p1 = p2 = p,
esto da
Si p1 = p2 y p2 = p entonces
etc. Ampliando este proceso usando el método estándar para exponenciales, para todos los números racionales m/n se cumple lo siguiente
De la supuesta continuidad de la medida de información, se deduce que la función logarítmica es la única solución continua a la ecuación funcional de Cauchy.
En teoría de la información, es común tomar la base del logaritmo como 2, por lo que una elección binaria contiene exactamente 1 bit de información. Por tanto, la información se mide mediante la fórmula.
Hagamos una pausa y comprendamos lo que sucedió arriba. En primer lugar, no definimos el concepto de “información”; simplemente definimos la fórmula para su medida cuantitativa.
En segundo lugar, esta medida está sujeta a incertidumbre y, aunque es razonablemente adecuada para máquinas (por ejemplo, sistemas telefónicos, radio, televisión, computadoras, etc.), no refleja actitudes humanas normales hacia la información.
En tercer lugar, esta es una medida relativa, depende del estado actual de sus conocimientos. Si observa una secuencia de "números aleatorios" de un generador de números aleatorios, asume que cada número siguiente es incierto, pero si conoce la fórmula para calcular los "números aleatorios", el siguiente número se conocerá y, por lo tanto, no se conocerá. contener información.
Así pues, la definición de información de Shannon es apropiada para las máquinas en muchos casos, pero no parece encajar en la comprensión humana de la palabra. Es por esta razón que la “Teoría de la Información” debería haberse llamado “Teoría de la Comunicación”. Sin embargo, es demasiado tarde para cambiar las definiciones (que dieron a la teoría su popularidad inicial y que todavía hacen que la gente piense que esta teoría trata sobre "información"), por lo que tenemos que vivir con ellas, pero al mismo tiempo debemos comprender claramente qué tan lejos está la definición de información de Shannon de su significado comúnmente utilizado. La información de Shannon trata de algo completamente diferente: la incertidumbre.
Aquí hay algo en lo que pensar cuando proponga cualquier terminología. ¿En qué medida una definición propuesta, como la definición de información de Shannon, concuerda con su idea original y en qué medida es diferente? Casi no existe un término que refleje exactamente su visión previa de un concepto, pero en última instancia, es la terminología utilizada la que refleja el significado del concepto, por lo que formalizar algo a través de definiciones claras siempre introduce algo de ruido.
Considere un sistema cuyo alfabeto consta de símbolos q con probabilidades pi. En este caso cantidad promedio de información en el sistema (su valor esperado) es igual a:
Esto se llama entropía del sistema con distribución de probabilidad {pi}. Usamos el término "entropía" porque la misma forma matemática aparece en termodinámica y mecánica estadística. Por eso el término “entropía” crea a su alrededor una cierta aura de importancia que, en última instancia, no está justificada. ¡La misma forma matemática de notación no implica la misma interpretación de símbolos!
La entropía de la distribución de probabilidad juega un papel importante en la teoría de la codificación. La desigualdad de Gibbs para dos distribuciones de probabilidad diferentes pi y qi es una de las consecuencias importantes de esta teoría. Entonces debemos demostrar que
La prueba se basa en un gráfico obvio, Fig. 13.I, lo que demuestra que
y la igualdad se logra solo cuando x = 1. Apliquemos la desigualdad a cada término de la suma del lado izquierdo:
Si el alfabeto de un sistema de comunicación consta de q símbolos, entonces tomando la probabilidad de transmisión de cada símbolo qi = 1/q y sustituyendo q, obtenemos de la desigualdad de Gibbs
Figura 13.I
Esto significa que si la probabilidad de transmitir todos los símbolos q es la misma e igual a - 1 / q, entonces la entropía máxima es igual a ln q; de lo contrario, se cumple la desigualdad.
En el caso de un código únicamente decodificable, tenemos la desigualdad de Kraft.
Ahora bien, si definimos pseudoprobabilidades
donde por supuesto = 1, que se sigue de la desigualdad de Gibbs,
y aplicamos un poco de álgebra (recuerde que K ≤ 1, por lo que podemos eliminar el término logarítmico y tal vez fortalecer la desigualdad más adelante), obtenemos
donde L es la longitud promedio del código.
Por lo tanto, la entropía es el límite mínimo para cualquier código carácter por símbolo con una longitud promedio de palabra de código L. Este es el teorema de Shannon para un canal libre de interferencias.
Consideremos ahora el teorema principal sobre las limitaciones de los sistemas de comunicación en los que la información se transmite como un flujo de bits independientes y hay ruido. Se entiende que la probabilidad de transmisión correcta de un bit es P > 1/2, y la probabilidad de que el valor del bit se invierta durante la transmisión (ocurrirá un error) es igual a Q = 1 - P. Por conveniencia, Supongamos que los errores son independientes y que la probabilidad de un error es la misma para cada bit enviado, es decir, hay "ruido blanco" en el canal de comunicación.
La forma en que tenemos un largo flujo de n bits codificados en un mensaje es la extensión n-dimensional del código de un bit. Determinaremos el valor de n más adelante. Considere un mensaje que consta de n bits como un punto en un espacio de n dimensiones. Dado que tenemos un espacio n-dimensional, y por simplicidad asumiremos que cada mensaje tiene la misma probabilidad de ocurrencia, hay M mensajes posibles (M también se definirá más adelante), por lo tanto, la probabilidad de que cualquier mensaje se envíe es
(remitente)
Anexo 13.II
A continuación, consideremos la idea de capacidad del canal. Sin entrar en detalles, la capacidad del canal se define como la cantidad máxima de información que se puede transmitir de manera confiable a través de un canal de comunicación, teniendo en cuenta el uso de la codificación más eficiente. No hay duda de que se puede transmitir más información a través de un canal de comunicación que su capacidad. Esto se puede demostrar para un canal simétrico binario (que usamos en nuestro caso). La capacidad del canal, al enviar bits, se especifica como
donde, como antes, P es la probabilidad de que no haya error en ningún bit enviado. Al enviar n bits independientes, la capacidad del canal viene dada por
Si estamos cerca de la capacidad del canal, entonces debemos enviar casi esta cantidad de información para cada uno de los símbolos ai, i = 1, ..., M. Considerando que la probabilidad de ocurrencia de cada símbolo ai es 1 / M, obtenemos
cuando enviamos cualquiera de M mensajes ai igualmente probables, tenemos
Cuando se envían n bits, esperamos que ocurran nQ errores. En la práctica, para un mensaje que consta de n bits, tendremos aproximadamente nQ errores en el mensaje recibido. Para n grande, variación relativa (variación = ancho de distribución, )
la distribución del número de errores será cada vez más estrecha a medida que n aumente.
Entonces, desde el lado del transmisor, tomo el mensaje ai para enviar y dibujo una esfera alrededor de él con un radio
que es ligeramente mayor en una cantidad igual a e2 que el número esperado de errores Q, (Figura 13.II). Si n es lo suficientemente grande, entonces existe una probabilidad arbitrariamente pequeña de que aparezca un punto de mensaje bj en el lado del receptor que se extienda más allá de esta esfera. Esbocemos la situación tal como la veo desde el punto de vista del transmisor: tenemos radios cualesquiera desde el mensaje transmitido ai hasta el mensaje recibido bj con una probabilidad de error igual (o casi igual) a la distribución normal, alcanzando un máximo de nQ. Para cualquier e2 dado, existe un n tan grande que la probabilidad de que el punto resultante bj esté fuera de mi esfera es tan pequeña como se desee.
Ahora veamos la misma situación desde su punto de vista (Fig. 13.III). En el lado del receptor hay una esfera S(r) del mismo radio r alrededor del punto recibido bj en un espacio n-dimensional, de modo que si el mensaje recibido bj está dentro de mi esfera, entonces el mensaje ai enviado por mí está dentro de tu esfera.
¿Cómo puede ocurrir un error? El error puede ocurrir en los casos descritos en la siguiente tabla:
Figura 13.III
Aquí vemos que si en la esfera construida alrededor del punto recibido hay al menos un punto más correspondiente a un posible mensaje no codificado enviado, entonces se produjo un error durante la transmisión, ya que no se puede determinar cuál de estos mensajes se transmitió. El mensaje enviado está libre de errores sólo si el punto correspondiente está en la esfera y no hay otros puntos posibles en el código dado que estén en la misma esfera.
Tenemos una ecuación matemática para la probabilidad de error Pe si se envió el mensaje ai
Podemos descartar el primer factor en el segundo término, tomándolo como 1. Así obtenemos la desigualdad
Obviamente, la
por lo tanto
volver a aplicar al último término de la derecha
Si n es lo suficientemente grande, el primer término puede tomarse tan pequeño como se desee, digamos menor que algún número d. Por lo tanto tenemos
Ahora veamos cómo podemos construir un código de sustitución simple para codificar M mensajes que constan de n bits. Al no tener idea de cómo construir exactamente un código (aún no se habían inventado los códigos de corrección de errores), Shannon eligió la codificación aleatoria. Lanza una moneda por cada uno de los n bits del mensaje y repite el proceso para M mensajes. En total, es necesario realizar nM lanzamientos de moneda, por lo que es posible
diccionarios de códigos que tienen la misma probabilidad ½nM. Por supuesto, el proceso aleatorio de creación de un libro de códigos significa que existe la posibilidad de duplicados, así como puntos de código que estarán cerca unos de otros y, por lo tanto, serán una fuente de probables errores. Se debe demostrar que si esto no sucede con una probabilidad mayor que cualquier nivel de error pequeño elegido, entonces el n dado es lo suficientemente grande.
¡El punto crucial es que Shannon promedió todos los libros de códigos posibles para encontrar el error promedio! Usaremos el símbolo Av[.] para indicar el valor promedio sobre el conjunto de todos los libros de códigos aleatorios posibles. Promediar sobre una constante d, por supuesto, da una constante, ya que para promediar cada término es igual a todos los demás términos de la suma,
que se puede aumentar (M–1 va a M)
Para cualquier mensaje dado, al promediar todos los libros de códigos, la codificación recorre todos los valores posibles, por lo que la probabilidad promedio de que un punto esté en una esfera es la relación entre el volumen de la esfera y el volumen total del espacio. El volumen de la esfera es
donde s=Q+e2 <1/2 y ns debe ser un número entero.
El último término de la derecha es el mayor de esta suma. Primero, estimemos su valor usando la fórmula de Stirling para factoriales. Luego veremos el coeficiente decreciente del término que está delante de él, tengamos en cuenta que este coeficiente aumenta a medida que nos movemos hacia la izquierda, por lo que podemos: (1) restringir el valor de la suma a la suma de la progresión geométrica con este coeficiente inicial, (2) expandir la progresión geométrica de ns términos a un número infinito de términos, (3) calcular la suma de una progresión geométrica infinita (álgebra estándar, nada significativo) y finalmente obtener el valor límite (para un número suficientemente grande norte):
Observe cómo apareció la entropía H(s) en la identidad binomial. Tenga en cuenta que la expansión de la serie de Taylor H(s)=H(Q+e2) da una estimación obtenida teniendo en cuenta sólo la primera derivada e ignorando todas las demás. Ahora armemos la expresión final:
donde
Todo lo que tenemos que hacer es elegir e2 tal que e3 < e1, y entonces el último término será arbitrariamente pequeño, siempre que n sea lo suficientemente grande. En consecuencia, el error PE promedio puede obtenerse tan pequeño como se desee con la capacidad del canal arbitrariamente cercana a C.
Si el promedio de todos los códigos tiene un error suficientemente pequeño, entonces al menos un código debe ser adecuado y, por lo tanto, existe al menos un sistema de codificación adecuado. Este es un resultado importante obtenido por Shannon: "El teorema de Shannon para un canal ruidoso", aunque cabe señalar que lo demostró para un caso mucho más general que para el canal simétrico binario simple que utilicé. Para el caso general, los cálculos matemáticos son mucho más complicados, pero las ideas no son tan diferentes, por lo que muy a menudo, usando el ejemplo de un caso particular, se puede revelar el verdadero significado del teorema.
Criticemos el resultado. Hemos repetido repetidamente: "Para n suficientemente grande". ¿Pero qué tamaño tiene n? ¡Muy, muy grande si realmente desea estar cerca de la capacidad del canal y estar seguro de la transferencia de datos correcta! De hecho, es tan grande que tendrá que esperar mucho tiempo para acumular un mensaje con suficientes bits para codificarlo más tarde. En este caso, el tamaño del diccionario de código aleatorio será simplemente enorme (después de todo, dicho diccionario no se puede representar en una forma más corta que una lista completa de todos los Mn bits, a pesar de que n y M son muy grandes).
Los códigos de corrección de errores evitan esperar un mensaje muy largo y luego codificarlo y decodificarlo a través de libros de códigos muy grandes porque evitan los libros de códigos en sí y utilizan cálculos ordinarios en su lugar. En teoría simple, dichos códigos tienden a perder la capacidad de acercarse a la capacidad del canal y aún mantener una tasa de error baja, pero cuando el código corrige una gran cantidad de errores, funcionan bien. En otras palabras, si asigna cierta capacidad del canal a la corrección de errores, entonces deberá utilizar la capacidad de corrección de errores la mayor parte del tiempo, es decir, se debe corregir una gran cantidad de errores en cada mensaje enviado; de lo contrario, desperdiciará esta capacidad.
Al mismo tiempo, ¡el teorema demostrado anteriormente todavía no carece de sentido! Muestra que los sistemas de transmisión eficientes deben utilizar esquemas de codificación inteligentes para cadenas de bits muy largas. Un ejemplo son los satélites que han volado más allá de los planetas exteriores; A medida que se alejan de la Tierra y del Sol, se ven obligados a corregir cada vez más errores en el bloque de datos: algunos satélites utilizan paneles solares, que proporcionan unos 5 W, otros utilizan fuentes de energía nuclear, que proporcionan aproximadamente la misma potencia. La baja potencia de la fuente de alimentación, el pequeño tamaño de las antenas parabólicas del transmisor y el tamaño limitado de las antenas parabólicas en la Tierra, la enorme distancia que debe recorrer la señal, todo esto requiere el uso de códigos con un alto nivel de corrección de errores para construir un sistema de comunicación eficaz.
Volvamos al espacio n-dimensional que usamos en la prueba anterior. Al discutirlo, demostramos que casi todo el volumen de la esfera se concentra cerca de la superficie exterior; por lo tanto, es casi seguro que la señal enviada se ubicará cerca de la superficie de la esfera construida alrededor de la señal recibida, incluso con una distancia relativamente baja. pequeño radio de tal esfera. Por tanto, no es sorprendente que la señal recibida, después de corregir un número arbitrariamente grande de errores, nQ, resulte arbitrariamente cercana a una señal sin errores. La capacidad de enlace que discutimos anteriormente es la clave para comprender este fenómeno. Tenga en cuenta que esferas similares construidas para códigos Hamming de corrección de errores no se superponen entre sí. La gran cantidad de dimensiones casi ortogonales en el espacio n-dimensional muestra por qué podemos colocar M esferas en el espacio con poca superposición. Si permitimos una superposición pequeña, arbitrariamente pequeña, que puede conducir sólo a un pequeño número de errores durante la decodificación, podemos obtener una colocación densa de esferas en el espacio. Hamming garantizó un cierto nivel de corrección de errores, Shannon, una baja probabilidad de error, pero al mismo tiempo mantuvo el rendimiento real arbitrariamente cerca de la capacidad del canal de comunicación, lo que los códigos Hamming no pueden hacer.
La teoría de la información no nos dice cómo diseñar un sistema eficiente, pero sí señala el camino hacia sistemas de comunicación eficientes. Es una herramienta valiosa para construir sistemas de comunicación de máquina a máquina, pero, como se señaló anteriormente, tiene poca relevancia en la forma en que los humanos se comunican entre sí. Simplemente se desconoce hasta qué punto la herencia biológica se parece a los sistemas de comunicación técnica, por lo que actualmente no está claro cómo se aplica la teoría de la información a los genes. No tenemos más remedio que intentarlo, y si el éxito nos muestra la naturaleza mecánica de este fenómeno, entonces el fracaso señalará otros aspectos importantes de la naturaleza de la información.
No nos desviemos demasiado. Hemos visto que todas las definiciones originales, en mayor o menor medida, deben expresar la esencia de nuestras creencias originales, pero se caracterizan por cierto grado de distorsión y por tanto no son aplicables. Tradicionalmente se acepta que, en última instancia, la definición que utilizamos define en realidad la esencia; pero esto sólo nos dice cómo procesar las cosas y de ninguna manera nos transmite ningún significado. El enfoque postulacional, tan favorecido en los círculos matemáticos, deja mucho que desear en la práctica.
Ahora veremos un ejemplo de pruebas de coeficiente intelectual donde la definición es tan circular como usted quiera y, como resultado, engañosa. Se crea una prueba que se supone mide la inteligencia. Luego se revisa para que sea lo más consistente posible, y luego se publica y, con un método simple, se calibra para que la “inteligencia” medida resulte tener una distribución normal (en una curva de calibración, por supuesto). Todas las definiciones deben volver a comprobarse, no sólo cuando se proponen por primera vez, sino también mucho más tarde, cuando se utilizan en las conclusiones extraídas. ¿Hasta qué punto son apropiados los límites definitorios para el problema que se está resolviendo? ¿Con qué frecuencia las definiciones dadas en un entorno se aplican en entornos muy diferentes? ¡Esto sucede con bastante frecuencia! En las humanidades, que inevitablemente encontrarás en tu vida, esto sucede con más frecuencia.
Así, uno de los propósitos de esta presentación de la teoría de la información, además de demostrar su utilidad, fue advertirle de este peligro, o mostrarle exactamente cómo utilizarla para obtener el resultado deseado. Durante mucho tiempo se ha observado que las definiciones iniciales determinan lo que se encuentra al final, en mucha mayor medida de lo que parece. Las definiciones iniciales requieren mucha atención por su parte, no sólo en cualquier situación nueva, sino también en áreas con las que ha estado trabajando durante mucho tiempo. Esto le permitirá comprender hasta qué punto los resultados obtenidos son una tautología y no algo útil.
La famosa historia de Eddington habla de personas que pescaban en el mar con una red. Después de estudiar el tamaño de los peces que capturaron, determinaron el tamaño mínimo de pez que se encuentra en el mar. Su conclusión fue impulsada por el instrumento utilizado, no por la realidad.
To be continued ...
¿Quién quiere ayudar con la traducción, el diseño y la publicación del libro? Escriba un mensaje personal o un correo electrónico. [email protected]
Por cierto, también hemos lanzado la traducción de otro libro interesante: )
Estamos buscando especialmente aquellos que ayudarán a traducir (transferencia durante 10 minutos, los primeros 20 ya han sido tomados)
Contenido del libro y capítulos traducidos.
- Introducción al arte de hacer ciencia e ingeniería: aprender a aprender (28 de marzo de 1995)
- "Fundamentos de la revolución digital (discreta)" (30 de marzo de 1995)
- "Historia de las Computadoras - Hardware" (31 de marzo de 1995)
- "Historia de las Computadoras - Software" (4 de abril de 1995)
- "Historia de las Computadoras - Aplicaciones" (6 de abril de 1995)
- "Inteligencia artificial - Parte I" (7 de abril de 1995)
- "Inteligencia artificial - Parte II" (11 de abril de 1995)
- "Inteligencia Artificial III" (13 de abril de 1995)
- "Espacio n-dimensional" (14 de abril de 1995)
- "Teoría de la codificación: la representación de la información, parte I" (18 de abril de 1995)
- "Teoría de la codificación: la representación de la información, parte II" (20 de abril de 1995)
- "Códigos de corrección de errores" (21 de abril de 1995)
- "Teoría de la Información" (25 de abril de 1995)
- "Filtros digitales, Parte I" (27 de abril de 1995)
- "Filtros digitales, parte II" (28 de abril de 1995)
- "Filtros digitales, parte III" (2 de mayo de 1995)
- "Filtros digitales, parte IV" (4 de mayo de 1995)
- "Simulación, Parte I" (5 de mayo de 1995)
- "Simulación, Parte II" (9 de mayo de 1995)
- "Simulación, Parte III" (11 de mayo de 1995)
- "Fibra Óptica" (12 de mayo de 1995)
- "Instrucción asistida por computadora" (16 de mayo de 1995)
- "Matemáticas" (18 de mayo de 1995)
- "Mecánica Cuántica" (19 de mayo de 1995)
- "Creatividad" (23 de mayo de 1995). Traducción:
- "Expertos" (25 de mayo de 1995)
- "Datos poco fiables" (26 de mayo de 1995)
- “Ingeniería de Sistemas” (30 de mayo de 1995)
- "Obtienes lo que mides" (1 de junio de 1995)
- (Junio 2, 1995) traducir en trozos de 10 minutos
- Hamming, "Usted y su investigación" (6 de junio de 1995).
¿Quién quiere ayudar con la traducción, el diseño y la publicación del libro? Escriba un mensaje personal o un correo electrónico. [email protected]
Fuente: habr.com