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

[Denkedran Joe]

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

 

[Spehro Pefhany]

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

 

[CBFalconer]

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.

 

[Denkedran Joe]

Bigger buffers. Smarter algos.

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

 

[MikeShepherd564]

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

 

[Phil Carmody]

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

 

[Jim Granville]

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

 

[Hans-Peter Diettrich]

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-Bernhard Bröker]

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]

 

[Pasi Ojala]

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

 

[Pascal Peyremorte]

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.

 

[CBFalconer]

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.

 

[Phil Carmody]

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

 

[MikeShepherd564]

So my idea was to put the question to all of you what to do in case of
How about sending the excess data by post?

What makes this an electronics problem anyway?

 

[Denkedran Joe]

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

 

[MikeShepherd564]

How about sending the excess data by post?

Joker!
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?