Science and Technology news... :: View topic - Compression for small-memory devices

Thomas Kindler · Guest

Hi!

I>m trying to solve a compression problem for an embedded
microcontroller application. I have an Atmel AVR, which has 16kB of
Flash, but only one kB of RAM.

The microcontroller only needs to decompress the stream from Flash
memory, the compression is done on a normal PC.

The data is highly redundant, so a LZ coding scheme seems optimal.

The problem is, that all the LZ algorithms I saw need some RAM space to
hold a sliding window on the decoder side -- LZ codes the offset/length
pairs in respect to the decoded stream. The repeating blocks of my data
are relatively large (~300 bytes), so I>d need a window of this size,
which I don>t want to spend.

Is there some LZ variant, that doesn>t need a sliding window? I could
imagine an algorithm that codes offset/length pairs for repetitions as
adresses of the compressed data. (i.e. "hey, here comes a part you
already decompressed. just decompress X bytes again, reading from
address Y."). The decompressor would then need to recurse into the
decompression step, instead of just copying from the sliding window.

I don>t have the memory to decompress the whole data, and don>t want to
use a big window of decompressed data. I _can_ spend a few 100 bytes for
a call stack, and I have random access to the compressed data in flash.

Has this been done already? Or is there something I overlooked?

--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte.

Willem · Guest

Thomas Kindler wrote:
) I>m trying to solve a compression problem for an embedded
) microcontroller application. I have an Atmel AVR, which has 16kB of
) Flash, but only one kB of RAM.
)
) The microcontroller only needs to decompress the stream from Flash
) memory, the compression is done on a normal PC.
)
) The data is highly redundant, so a LZ coding scheme seems optimal.

<snip>

) Has this been done already? Or is there something I overlooked?

Perhaps you want a two-pass dictionary-based LZ variant, one that first
calculates an optimal dictionary, and then stores that separately from
the compressed data. Then you can just encode the dictionary entries,
(or perhaps entry/length pairs), and read those from your flash mem.

Then the decompressor can be very simple and will only use a handful of
bytes of RAM.

I don>t know if something like that has been done (although very likely),
but I don>t think it>s that hard to implement. The hardest part would be
to find the optimal dictionary, but you can throw lots of CPU at that.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I>m not paranoid. You all think I>m paranoid, don>t you !
#EOT

Jim Leonard · Guest

On Oct 17, 6:48 am, Thomas Kindler <mail+n...@t-kindler.de> wrote:
[quote]The problem is, that all the LZ algorithms I saw need some RAM space to
hold a sliding window on the decoder side -- LZ codes the offset/length
pairs in respect to the decoded stream. The repeating blocks of my data
are relatively large (~300 bytes), so I>d need a window of this size,
which I don>t want to spend.
[/quote]
Maybe an alternate approach might work for you, like LZ78/LZW?
Instead of a sliding window you>d be building a dictionary, and you
get to flush it when it hits your RAM ceiling. Your compressor on the
PC would monitor the size of the dictionary and flush as necessary.

Then again, if you know the blocks are large, you would need a window/
dictionary at least that large to realize savings. So you *must*
allocate at least a window (LZ77) or dictionary (LZ78) that large to
realize compression.

Otherwise, you>re limited to just statistical coding like Huffman.

John Reiser · Guest

[quote]I have an Atmel AVR, which has 16kB of Flash, but only one kB of RAM.

The microcontroller only needs to decompress the stream from Flash
memory, the compression is done on a normal PC.
[/quote]
Obviously the decompressed data must be sent to a communication device,
or to a function which computes statistics on the decompressed stream, etc.

[quote]Is there some LZ variant, that doesn>t need a sliding window? I could
imagine an algorithm that codes offset/length pairs for repetitions as
adresses of the *compressed* data. (i.e. "hey, here comes a part you
already decompressed. just decompress X bytes again, reading from
address Y."). The decompressor would then need to recurse into the
decompression step, instead of just copying from the sliding window.
[/quote]
The recursive decompressor needs three parameters: backward offset into
compressed data (which must designate either a literal or the *beginning*
of the coding for a repetition), length, and the number of decompressed
bytes to skip at the beginning. The substring that is to be repeated now,
need not start at the beginning of the substring that was repeated before.

--

Thomas Kindler · Guest

Willem wrote:
[quote]Thomas Kindler wrote:
) I>m trying to solve a compression problem for an embedded
) microcontroller application. I have an Atmel AVR, which has 16kB of
) Flash, but only one kB of RAM.
)
) The microcontroller only needs to decompress the stream from Flash
) memory, the compression is done on a normal PC.
)
) The data is highly redundant, so a LZ coding scheme seems optimal.

snip

) Has this been done already? Or is there something I overlooked?

Perhaps you want a two-pass dictionary-based LZ variant, one that first
calculates an optimal dictionary, and then stores that separately from
the compressed data. Then you can just encode the dictionary entries,
(or perhaps entry/length pairs), and read those from your flash mem.

Then the decompressor can be very simple and will only use a handful of
bytes of RAM.
[/quote]
That could work.. I want to use the algorithm to compress music data
(very similar to a MIDI stream). In a first preprocessing step, I
already do deltas between successive notes, and get a stream that
consists mainly of zeros, occasional bigger numbers, and some runs of
constant values (for volume changes, slides, etc..). I also read about
the move-to-first transform, which could convert the constant runs to
zero runs.

The entries in the dictionary would ideally end up as small pieces of
music that can be chained together by the decompressor.

[quote]I don>t know if something like that has been done (although very likely),
but I don>t think it>s that hard to implement.
The hardest part would be to find the optimal dictionary, but you can
throw lots of CPU at that.
[/quote]
Does anyone know a good algorithm for this? Perhaps I>ll just try plain
LZW and store the dictonary statically in front of the compressed data.

--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte
www.microsoft-hellhounds.de, www.bredobrothers.de

Ross Ridge · Guest

Thomas Kindler <mail+news@t-kindler.de> wrote:
[quote]I don>t have the memory to decompress the whole data, and don>t want to
use a big window of decompressed data. I _can_ spend a few 100 bytes for
a call stack, and I have random access to the compressed data in flash.
[/quote]
I>d use a (non-adapative) static dictionary based algorithim, with the
precomputed dictionary stored in Flash. Since your input and output is
always the same you don>t need to use any RAM at all.

Ross Ridge

--
l/ // Ross Ridge -- The Great HTMU
[oo][oo] rridge@csclub.uwaterloo.ca
-()-/()/ http://www.csclub.uwaterloo.ca/~rridge/
db //


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Compression Forum
Page 1 of 1