lossless compression in hardware: what to do in case of uncompressibility?

Discussion in 'VHDL' started by Denkedran Joe, Nov 29, 2007.

  1. Hi all,

    I'm working on a hardware implementation (FPGA) of a lossless compression
    algorithm for a real-time application. The data will be fed in to the
    system, will then be compressed on-the-fly and then transmitted further.

    The average compression ratio is 3:1, so I'm gonna use some FIFOs of a
    certain size and start reading data out of the FIFO after a fixed
    startup-time. The readout rate will be 1/3 of the input data rate The size
    of the FIFOs is determined by the experimental variance of the mean
    compression ratio. Nonetheless there are possible circumstances in which no
    compression can be achieved. Since the overall system does not support
    variable bitrates a faster transmission is no solution here.

    So my idea was to put the question to all of you what to do in case of
    uncompressibility? Any ideas?

    Denkedran Joe
     
    Denkedran Joe, Nov 29, 2007
    #1
    1. Advertising

  2. On Thu, 29 Nov 2007 15:42:45 +0100, "Denkedran Joe"
    <> wrote:

    >Hi all,
    >
    >I'm working on a hardware implementation (FPGA) of a lossless compression
    >algorithm for a real-time application. The data will be fed in to the
    >system, will then be compressed on-the-fly and then transmitted further.
    >
    >The average compression ratio is 3:1, so I'm gonna use some FIFOs of a
    >certain size and start reading data out of the FIFO after a fixed
    >startup-time. The readout rate will be 1/3 of the input data rate The size
    >of the FIFOs is determined by the experimental variance of the mean
    >compression ratio. Nonetheless there are possible circumstances in which no
    >compression can be achieved. Since the overall system does not support
    >variable bitrates a faster transmission is no solution here.
    >
    >So my idea was to put the question to all of you what to do in case of
    >uncompressibility? Any ideas?
    >
    >Denkedran Joe


    Given the constraints you have put on the problem, you're kinda left
    with reducing the incoming data rate or dropping packets.

    Best regards,
    Spehro Pefhany
    --
    "it's the network..." "The Journey is the reward"
    Info for manufacturers: http://www.trexon.com
    Embedded software/hardware/analog Info for designers: http://www.speff.com
     
    Spehro Pefhany, Nov 29, 2007
    #2
    1. Advertising

  3. Denkedran Joe

    CBFalconer Guest

    Re: lossless compression in hardware: what to do in case ofuncompressibility?

    Denkedran Joe wrote:
    >
    > I'm working on a hardware implementation (FPGA) of a lossless
    > compression algorithm for a real-time application. The data will
    > be fed in to the system, will then be compressed on-the-fly and
    > then transmitted further.
    >
    > The average compression ratio is 3:1, so I'm gonna use some FIFOs
    > of a certain size and start reading data out of the FIFO after a
    > fixed startup-time. The readout rate will be 1/3 of the input
    > data rate The size of the FIFOs is determined by the experimental
    > variance of the mean compression ratio. Nonetheless there are
    > possible circumstances in which no compression can be achieved.
    > Since the overall system does not support variable bitrates a
    > faster transmission is no solution here.
    >
    > So my idea was to put the question to all of you what to do in
    > case of uncompressibility? Any ideas?


    Bigger buffers. Smarter algos.

    --
    Chuck F (cbfalconer at maineline dot net)
    <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Nov 29, 2007
    #3
  4. Re: lossless compression in hardware: what to do in case of uncompressibility?

    "CBFalconer" <> wrote:
    >
    > Bigger buffers. Smarter algos.
    >


    Ah okay, now that's why I'm here! Let's discuss some ideas of smarter algos!
     
    Denkedran Joe, Nov 29, 2007
    #4
  5. Denkedran Joe

    Guest

    Re: lossless compression in hardware: what to do in case of uncompressibility?

    >> Bigger buffers. Smarter algos

    >Ah okay, now that's why I'm here! Let's discuss some ideas of smarter algos!


    Let's not.

    Instead, start here and study for a few weeks, then get back to us:

    http://en.wikipedia.org/wiki/Lossless_data_compression
     
    , Nov 29, 2007
    #5
  6. Denkedran Joe

    Phil Carmody Guest

    "Denkedran Joe" <> writes:
    > Hi all,
    >
    > I'm working on a hardware implementation (FPGA) of a lossless compression
    > algorithm for a real-time application. The data will be fed in to the
    > system, will then be compressed on-the-fly and then transmitted further.
    >
    > The average compression ratio is 3:1, so I'm gonna use some FIFOs of a
    > certain size and start reading data out of the FIFO after a fixed
    > startup-time. The readout rate will be 1/3 of the input data rate The size
    > of the FIFOs is determined by the experimental variance of the mean
    > compression ratio. Nonetheless there are possible circumstances in which no
    > compression can be achieved. Since the overall system does not support
    > variable bitrates a faster transmission is no solution here.
    >
    > So my idea was to put the question to all of you what to do in case of
    > uncompressibility? Any ideas?



    You will need to specify your data integrity contraints.
    If your real-time constraints are soft, then big buffers
    will make the problem less common, but not get rid of it
    entirely. If you've got hard real time constraints, then
    they won't, as the data will be stale before you've had
    a chance to send it. Either way, you must be prepared to
    throw some data away under some situations. The question
    then becomes chosing what to throw away, and how to make
    sure that the recipient can also cope with the lost data.

    However, if you know something about your source data that
    general purpose algorithms don't know, then perhaps you
    can achieve a guaranteed compression ratio from a bespoke
    algorithm. What's in your data?

    Phil
    --
    Dear aunt, let's set so double the killer delete select all.
    -- Microsoft voice recognition live demonstration
     
    Phil Carmody, Nov 29, 2007
    #6
  7. Denkedran Joe wrote:
    > Hi all,
    >
    > I'm working on a hardware implementation (FPGA) of a lossless compression
    > algorithm for a real-time application. The data will be fed in to the
    > system, will then be compressed on-the-fly and then transmitted further.
    >
    > The average compression ratio is 3:1, so I'm gonna use some FIFOs of a
    > certain size and start reading data out of the FIFO after a fixed
    > startup-time. The readout rate will be 1/3 of the input data rate The size
    > of the FIFOs is determined by the experimental variance of the mean
    > compression ratio. Nonetheless there are possible circumstances in which no
    > compression can be achieved. Since the overall system does not support
    > variable bitrates a faster transmission is no solution here.
    >
    > So my idea was to put the question to all of you what to do in case of
    > uncompressibility? Any ideas?


    If you have cast this in concrete : "The readout rate will be 1/3 of the
    input data rate" and you hit any compression case above 33.33%, then
    you are dead in the water : something HAS to give - either discard data,
    or take longer.
    You can tolerate 'errant peaks' in the data compression,
    by using larger buffers, but the _average_ must remain under 33.33% over
    the buffer size.

    -jg
     
    Jim Granville, Nov 30, 2007
    #7
  8. Re: lossless compression in hardware: what to do in case of uncompressibility?

    cms wrote:

    > It isin't right to applicate lossless algorithms to fixed-bandwidth
    > systems.


    Depends on the algorithm. E.g. RLE will never cause an increase in size,
    what's sufficient even for use with fixed-bandwidth channels.

    DoDi
     
    Hans-Peter Diettrich, Dec 2, 2007
    #8
  9. Re: lossless compression in hardware: what to do in case of uncompressibility?

    Hans-Peter Diettrich wrote:

    > Depends on the algorithm. E.g. RLE will never cause an increase in size,


    Wrong. It's trivially easy to prove that *no* lossless compression
    algorithm can avoid to sometimes cause an increase in size, while still
    compressing at least some inputs:

    There are 2^N different inputs with N bits, and as long as one of them
    is compressed by at least 1 bit, that means you have only 2^N-2 possible
    outputs left to represent the remaining 2^N-1 inputs with --- impossible.

    [F'up2 comp.compression, which is the only place this could possibly be
    on-topic]
     
    Hans-Bernhard Bröker, Dec 2, 2007
    #9
  10. Denkedran Joe

    Pasi Ojala Guest

    Re: lossless compression in hardware: what to do in case of uncompressibility?

    On 2007-12-02, Hans-Peter Diettrich <> wrote:
    > Depends on the algorithm. E.g. RLE will never cause an increase in size


    Even RLE can increase the size. Two of the most used methods to
    incidate runs are 1) prefix byte, 2) two consequtive bytes are
    the same. For both of these methods you can construct (or the
    file sometimes happens to be) a file containing 1) the value
    of the prefix byte 2) exactly two equal bytes.

    Even if you use some other method of indicating the runs, you
    can always constuct the pathological file that increases in size
    after compression. This fact does not change depending on what
    the compression algorithm is.

    The best you can do is have one bit to select uncompressed/compressed.

    followups set to comp.compression

    -Pasi
    --
    "You're the type of guy who doesn't like to give up control."
    -- Wade to Garibaldi in Babylon 5:"The Exercise of Vital Powers"
     
    Pasi Ojala, Dec 2, 2007
    #10
  11. Denkedran Joe a écrit :
    > So my idea was to put the question to all of you what to do in case of
    > uncompressibility? Any ideas?


    Hi,

    Generally, a compression algorithm may be optimized for a type of data, or for a
    "packet" of data (ie with dynamic table building huffman compression, with
    different algorithms for video, sound or exe files, etc).

    If you can find two (or more) complementary algorithms (or sets of fixed
    parameters for a single algo) that covers the whole flows, you can dynamically
    switch between them, without transmitting the parameters.

    The known of the data flow may help you. Ie, if you may have to transmit an
    already compressed packet, your problem may have not any solution.
     
    Pascal Peyremorte, Dec 2, 2007
    #11
  12. Denkedran Joe

    CBFalconer Guest

    Re: lossless compression in hardware: what to do in case ofuncompressibility?

    Hans-Peter Diettrich wrote:
    > cms wrote:
    >
    >> It isin't right to applicate lossless algorithms to
    >> fixed-bandwidth systems.

    >
    > Depends on the algorithm. E.g. RLE will never cause an increase in
    > size, what's sufficient even for use with fixed-bandwidth channels.


    Nit. Depends on the data. You have to have something to separate
    a repetition count from a new value, which implies a lost char (or
    more) somewhere. However, any such expansion can be expected to be
    small.

    --
    Chuck F (cbfalconer at maineline dot net)
    <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Dec 2, 2007
    #12
  13. Denkedran Joe

    Phil Carmody Guest

    Re: lossless compression in hardware: what to do in case of uncompressibility?

    CBFalconer <> writes:
    > Hans-Peter Diettrich wrote:
    > > cms wrote:
    > >
    > >> It isin't right to applicate lossless algorithms to
    > >> fixed-bandwidth systems.

    > >
    > > Depends on the algorithm. E.g. RLE will never cause an increase in
    > > size, what's sufficient even for use with fixed-bandwidth channels.

    >
    > Nit. Depends on the data. You have to have something to separate
    > a repetition count from a new value, which implies a lost char (or
    > more) somewhere. However, any such expansion can be expected to be
    > small.


    Most RLEs can be caused to explode horribly, simply by
    peppering the file with the value used as the escape code(s).
    Packbits solves this problem, and it will never expand
    more than a small fraction, as it escapes both blocks
    of literals and runs.

    Phil
    --
    Dear aunt, let's set so double the killer delete select all.
    -- Microsoft voice recognition live demonstration
     
    Phil Carmody, Dec 2, 2007
    #13
  14. Denkedran Joe

    Guest

    >> So my idea was to put the question to all of you what to do in case of
    >> uncompressibility? Any ideas?


    How about sending the excess data by post?

    What makes this an electronics problem anyway?
     
    , Dec 2, 2007
    #14
  15. <> wrote:
    >
    > How about sending the excess data by post?


    Joker!

    > What makes this an electronics problem anyway?


    The hardware implementation on an FPGA plattform makes it an electronics
    problem. So, think again! Next time you better come up with a more
    sophisticated answer...
     
    Denkedran Joe, Dec 3, 2007
    #15
  16. Denkedran Joe

    Guest

    >> How about sending the excess data by post?
    >Joker!


    >> What makes this an electronics problem anyway?

    >The hardware implementation on an FPGA plattform makes it an electronics
    >problem. So, think again! Next time you better come up with a more
    >sophisticated answer...


    Let me put it more clearly. You fail to distinguish the separate
    problems of algorithm and implementation. There is nothing
    specifically electronic about this problem, so it doesn't concern
    FPGAs in general nor VHDL in particular.

    If you don't like what's on TV, does that make it an electronic
    problem?
     
    , Dec 3, 2007
    #16
    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. Steve Franks
    Replies:
    2
    Views:
    1,273
    Steve Franks
    Jun 10, 2004
  2. Chris Spencer

    Lossless Number Conversion

    Chris Spencer, Aug 28, 2005, in forum: Python
    Replies:
    3
    Views:
    311
    Raymond L. Buvel
    Aug 29, 2005
  3. Kurt Kaiser
    Replies:
    5
    Views:
    678
    John_H
    Nov 10, 2006
  4. Rajesh.Rapaka

    jpeg lossless decoding

    Rajesh.Rapaka, Nov 14, 2006, in forum: Java
    Replies:
    0
    Views:
    542
    Rajesh.Rapaka
    Nov 14, 2006
  5. Daniel Nogradi

    lossless transformation of jpeg images

    Daniel Nogradi, Oct 29, 2006, in forum: Python
    Replies:
    0
    Views:
    362
    Daniel Nogradi
    Oct 29, 2006
Loading...

Share This Page