Arduino: algoritmo di compressione leggero per archiviare i dati in EEPROM

Question

Voglio archiviare una grande quantità di dati sul mio Arduino con un ATmega168 / ATmega328 microcontrollore, ma sfortunatamente ci sono solo 256 & nbsp; KB / 512 & nbsp; KB di archiviazione EEPROM.

La mia idea è quella di utilizzare un algoritmo di compressione per ridurre le dimensioni. Ma bene, la mia conoscenza degli algoritmi di compressione è piuttosto bassa e la mia ricerca di librerie pronte per l'uso non è riuscita.

Quindi, c'è un buon modo per ottimizzare le dimensioni di archiviazione?

Answer 1

Potresti dare un'occhiata all'algoritmo LZO , progettato per essere leggero. Non so se ci sono implementazioni per il sistema AVR, ma potrebbe essere qualcosa che potresti implementare da solo.

Tuttavia, potresti essere un po 'male informato sulla quantità di memoria disponibile in EEPROM sul tuo chip; secondo la scheda tecnica ho le dimensioni EEPROM sono:

ATmega48P: 256
ATmega88P: 512
ATmega168P: 512
ATmega256P: 1024

Nota che questi valori sono in byte , non in KB come menzionato nella tua domanda. Questo non è, in alcun modo, un "carico di merda".

Answer 2

Gli AVR hanno al massimo solo pochi kilobyte di EEPROM e pochissimi hanno molti più di 64 KB di Flash (nessun Arduinos standard).

Se hai bisogno di archiviare qualcosa e di modificarlo raramente, ad esempio un'immagine, puoi provare a usare Flash in quanto c'è molto più spazio lì con cui lavorare. Per immagini semplici, una certa codifica RLE grezza farebbe molto.

La compressione di qualcosa di più casuale, ad esempio dati registrati, audio, ecc., richiederà un enorme sovraccarico per l'AVR, avrai più fortuna a ottenere un chip EEPROM seriale per contenere questi dati. Il sito di Arduino ha una pagina su interfacciamento con un chip 64K , che suona. Se vuoi qualcosa di più, guarda l'interfaccia con una scheda SD con SPI, ad esempio in questo scudo audio

Answer 3

Uno studio della NASA qui (Postscript)

Un ripubblicare l'articolo del 1989 su LZW qui

Semplifica e esegui l'analisi del costo / pagamento dell'aggiunta della compressione. Ciò include tempo e fatica, complessità, utilizzo delle risorse, comprimibilità dei dati, ecc.

Answer 4

Un algoritmo simile a LZSS sarebbe probabilmente una buona scelta per una piattaforma integrata. Sono semplici algoritmi e non richiedono molta memoria.

LZS è uno che conosco. Utilizza un dizionario da 2 kB per compressione e decompressione (il dizionario è il più recente da 2 kB del flusso di dati non compresso). ( LZS è stato brevettato da HiFn , tuttavia, per quanto ne so, tutti i brevetti sono scaduti.)

Ma vedo che un ATmega328 , utilizzato su Arduinos recenti , ha solo 512 byte a 2 KB SRAM, quindi forse anche LZS è troppo grande per questo. Sono sicuro che potresti utilizzare una variante con un dizionario più piccolo, ma non sono sicuro di quali rapporti di compressione otterrai.

Answer 5

Il metodo descritto nel documento & # 8220; Algoritmi di compressione dei dati per dispositivi a vincolo energetico nelle reti con tolleranza di ritardo & # 8221; potrebbe essere eseguito su un ATmega328 .

Riferimento: C. Sadler e M. Martonosi, & # 8220; Algoritmi di compressione dei dati per dispositivi a vincolo energetico nelle reti a tolleranza ritardata, & # 8221; Atti della conferenza ACM sui sistemi di sensori integrati in rete (SenSys) 2006, novembre 2006. .pdf. S-LZW Fonte per MSPGCC: slzw.tar.gz. Aggiornato il 10 marzo 2007.

Answer 6

Potresti anche dare un'occhiata a LZJB , essendo molto corto, semplice e leggero.

Inoltre, FastLZ potrebbe valere la pena dare un'occhiata. Ottiene rapporti di compressione migliori rispetto a LZJB e presenta requisiti di memoria piuttosto minimi per la decompressione:

Answer 7

Se vuoi solo rimuovere alcuni zero ripetuti o simili, usa Codifica run-length Le sequenze di byte ripetute verranno memorizzate come:

<mark><byte><count>

È un algoritmo semplicissimo, che probabilmente puoi codificare in poche righe di codice.

Answer 8

Un'EEPROM esterna (ad esempio tramite I2C) non è un'opzione? Anche se si utilizza un algoritmo di compressione, il lato negativo è che la dimensione dei dati che è possibile archiviare nella EEPROM interna potrebbe non essere più determinata in modo semplice. E, naturalmente, se intendi davvero kBYTES, allora considera una SDCard collegata alla SPI ... Ci sono alcuni file system open source compatibili compatibili con FAT in rete.