¿Es el concepto de "bit" en la programación de computadoras similar al concepto de "bit" en la teoría de la información?

Hasta hoy sabía que un bit es una variable o un espacio en la memoria que puede contener un valor de Uno (alto) o Cero (bajo). Este es el concepto que aprendí al estudiar programación de computadoras, microprocesador o bus de datos, etc.

Pero después de comenzar el curso sobre teoría de la información, descubrí que ese bit se expresa como el contenido de información de un símbolo en el mensaje. Esto se calcula tomando el logaritmo (base 2) de la inversa de la probabilidad de ocurrencia del símbolo.

¿Son estos dos conceptos iguales? Por un lado, un bit es una variable que puede almacenar cero o uno. Por otro lado, un bit es la incertidumbre asociada con uno de los dos símbolos con una probabilidad de ocurrencia de 0.5. Entonces, ¿1 bit en programación de computadora o código ASCII significa 1 bit en contenido de información de fuente o teoría de la información?

Una pequeña edición: aquí hay una cosa que encuentro problemas para entender este tema. Ver, en la transferencia de datos de alfabetos ingleses, si usamos código ASCII, básicamente representamos cada símbolo con 8 bits. Supongamos que es 00000000 para a, 00000001 para b, etc. Así que esencialmente estamos asignando 8 niveles de cuantización para cada símbolo.

Pero cuando la teoría de la información entra en juego, tomamos en cuenta la probabilidad de cada símbolo. 'E' tiene la frecuencia más alta, donde 'Z' tiene la más baja. Entonces, el contenido promedio de información se reduce a 3 o 4 bits, ¿verdad?

Mi libro dice: 'La entropía o el contenido de información promedio es el número promedio mínimo de bits requerido para representar cada muestra sin distorsión'. Entonces, en este caso, para una transferencia de datos eficiente, ¿estamos creando un máximo de cuatro niveles de cuantificación para cada símbolo? Porque, en promedio, llevan información por valor de 4 bits. Si es así, ¿no es lo mismo en teoría de la información que en programación de computadoras, transferencia de datos o código ASCII, etc.?

Probablemente entiendas que claramente soy un novato aquí: p

information-theory Benjamín
fuente

Una cosa para agregar a la respuesta de MBaz es que la escala del "bit" en la teoría de la información es tal que es lo mismo que "bits" en la memoria de la computadora. Hay otras unidades de información en Shannon IT. lo que sea que multiplique la función . si es que escala la función de registro, entonces está en bits.

I (m) = - C \log (P (m))

$I(m) = -C\log(P(m))$

C = \frac{1}{\log (2)}

$C= \frac{1}{\log(2)}$

I (m)

$I(m)$

robert bristow-johnson

@ robertbristow-johnson, ese es un buen punto.

MBaz

La codificación de Huffman intenta alcanzar el límite teórico de información asignando menos bits a símbolos frecuentes. Este es un proceso aproximado ya que las frecuencias verdaderas son desconocidas y el número de bits debe seguir siendo un número entero. La codificación aritmética funciona mejor y se las arregla para empacar usando un número fraccional de bits por símbolos.

Yves Daoust

las frecuencias (digamos, de caracteres, si se trata de un archivo de texto) se pueden conocer contando. También se pueden agrupar diferentes símbolos (con un número fraccionario de bits) en un solo mensaje compuesto que tiene un número entero de bits. pero siempre será menos eficiente que el límite teórico.

Robert Bristow-Johnson

Respuestas:

No son lo mismo, pero están relacionados. En particular, si observa una memoria de computadora que contiene bits de "computadora", donde cada bit puede considerarse aleatorio e independiente de todos los demás bits, y hay aproximadamente el 50% de ceros, entonces la memoria también contiene aproximadamente "teoría de la información "bits" $M$ $M$

Por supuesto, este no suele ser el caso: los bits de la computadora generalmente están correlacionados y no son aleatorios de manera uniforme. Por eso se pueden comprimir. Los programas de compresores como LZW ("codificadores de origen" en el lenguaje de la teoría de la información) funcionan, en cierto sentido, haciendo que cada bit de la computadora contenga un bit de información.

Editado para agregar: este ejemplo puede aclarar la distinción. Considere una fuente sin memoria con dos salidas, y , con probabilidad 0.5 para cada una. Claramente, la información en cada mensaje es un bit (información), pero su longitud es de tres bits (computadora). Un codificador de origen, como el algoritmo Huffman, codificará fácilmente los mensajes a y , comprimiendo la salida de origen. Puede extrapolar fácilmente este ejemplo a una fuente que produce texto codificado en ASCII. $m_1=000$ $m_2=001$ $c_1=0$ $c_2=1$

