Connect with us

fast universal compression scheme and its implementation in VHDL

Discussion in 'Electronic Basics' started by Jens Mander, Jun 10, 2005.

Scroll to continue with content
  1. Jens Mander

    Jens Mander Guest

    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?
     
  2. Guest

    Have a look at bzip2:
    bzip2 compresses files using the Burrows-Wheeler block sorting text
    compression algorithm, and Huffman coding. Compression is generally
    considerably better than that achieved by more conventional
    LZ77/LZ78-based compressors, and approaches the performance of the PPM
    family of statistical compressors.

    It's the most effective I have stumbled upon in terms of bytes saved so far. I
    have however not made any deep research into this ;)
    It can however take considerble amount of processor time. Thus a good candidate
    for hardware implementation.
     
  3. I too am interested in this and I would be interested to see results of Jens
    findings and work in this area if he decides to work on it and publish it.

    Josh
     
  4. Zak

    Zak Guest

    It is again surpassed by 7-zip (www.7-zip.org). They use an improved
    LZ77, but also have a PPM option available. It compresses more but is
    slower. See http://www.cs.tut.fi/~warp/ArchiverComparison/

    Again, source code is available.


    Thomas
     
  5. "Jens Mander" ...
    AFAIK compression on such small blocks is often inefficient. The rest
    strongly depends on the type of data.

    Try to find a good and simple compression for the bitstreams used to program
    FPGA's. Then publish a link to your thesis and the algorithm here please.

    Arie de Muynck
     
  6. colin

    colin Guest

    interesting project, it depends what your emphasis is, ie if its useful to
    have very high savings when its posible even if it doesnt hapen very often
    or wether its just necesary to make moderate savings as much of the time as
    possible. you might make very big savings on certain types of data, but the
    greater extent to wich u can recognise reduntant patterns etc increases
    overhead so that it becomes worse for data that is more random (or even
    already compressed).

    if you have fixed diferent rate fifos you have to evelauate what needs to
    happen if or when your data is uncompresable.

    the obvious thing to my mind is things like reducing strings of all zero (or
    al ones) bits or bytes, or alternate such bytes as seem to apear a lot in
    wave files etc, even strings of any identical bytes etc, if you take this
    further you end up with the usual huffman encoding. (wich many of the other
    schemes are based on).

    it depends how much you can do in hardware, but you could try and do many
    different such simple proceses in parallel on the data and see wich ends up
    with most compresion. this is probably the key to taking advantage of the
    hardware aproach ?

    many file storage systems use compresion to reduce blocks of data (i think
    ntfs uses 16k blocks). I was once interested in high level compresion, even
    going as far as finding identical files and eliminating the redundancy.

    Colin =^.^=
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-