Quale potrebbe essere una buona (de) routine di compressione per questo scenario

Question

Ho bisogno di una routine di decompressione VELOCE ottimizzata per l'ambiente risorsa limitata come sistemi embedded su (dati esadecimali) binarie che ha seguenti caratteristiche:

1. I dati sono 8bit (byte) orientato (bus dati largo 8 bit).
2. I valori di byte Non variare in maniera uniforme da 0 - 0xFF, ma hanno una distribuzione di Poisson (curva a campana) in ogni DataSet
.
3. Dataset è fissato in anticipo (da bruciare in Flash) e ogni set è raramente> 1 - 2 MB

La compressione può prendere tutto il tempo necessario, ma la decompressione di un byte dovrebbe prendere 23US nel peggiore dei casi con il minimo ingombro di memoria in quanto sarà fatto su un ambiente di risorsa limitata come un sistema embedded (3Mhz - nucleo 12MHz, 2k byte di RAM).

Quale potrebbe essere una buona routine di decompressione?

La codifica base Run-length sembra troppo dispendioso - posso vedere subito che l'aggiunta di un'intestazione setion ai dati compressi di mettere a frutto i valori di byte non utilizzati per rappresentare i modelli spesso ripetuto darebbe prestazioni fenomenali

Con me che ha investito solo pochi minuti, sicuramente ci deve già esistere algoritmi molto meglio da persone che amano questa roba?

Mi piacerebbe avere un po ' "pronto ad andare" esempi per provare su un PC in modo che possa confrontare le prestazioni vis-a-vis a RLE di base.

Answer 1

Le due soluzioni che uso quando le prestazioni sono l'unica preoccupazione:

• LZO Ha un GPL License.
• liblzf ha una licenza BSD.
• miniLZO.tar.gz Questo è LZO, proprio reimballata in una versione 'minified' che è più adatto per lo sviluppo embedded.

Entrambi sono molto veloce quando la decompressione. Ho scoperto che LZO creerà dati compressi leggermente più piccolo rispetto liblzf nella maggior parte dei casi. Avrai bisogno di fare i propri punti di riferimento per velocità, ma io li considerano "sostanzialmente uguale". Entrambi sono anni luce più veloce di zlib, anche se nessuno comprime così (come ci si aspetterebbe).

LZO, in particolare miniLZO, e liblzf sono entrambi eccellenti per i target embedded.

Answer 2

Se si ha una distribuzione prefissato di valori che indica il propability di ciascun valore è fissato su tutti i set di dati, è possibile creare una codifica Huffman con codici fissi (l'albero codice non deve essere incorporato nei dati).

A seconda dei dati, mi piacerebbe provare Huffman con codici fissi o LZ77 (vedi link di Brian).

Answer 3

Bene, i due principali algoritmi che vengono in mente sono Huffman e LZ .

La prima fondamentalmente solo crea un dizionario. Se si limita la dimensione del dizionario a sufficienza, dovrebbe essere abbastanza veloce ... ma non aspettatevi molto buona compressione.

Quest'ultimo funziona, aggiungendovi riferimenti a ripetere porzioni di file di output. Questo probabilmente sarebbe voluto molto poca memoria per funzionare, se non che si avrebbe bisogno sia di file utilizzare per i / o per leggere il back-riferimenti o conservare un pezzo di dati letto di recente nella RAM.

Ho il sospetto LZ è la scelta migliore, se le sezioni ripetute tendono ad essere vicini l'uno all'altro. Huffman funziona avendo un dizionario di elementi spesso ripetuti, come lei ha ricordato.

Answer 4

Dal momento che questo sembra essere l'audio, mi guardo PCM differenziale o ADPCM, o qualcosa di simile, che ridurrà a 4 bit / campione senza troppa perdita di qualità.

Con l'implementazione di base differenziale PCM, basta memorizzare una differenza firmato 4 bit tra il campione attuale e un accumulatore, e aggiungere che differenza per l'accumulatore e passare al campione successivo. Se la differenza è al di fuori di [-8,7], è necessario bloccare il valore e potrebbero essere necessari diversi campioni per l'accumulatore per recuperare. La decodifica è molto veloce utilizza quasi alcun ricordo, solo l'aggiunta di ogni valore all'accumulatore ed emettere l'accumulatore come il campione successivo.

Un piccolo miglioramento rispetto DPCM di base per aiutare l'accumulatore recuperare più velocemente quando il segnale diventa più forte e il passo più alto è quello di utilizzare una tabella di ricerca per decodificare i valori 4 bit per una gamma non lineare più grandi, dove sono ancora 1 parte vicino allo zero, ma aumentare a grandi incrementi verso i limiti. E / o si potrebbe riservare uno dei valori per attivare o disattivare un moltiplicatore. Decidere quando usarlo fino al codificatore. Con questi miglioramenti, è possibile ottenere una migliore qualità o farla franca con 3 bit per campione invece di 4.

Se il dispositivo ha un non-lineare μ-legge o A-legge ADC, è possibile ottenere una qualità paragonabile a 11-12 bit con 8 campioni bit. Oppure si può probabilmente fare da soli nel vostro decoder. http://en.wikipedia.org/wiki/M-law_algorithm

Ci potrebbe essere poco costosi chip là fuori che già fare tutto questo per voi, a seconda di quello che stai facendo. Non ho guardato in qualsiasi.

Answer 5

Si dovrebbe provare diversi algoritmi di compressione sia con un software di compressione con riga di comando o di una libreria di compressione in cui è possibile provare diversi algoritmi. Utilizzare i dati tipici per la vostra applicazione. Poi si sa che l'algoritmo è migliore-montaggio per le vostre esigenze.

Answer 6

Ho usato zlib nei sistemi embedded per un bootloader che decomprime l'immagine richiesta di RAM su start-up. La licenza è ben permissiva, al dialogo GPL. Si fa una singola chiamata malloc, ma nel mio caso ho semplicemente sostituito questo con uno stub restituito un puntatore a un blocco statico, e uno stub libera corrispondente (). Ho fatto questo attraverso il monitoraggio suo utilizzo allocazione di memoria per ottenere la giusta dimensione. Se il sistema può supportare allocazione dinamica della memoria, allora è molto più semplice.

http://www.zlib.net/