8051 data compression

Hi Martin,

What are you wanting to compress? We used a lookup table to compress common html tags and sequences that repeated often. It's only really suitable if the data does not contain all 256 possible values - you use the spare values to index a lookup table.

Regards - Rocky

It's not possible to give a good answer without knowing what it is that you are trying to compress. The solutions will differ for, say, long strings of ASCII numeric characters versus image bitmaps versus pseudo-random values. There are general purpose compression routines, such as gzip, zip, arc, zoo (remember that one?) but general purpose means a larger code size.

What about a lossy compression? For some applications, keeping only "the important stuff" and discarding the rest is perfectly acceptable.

In addition to code size, how constrained are you with respect to variable storage? Are you limited to 128 bytes in the register space or do you have many KBs of external memory for table generation?

--
Rich Webb   Norfolk, VA

google for "zlib" Its free, in C and _not_ fast.

Run length encoding can be very compact & RAM frugal - some versions will fit into a CPLD. If you can tune, to match repeat patterns on your data, it can get even more efficent. All compressions are very data-content dependant, and truly random data compresses the worst.

-jg

I should have been more precise. Trying to consider compressing a Virtex II bitfile. Storage would be in an external SPI FLASH device. The uncompressed bit image is just under 512K-bytes. In looking at it, there are lots of 0x00 bytes. It should compress very well.

Lossy compression is not an option, obvisouly.

-Martin

To add to that, obviously I only need to expand with the 8051. The compression part would be done on a PC.

-Martin

Then the PC can search for the best RLC lengths, and you can even look at adding a simple table, if the best pattern repeats are > 1 byte. Unused portions of the bitstream should compress very well.

In the most vanilla form, RLC is Value.Count, but it can expand to TableIndex.Count, expecially if a PC can do the leg-work, of checking the table values, and patterns. ZIP the bitstream, and you have a target of what complex compression gives.

-jg

I'm familiar with plain RLC. I need to research the table approach.

I did do that. 500K compressed down to 100K~112K, depending on settings. I think that I can safely assume that allocating 250K of FLASH should do the job. I need to allow for changes in code affecting compression. That's the toughest aspect of this to guestimate.

I am going to post to comp.arch.fpga to see if anyone might have statistics on attainable compression ratios for different design densities.

Thanks,

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
x@y
where
x  =  "martineu"
y = "pacbell.net"

Then the easiest is probably good old run length encoding (google for RLE).

is probably the easiest place to start; several links to pseudo-code there. Wikipedia also has a short entry on it.

--
Rich Webb   Norfolk, VA

A recent article in Circuit Cellar (November 2004), mentions just that, includingdetails of the compression algorithm used.

ted

Doesn't the Virtix II support compressed bitstreams? I've never used Xilinx devices myself, but Altera devices all support compression in the devices themselves. Trying to further compress the compressed bitstreams is a waste of effort, as you are never going to get better than a percent or two. Also, if you are using encrypted bitsteams, you are not going to be able to compress them effectively.

Yes. However, the form of compression they use is to match repeating frames, which isn't ideal in non-trivial designs. Almost anything else should produce better results.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Martin Euredjian

To send private email: x@y where x = "martineu" y = "pacbell.net"

Hi Dear: Keil developmmet environmnet give you 56 bit 8051 compression sample for free. Look there, I porteed 128 rigandel public domain algorithms. It took 28k ram

code