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

Denkedran Joe

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

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

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

Denkedran Joe

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

MikeShepherd564@btinternet.com

"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

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

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

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

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