constant bitrate approach with lossless data compression on an FPGA

Discussion in 'VHDL' started by Kurt Kaiser, Nov 10, 2006.

  1. Kurt Kaiser

    Kurt Kaiser Guest

    Hi folks,

    I've implemented a lossless data compression (kind of experimental
    proprietary solution) algorithm in VHDL. For buffering the non-constant data
    output I've chosen a FIFO in the encoder and decoder although I'm not very
    happy with that. Because of the high variance it will happen sooner or later
    that the FIFOs run under or over, respectively. Is there a common practice
    or trick of "enforcing" a certain constant bitrate over certain periods?

    Any ideas? Answeers and tips are very appreciated.



    Regards Kurt
     
    Kurt Kaiser, Nov 10, 2006
    #1
    1. Advertising

  2. Re: constant bitrate approach with lossless data compression on anFPGA

    > I've implemented a lossless data compression (kind of experimental
    > proprietary solution) algorithm in VHDL. For buffering the non-constant data
    > output I've chosen a FIFO in the encoder and decoder although I'm not very
    > happy with that. Because of the high variance it will happen sooner or later
    > that the FIFOs run under or over, respectively. Is there a common practice
    > or trick of "enforcing" a certain constant bitrate over certain periods?


    well ... this is called rate-control

    to prevent overflow:
    you would need to modify your algorithm to be lossy (at least in some
    extreme cases where it would produce too much data) ... this could be
    done by some adjustable quantization but this depends on your algorithm ...

    to prevent underflow:
    just don't read anything from your fifo if there is not enough data!?
    or is your output some kind of streaming? fixed data-rate?
    you could build "packets" and mark some of them as invalid ..


    bye,
    Michael
     
    =?ISO-8859-15?Q?Michael_Sch=F6berl?=, Nov 10, 2006
    #2
    1. Advertising

  3. Kurt Kaiser

    Kurt Kaiser Guest

    "Michael Schöberl" <> schrieb im Newsbeitrag
    news:4554ab2a$...
    >
    > or is your output some kind of streaming? fixed data-rate?
    >


    Unfortunately it is. It HAS to be lossless and it's based on streaming data.
     
    Kurt Kaiser, Nov 10, 2006
    #3
  4. Re: constant bitrate approach with lossless data compression on anFPGA

    Kurt Kaiser wrote:

    > I've implemented a lossless data compression (kind of experimental
    > proprietary solution) algorithm in VHDL. For buffering the non-constant data
    > output I've chosen a FIFO in the encoder and decoder although I'm not very
    > happy with that. Because of the high variance it will happen sooner or later
    > that the FIFOs run under or over, respectively. Is there a common practice
    > or trick of "enforcing" a certain constant bitrate over certain periods?
    >
    > Any ideas? Answeers and tips are very appreciated.


    For overflow: I afraid there's nothing you can do. If you cannot
    compress the data to the target rate you promised to compress to, and
    lossless is your only option, then the code must fail. If you feed a
    high-entropy source into the codec, you cannot expect a high compression
    rate, no matter what.

    What you can possibly do is to have a certain escape symbol to send the
    data uncompressed if the buffer becomes too full. This reduces the
    latency at the encoder side. If you then have a limited bandwidth
    connection to send the data across - well, nothing can be done at all.

    For buffer underflow: That's easier. Just send another escape symbol
    ("line fill") to the receiver to have him stand by for more data.

    So long,
    Thomas
     
    Thomas Richter, Nov 10, 2006
    #4
  5. Kurt Kaiser

    KJ Guest

    "Kurt Kaiser" <> wrote in message
    news:4554af0d$0$30311$-online.net...
    >
    > "Michael Schöberl" <> schrieb im Newsbeitrag
    > news:4554ab2a$...
    >>
    >> or is your output some kind of streaming? fixed data-rate?
    >>

    >
    > Unfortunately it is. It HAS to be lossless and it's based on streaming
    > data.
    >

    Then you need to
    1. Compute a guaranteed upper bound on the amount of output data produced
    per input in your worst case scenario
    2. Run the fifo fast enough per the above computation that it will not
    overflow.
    3. If the output side has flow control then when you perform #1 you also
    have to figure out and take into account the worst case amount of time when
    the output may be saying 'not ready' and add that in plus any latency in
    your logic in responding once it finally does say 'ready'.

    KJ
     
    KJ, Nov 10, 2006
    #5
  6. Kurt Kaiser

    John_H Guest

    I'm an FPGA guy that's flirted with compression and decompression in the
    past so I have a good feel for your world. First, you must know that you
    cannot compress all of the data all of the time. The comment that you'll
    have to be able to go lossy at some point could is valid whether it's an
    algorithm that tosses out some of the less significant information or if the
    link "comes down" until the data is back to normal. If your data set is
    typically well behaved, you've got a good shot of keeping things lossless
    most of the time but there can always be a problem case: imagine 100
    hawaiian-shirt-wearing leprechauns dancing across a teleconference screen.
    The movement and virtual randomness of those colorful patterns across the
    majority of the image will play havoc with an encoder that expects a static
    background image.

    If you can figure the absolute worst case scenario that your lossless
    algorithm has to keep up with, you have your speed. If you want all random
    data to compress losslessly at a fixed streaming rate, it cannot happen.
    There are no FIFOs big enough to guarantee you can cover all situations
    losslessly without having a *higher* output rate than your input.


    "Kurt Kaiser" <> wrote in message
    news:45547ba4$0$27621$-online.net...
    > Hi folks,
    >
    > I've implemented a lossless data compression (kind of experimental
    > proprietary solution) algorithm in VHDL. For buffering the non-constant
    > data output I've chosen a FIFO in the encoder and decoder although I'm not
    > very happy with that. Because of the high variance it will happen sooner
    > or later that the FIFOs run under or over, respectively. Is there a common
    > practice or trick of "enforcing" a certain constant bitrate over certain
    > periods?
    >
    > Any ideas? Answeers and tips are very appreciated.
    >
    >
    >
    > Regards Kurt
    >
    >
     
    John_H, Nov 10, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Susanne Kaufmann

    cut and join mp3-files with known bitrate

    Susanne Kaufmann, Jun 28, 2006, in forum: Java
    Replies:
    6
    Views:
    475
    Chris Uppal
    Jun 30, 2006
  2. Chris Spencer

    Lossless Number Conversion

    Chris Spencer, Aug 28, 2005, in forum: Python
    Replies:
    3
    Views:
    316
    Raymond L. Buvel
    Aug 29, 2005
  3. thomasau

    Retrieving NIC bitrate

    thomasau, Apr 26, 2007, in forum: C Programming
    Replies:
    1
    Views:
    319
    Joachim Schmitz
    Apr 26, 2007
  4. Geronimo Stempovski

    data compression algorithms on FPGA

    Geronimo Stempovski, May 31, 2007, in forum: VHDL
    Replies:
    3
    Views:
    1,031
    comp.arch.fpga
    May 31, 2007
  5. Denkedran Joe
    Replies:
    15
    Views:
    724
Loading...

Share This Page