¿La forma más eficiente de codificar 2 posiciones entre 0 y 64?

Question

Tengo valores de 64 bits que quiero comprimir explotando el hecho de que solo una parte en el medio contiene datos y antes y después de eso hay ceros.

Digamos que los datos reales tienen una longitud de l bits y están rellenados con n 0s al frente y m 0s al final de manera que n + l + m = 64. En lugar de transmitir / almacenar 64 bits, puedo transmitir l bits más lo que sea necesita codificar la posición de los datos en el intervalo de 64 bits.

Por ejemplo, supongamos que estaba almacenando l, my los bits de datos, luego restablecería el patrón original de 64 bits al leer l, leer l bits de datos, leer my desplazar los bits de datos a la izquierda.

La sobrecarga más pequeña que se me ocurrió es dos veces 6 bits para almacenar dos de l, ny m (cada uno puede estar entre 0 y 64). ¿Es posible reducir ese número?

Answer 1

l puede ser de 0 a 64, así que no envíe l, envíe nym, ya que ambos pueden ser cero y no necesitan subir a 64 (simplemente deben poder agregar a 64).

Los bits l deben comenzar y terminar con un 1, por lo que no es necesario transmitirlos.

enviar 6 bits para n
enviar hasta 6 bits por m (ver más abajo)
calcular l = 64 - (n + m)
si l = 0, el número es 0, no envíe nada más
si l = 1, el número es 1 * 2 ^ m, no envíe nada más
si l = 2, el número es 3 * 2 ^ m, no envíe nada más
envíe el medio l - 2 bits.

Sobrecarga máxima = 10 bits.

La reducción en los bits para m se debe a que
si n > 32 entonces sabes m & Lt; 32, por lo que solo necesita 5 bits
si n > 48 entonces sabes m & Lt; 16, por lo que solo necesita 4 bits
si n > 56 entonces sabes m & Lt; 8, por lo que solo necesita 3 bits
si n > 60 entonces sabes m & Lt; 4, por lo que solo necesita 2 bits
si n = 63 entonces sabes m < 2, por lo que solo necesita 1 bit

Answer 2

Su análisis suena bien para vlaues individuales. Pero si está transmitiendo muchos de estos valores juntos, un algoritmo genérico de codificación de entropía como gzip probablemente funcionará mejor, ya que puede eliminar las cadenas de ceros bastante bien y también explotar redundancias en los datos.

Answer 3

Como ha indicado el problema, no, no puede mejorar la solución que ha propuesto.

Sin embargo, si la distribución de los ceros en los números está sesgada, es posible que pueda obtener una mejor compresión en promedio utilizando códigos Huffman o una técnica similar para representar los recuentos. Otra posibilidad es usar la codificación delta si la distribución cero está fuertemente correlacionada de un valor de 64 bits al siguiente.

En cualquier caso, necesitará usar un número variable de bits para representar los números de ceros. Y si sus suposiciones sobre la asimetría o la correlación resultan ser falsas, puede terminar usando más bits en promedio que si lo hubiera hecho de la manera más simple.

Answer 4

Su solución parece bastante buena.
La codificación de Huffman es otra forma de comprimir sus valores, especialmente si hay valores con gran frecuencia.

No es muy difícil implementarlo, pero puede ser abrumador si no tiene muchos datos para transmitir.

Answer 5

Hay 64 posibles posiciones de inicio n de la secuencia de unos y la longitud de la secuencia l ya no puede ser 64 - n. Entonces hay un

r = sum(n = 0..63, 64 - n) + 1

secuencias en total. El agregado es para una secuencia de todos los ceros. Hacer algunas matemáticas produce lo siguiente.

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

Representar 2081 valores posibles requiere log2(2081) = 11.023 bits. Su sugerencia para codificar la información utilizando dos números de 6 bits que requieren 12 bits en total es, por lo tanto, óptima (bajo el supuesto de distribuciones iguales de todos los valores posibles).