Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > lossless compression in hardware: what to do in case of uncompressibility?

Reply
Thread Tools

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

 
 
Denkedran Joe
Guest
Posts: n/a
 
      11-29-2007
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


 
Reply With Quote
 
 
 
 
Spehro Pefhany
Guest
Posts: n/a
 
      11-29-2007
On Thu, 29 Nov 2007 15:42:45 +0100, "Denkedran Joe"
<(E-Mail Removed)> 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"
http://www.velocityreviews.com/forums/(E-Mail Removed) Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      11-29-2007
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

 
Reply With Quote
 
Denkedran Joe
Guest
Posts: n/a
 
      11-29-2007
"CBFalconer" <(E-Mail Removed)> wrote:
>
> Bigger buffers. Smarter algos.
>


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


 
Reply With Quote
 
MikeShepherd564@btinternet.com
Guest
Posts: n/a
 
      11-29-2007
>> 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
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      11-29-2007
"Denkedran Joe" <(E-Mail Removed)> 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
 
Reply With Quote
 
Jim Granville
Guest
Posts: n/a
 
      11-30-2007
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

 
Reply With Quote
 
Hans-Peter Diettrich
Guest
Posts: n/a
 
      12-02-2007
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
 
Reply With Quote
 
Hans-Bernhard Bröker
Guest
Posts: n/a
 
      12-02-2007
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]
 
Reply With Quote
 
Pasi Ojala
Guest
Posts: n/a
 
      12-02-2007
On 2007-12-02, Hans-Peter Diettrich <(E-Mail Removed)> 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"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Rawzor beta release (lossless raw compression) Sachin Garg Digital Photography 84 09-15-2008 04:43 AM
'extra' lossless compression for camera raw images Sachin Garg Digital Photography 12 07-08-2008 05:57 PM
'extra' lossless compression for camera raw images Sachin Garg Digital Photography 52 03-25-2008 10:40 PM
constant bitrate approach with lossless data compression on an FPGA Kurt Kaiser VHDL 5 11-10-2006 05:50 PM
question about using jpegtran for lossless compression of jpegs ewaguespack@gmail.com Digital Photography 4 10-24-2006 09:55 AM



Advertisments