Lo que sería una buena (de) rutina de compresión para este escenario

Question

Necesito una rutina de descompresión RÁPIDO optimizado para entorno de recursos restringida como sistemas embebidos en (datos hexadecimales) binarios que tiene las características siguientes:

1. de datos es de 8 bits (byte) orientado (bus de datos es de 8 bits de ancho).
2. Los valores de byte no lo hacen variar de manera uniforme desde 0 - 0xFF, pero tienen una distribución de Poisson (curva de campana) en cada conjunto de datos
.
3. conjunto de datos se fija en avanzado (para ser quemados en Flash), y cada conjunto rara vez es> 1 - 2 MB

La compresión puede tomar tanto como el tiempo necesario, pero la descompresión de un byte debe tomar 23US en el peor de los casos con la cantidad de memoria mínima, ya que se llevará a cabo en un entorno de recursos restringidos como un sistema embebido (3Mhz - núcleo de 12Mhz, 2k RAM bytes).

¿Cuál sería una buena rutina de descompresión?

La codificación de longitud básica parece demasiado derrochador - Puedo ver de inmediato que la adición de un setion cabecera a los datos comprimidos para poner en uso los valores de bytes utilizados para representar los patrones repetidos daría un rendimiento fenomenal

Con yo que sólo invirtió unos minutos, seguramente debe existir ya mucho mejores algoritmos de personas que aman este material?

Me gustaría tener un poco de "listo para funcionar" ejemplos de probar en un PC para que pueda comparar el rendimiento vis-a-vis a RLE básica.

Answer 1

Las dos soluciones que utilizan cuando el rendimiento es la única preocupación:

• lzo tiene una licencia GPL.
• liblzf disponga de una licencia BSD.
• miniLZO.tar.gz Esto es LZO, simplemente embalados de nuevo en una versión 'minified' que es mejor para el desarrollo integrado.

Ambos están muy rápido cuando se descomprime. He encontrado que LZO creará datos comprimidos ligeramente más pequeño que en la mayoría de los casos liblzf. Usted tendrá que hacer sus propios puntos de referencia para las velocidades, pero yo considero que son "esencialmente iguales". Ambos son años luz más rápido que zlib, aunque ni comprime así (como era de esperar).

LZO, en particular miniLZO, y liblzf son excelentes para objetivos embebidos.

Answer 2

Si usted tiene una distribución preestablecida de valores que significa el propability de cada valor se fija sobre todos los conjuntos de datos, puede crear una codificación Huffman con los códigos fijos (el árbol de código no ha de ser incrustado en los datos).

En función de los datos, que iba a tratar con los códigos de Huffman fijos o LZ77 (ver enlaces de Brian).

Answer 3

Bueno, los dos principales algoritmos que vienen a la mente son Huffman y LZ .

La primera, básicamente, sólo crea un diccionario. Si se restringe el tamaño del diccionario suficiente, que debe ser bastante rápido ... pero no espere una compresión muy buena.

Los últimos trabajos de la adición de nuevo referencias a la repetición de partes de archivo de salida. Esto probablemente llevaría muy poca memoria para funcionar, excepto que usted tendría que utilizar cualquiera de los archivos de E / S para leer las copias de referencias o almacenar una parte de los datos recientemente leído en la memoria RAM.

Sospecho LZ es su mejor opción, si las secciones repetidas tienden a estar cerca el uno al otro. Huffman funciona por tener un diccionario de elementos repetidos con frecuencia, como usted ha mencionado.

Answer 4

Dado que esto parece ser de audio, me vería en cualquiera PCM diferencial o ADPCM, o algo similar, lo que reducirá a 4 bits / muestra sin mucha pérdida de calidad.

Con la implementación más básica diferencial PCM, que acaba de almacenar una diferencia de 4 bits firmado entre la muestra actual y un acumulador, y agrega que la diferencia con el acumulador y pasar a la siguiente muestra. Si la diferencia fuera de [-8,7], tiene que sujetar el valor y puede tomar varias muestras para el acumulador para ponerse al día. La decodificación se usa muy rápido, casi sin memoria, simplemente añadiendo cada valor al acumulador y dar salida a un acumulador en la siguiente muestra.

Una pequeña mejora con respecto a DPCM básica para ayudar al acumulador de ponerse al día más rápido cuando la señal se hace más fuerte y tono más alto es el uso de una tabla de consulta para decodificar los valores de 4 bits a un rango no lineal más grande, donde siguen siendo 1 Aparte cerca de cero, pero aumentar en incrementos más grandes hacia los límites. Y / o se puede reservar uno de los valores para cambiar un multiplicador. Decidir cuándo usarlo hasta el codificador. Con estas mejoras, puede lograr una mejor calidad o salirse con 3 bits por muestra en lugar de 4.

Si el dispositivo tiene un μ-ley o ley A ADC no lineal, se puede obtener una calidad comparable a 11-12 bits con muestras de 8 bits. O es probable que pueda hacerlo usted mismo en su decodificador. http://en.wikipedia.org/wiki/M-law_algorithm

Es posible que haya virutas baratas por ahí que ya hacen todo esto para usted, dependiendo de lo que está haciendo. No he mirado en ninguna.

Answer 5

Debe probar diferentes algoritmos de compresión, ya sea con una herramienta de software de compresión con la línea de comandos o una biblioteca de compresión donde se pueden probar diferentes algoritmos. Utilizar los datos típicos para su aplicación. Entonces sabe qué algoritmo se mejor se ajusta a sus necesidades.

Answer 6

He utilizado zlib en sistemas embebidos para un cargador de arranque que descomprime la imagen de aplicación a la RAM en el arranque. La licencia es bien permisiva, sin sentido GPL. Se hace una sola llamada malloc, pero en mi caso simplemente se sustituye esto con un talón que devuelve un puntero a un bloque estático, y un talón libre correspondiente (). Hice esto mediante el control de su uso asignación de memoria para obtener el tamaño correcto. Si su sistema puede soportar asignación dinámica de memoria, entonces es mucho más simple.

http://www.zlib.net/