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

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 

On Thu, 29 Nov 2007 15:42:45 +0100, "Denkedran Joe"
<denkedranjoe@googlemail.com> 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"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

On Nov 29, 8:42 am, "Denkedran Joe" <denkedran...@googlemail.com>
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

If the compression must be lossless, and you can not increase the bit
rate, you need to allow for the buffering of the input data to grow in
size to accommodate the worst case.  If you can not build a big enough
FIFO inside the FPGA, add some external memory and use it as a FIFO.


Is the hardware already designed? What are your data rates, and do you
know what the worst case compression is?

Regards,

John McCaskill
www.fastertechnology.com

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" <cbfalconer@yahoo.com> wrote:
>
> Bigger buffers.  Smarter algos.
>

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

>> 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

On Nov 29, 6:42 am, "Denkedran Joe" <denkedran...@googlemail.com>
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

You cannot solve your problem losslessly.  You must guarantee your
image is in a state that will guarantee compressibility or your stream
will occasionally require more bandwidth than is available; you'd need
infinite FIFOs to cover worst-case situations.

You MUST have a lossy fallback OR supply enough bandwidth to
accommodate uncompressed data as a fallback.  Variable bit-rate multi-
channel systems can borrow bandwidth from each other since -
statistically - all channels do not experience poor compression at
once unless they're all transmitting similarly uncompressible images.

If your video is dynamic in movement and in color for a length of
time, your stream will exceed your channel bandwidth.  If you have
very large (disk based?) FIFOs, you can drop video for a short time
and pick back up when the compressed stream is better behaved and you
can receive continuous video again.  You will not be able to recover
the delay that you introduced from the compression on the receive side
unless you skip some received video (which is lossy) or speed up the
playback.  Can you deal with a fixed delay of seconds or minutes once
you've experienced a period of poor compression?

No lossless compression scheme can compress everything.  You can only
have better compression schemes that will fail less often or present a
fallback: lossy compression or variable bit rates.

There are no finite alternatives; it's one of the basic principles of
compression.  There are no smarter algos, just better compression
schemes that fail less often.

- John_H

"Denkedran Joe" <denkedranjoe@googlemail.com> 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

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

It isin't right to applicate lossless algorithms to fixed-bandwidth
systems.
There is always dark case corner with fully uncorrerlated data set
then compression ratio will be 1:1 (or even worse
for prediction-based algorithms with not corresponding distribution
model).

Lossless algorithms are perfect in storage systems for space saving.
But transport channel should be wide enough
for  the worst case.

From my knowledge of life the robust solution in your case is the
redesigning system with wide channel at the current stage.
Don't play with thin air, force oneself now and eliminate great
troubles in the future.

Digitally yours,
Michael Tsvetkov (JPEG-lossless IP Core developer)

http://www.jpegls.com