fast universal compression scheme and its implementation in VHDL

Hi folks,

my name is Jens and I am student of the Technical University Berlin. Through my course of study in microelectronics VHDL design is becoming my favorite hobby. My other interests are signal processing and compression in general. Lately I purchased an FPGA Evalution board second-hand (guess where?) and I am now starting my first "private" implementations. Just to give you a short intro... ;-)

I am interested in implementing compression algorithms using VHDL on an FPGA. I want to build a data transmission system that compresses portions of the incoming data (not the whole data but "frames" of like 800 bytes) on-the-fly. In my search for a fast (i.e. real-time capable at a "desired" data rate of - let's say - 300 MHZ?) "universal" compression scheme I came across the following stepping stones:

- is there any free example code for compression algorithms available in VHDL to get an overview and a first impression of implementation complexity?

- what would you think are the most promising algorithms for my purpose (i.e. when statistics and semantics of the input data are unknown), first of all I thought of delta encoding, sorted RLE, LZ, ....?

- as the input data is unknown the álgorithm must be lossless, reducing redundancy (if possible), not irrelevancy. what are the theoretical limits of "universal" compression, not emphazizing one particular statistical property (like similar by values in succession)?

- what is meant by the keyword "systolic implementations" and "pipeling" in that particular context? I came across that very often lately

- what if my code gains different compression ratios for consecutive data portions? surely a FIFO can decouple input and output rate but eventually the FIFO will underflow?

Thanks for you help + support in advance, any comments, hints and help is appreciated!

Bye Jens

P.S.: I'm looking for the standard works "Sayood, Khalid: Introduction to data compression, Academic Press, 199x or 200x" and/or ". Salomon: Data Compression, Springer-Verlag, New York, 200x". Are there any sources of an electronic copy (ps, pfd, etc.) or transcriptions?

Reply to
Jens Mander
Loading thread data ...

Hi folks,

my name is Jens and I am student of the Technical University Berlin. Through my course of study in microelectronics VHDL design is becoming my favorite hobby. My other interests are signal processing and compression in general. Lately I purchased an FPGA Evalution board second-hand (guess where?) and I am now starting my first "private" implementations. Just to give you a short intro... ;-)

I am interested in implementing compression algorithms using VHDL on an FPGA. I want to build a data transmission system that compresses portions of the incoming data (not the whole data but "frames" of like 800 bytes) on-the-fly. In my search for a fast (i.e. real-time capable at a "desired" data rate of - let's say - 300 MHZ?) "universal" compression scheme I came across the following stepping stones:

- is there any free example code for compression algorithms available in VHDL to get an overview and a first impression of implementation complexity?

- what would you think are the most promising algorithms for my purpose (i.e. when statistics and semantics of the input data are unknown), first of all I thought of delta encoding, sorted RLE, LZ, ....?

- as the input data is unknown the álgorithm must be lossless, reducing redundancy (if possible), not irrelevancy. what are the theoretical limits of "universal" compression, not emphazizing one particular statistical property (like similar by values in succession)?

- what is meant by the keyword "systolic implementations" and "pipeling" in that particular context? I came across that very often lately

- what if my code gains different compression ratios for consecutive data portions? surely a FIFO can decouple input and output rate but eventually the FIFO will underflow?

Thanks for you help + support in advance, any comments, hints and help is appreciated!

Bye Jens

P.S.: I'm looking for the standard works "Sayood, Khalid: Introduction to data compression, Academic Press, 199x or 200x" and/or ". Salomon: Data Compression, Springer-Verlag, New York, 200x". Are there any sources of an electronic copy (ps, pfd, etc.) or transcriptions?

Reply to
Jens Mander

Hi Jens,

I am not an expert in this field, but I think there is no guarenteed compression-rate at all for real random data, so the answer for your question would be 0%. Otherwise you could compress something, then compress it again and again.... However, I think in real life data there is often some kind of redundancy.

Regards,

Thomas

Reply to
Thomas Entner

Wow 300 Mhz, what kind of fgpa are you targetting ?

Not sure, open-cores.net or maybe some application note from Xilinx or Altera.

There is no limit ... If the input stream is a "true random", with maximum entropy then you just can't compress it at all. But all real-life data have not a maximum entropy and some kind of redundancy can be found. But there is no guarantee ..

There must be some kind of "flow control" implemented in either your input / output or both. So that you core can for example says : "No more input data for the moment" or "Sorry, can't output more data for now, wait till I say otherwise". It can be just a single line like "in_rdy" to say you're ready for new data input or "out_valid". Ideally you would have handshake line on both port and a fifo so that your core can be inserted in any comm line. (just my 2 cents)

Sylvain

Reply to
Sylvain Munaut

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.