Tenga en cuenta que, en el caso de los idiomas escritos en general y el inglés en particular, nadie sabe cuál es la entropía de origen real, porque no hay un modelo para ello. Es por eso que hay concursos para la mejor compresión de grandes cuerpos de texto; nadie está realmente seguro de cuál es el algoritmo de compresión óptimo para el inglés.

MBaz
fuente

Gracias MBaz Pero aquí hay una cosa que encuentro problemas para entender este tema. Ver, en la transferencia de datos de alfabetos ingleses, si usamos código ASCII, básicamente representamos cada símbolo con 8 bits. Supongamos que es 00000000 para a, 00000001 para b, etc. Así que esencialmente estamos asignando 8 niveles de cuantización para cada símbolo. Pero cuando la teoría de la información entra en juego, tomamos en cuenta la probabilidad de cada símbolo. 'E' tiene la frecuencia más alta, donde 'Z' tiene la más baja. Entonces, el contenido promedio de información se reduce a 3 o 4 bits, ¿verdad?

benjamin

@benjamin, eso es correcto, y esa es la razón por la cual el texto se puede comprimir tanto. Contiene mucha menos información que la cantidad de bits (de computadora) utilizados para representarlo.

MBaz

Hola, publiqué el comentario en la sección de respuestas en detalle, ya que se estaba haciendo demasiado largo. Debe haber olvidado borrarlo. por cierto, eso básicamente significa que los símbolos de texto contienen información de 3 a 4 bits, mientras que usamos 8 bits para transferirlos, ¿verdad? Por lo tanto, contienen bits inútiles o redundancia. Entonces, para una transferencia de datos eficiente, podemos codificarlos usando menos bits y así comprimirlos. Eso significa que podemos crear niveles de cuantificación menores para codificarlos. Anteriormente creamos 8 niveles de cuantización, pero ahora 4 niveles de cuantización serían suficientes.

benjamin

Un nivel de cuantización es 1 bit de dígito binario. Así que ahora podemos usar niveles de cuantificación menores o menos bits de dígitos binarios. Entonces, ¿no estamos considerando bits de dígitos binarios y bits de cuantificación como básicamente la misma cosa? En aquel entonces, utilizamos 8 bits para transmitir un solo símbolo. Pero ahora sabemos que los símbolos valen solo 4 bits de información en promedio. Entonces los estamos enviando usando 4 niveles de cuantización o 4 bits de dígitos binarios, porque llevan 4 bits de información. De hecho, intenté aprender un poco sobre la codificación de Hoffman por mi cuenta, pero aquí es donde realmente me quedé estancado.

benjamin

@benjamin, creo que estás en el camino correcto aquí. Piénselo de esta manera, cuando el texto (o cualquier archivo o fecha de la computadora) esté perfectamente comprimido, cada bit de la computadora llevará un bit de información.

MBaz

El bit es una unidad de medida y las cantidades múltiples se miden en bits. No es que la programación y la teoría de la información signifiquen cosas diferentes. Es que la memoria y el contenido de información representan cantidades conceptualmente diferentes.

Por ejemplo, podemos tomar la contraseña '' 123456 ''. Si está codificado en UTF-8, requiere 6 * 8 = 48 bits de memoria. Para fines del mundo real, su contenido de información es de aproximadamente 10 bits. Bit significa lo mismo en ambos casos, la cantidad que se mide es lo que es diferente. Si comprime la contraseña, la cantidad de memoria que necesita disminuye, pero el contenido de la información no cambiará.

Una analogía: las cantidades físicas como la gravedad y la fuerza electromagnética se miden en Newtons pero representan diferentes tipos de interacciones. Puedes ver empíricamente que la unidad Newton representa la misma idea en ambos casos: la gravedad y la fuerza electromagnética pueden equilibrarse entre sí (levitación magnética).

Espero que eso ayude :)

martinkunev
fuente

En el bus de datos, en teoría podemos hacerlo mejor de lo que dice la teoría de la información. Sé cómo construir un circuito que me permita enviar 8 bits en paralelo por 6 cables. Esto implica un truco con diodos y resistencias de subida / bajada que permite usar los tres estados de no encendido de un cable digital para transmitir información. Con 3 estados de 6 líneas, obtengo 729 estados posibles, lo que me permite transportar EOF, INT, CLK y desconectado en el canal principal y todavía tengo mucho espacio (esto solo usa 518 de los 729 estados).

Joshua
fuente

Ahora eso es solo redefinir el canal y agregar memoria;)

estrella brillante

Lo que dijo Trevor. Usted asume implícitamente que el "teórico de la información" solo usa el canal una vez que la duración de cada símbolo envía 1 información de H o L, pero si agrega estados, está haciendo algo que no es lo mismo :)

Marcus Müller