FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > VHDL

VHDL comp.lang.vhdl newsgroup / Usenet

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 11-10-2006, 02:16 PM
Kurt Kaiser
Guest
 
Posts: n/a
Default constant bitrate approach with lossless data compression on an FPGA

Hi folks,

I've implemented a lossless data compression (kind of experimental
proprietary solution) algorithm in VHDL. For buffering the non-constant data
output I've chosen a FIFO in the encoder and decoder although I'm not very
happy with that. Because of the high variance it will happen sooner or later
that the FIFOs run under or over, respectively. Is there a common practice
or trick of "enforcing" a certain constant bitrate over certain periods?

Any ideas? Answeers and tips are very appreciated.



Regards Kurt


Reply With Quote
  #2 (permalink)  
Old 11-10-2006, 05:39 PM
Michael Sch÷berl
Guest
 
Posts: n/a
Default Re: constant bitrate approach with lossless data compression on anFPGA

> I've implemented a lossless data compression (kind of experimental
> proprietary solution) algorithm in VHDL. For buffering the non-constant data
> output I've chosen a FIFO in the encoder and decoder although I'm not very
> happy with that. Because of the high variance it will happen sooner or later
> that the FIFOs run under or over, respectively. Is there a common practice
> or trick of "enforcing" a certain constant bitrate over certain periods?


well ... this is called rate-control

to prevent overflow:
you would need to modify your algorithm to be lossy (at least in some
extreme cases where it would produce too much data) ... this could be
done by some adjustable quantization but this depends on your algorithm ...

to prevent underflow:
just don't read anything from your fifo if there is not enough data!?
or is your output some kind of streaming? fixed data-rate?
you could build "packets" and mark some of them as invalid ..


bye,
Michael
Reply With Quote
  #3 (permalink)  
Old 11-10-2006, 05:55 PM
Kurt Kaiser
Guest
 
Posts: n/a
Default Re: constant bitrate approach with lossless data compression on an FPGA


"Michael Sch÷berl" <[email protected]> schrieb im Newsbeitrag
news:[email protected]
>
> or is your output some kind of streaming? fixed data-rate?
>


Unfortunately it is. It HAS to be lossless and it's based on streaming data.


Reply With Quote
  #4 (permalink)  
Old 11-10-2006, 06:07 PM
Thomas Richter
Guest
 
Posts: n/a
Default Re: constant bitrate approach with lossless data compression on anFPGA

Kurt Kaiser wrote:

> I've implemented a lossless data compression (kind of experimental
> proprietary solution) algorithm in VHDL. For buffering the non-constant data
> output I've chosen a FIFO in the encoder and decoder although I'm not very
> happy with that. Because of the high variance it will happen sooner or later
> that the FIFOs run under or over, respectively. Is there a common practice
> or trick of "enforcing" a certain constant bitrate over certain periods?
>
> Any ideas? Answeers and tips are very appreciated.


For overflow: I afraid there's nothing you can do. If you cannot
compress the data to the target rate you promised to compress to, and
lossless is your only option, then the code must fail. If you feed a
high-entropy source into the codec, you cannot expect a high compression
rate, no matter what.

What you can possibly do is to have a certain escape symbol to send the
data uncompressed if the buffer becomes too full. This reduces the
latency at the encoder side. If you then have a limited bandwidth
connection to send the data across - well, nothing can be done at all.

For buffer underflow: That's easier. Just send another escape symbol
("line fill") to the receiver to have him stand by for more data.

So long,
Thomas
Reply With Quote
  #5 (permalink)  
Old 11-10-2006, 06:31 PM
KJ
Guest
 
Posts: n/a
Default Re: constant bitrate approach with lossless data compression on an FPGA


"Kurt Kaiser" <diebombeausdemweste[email protected]> wrote in message
news:[email protected]
>
> "Michael Sch÷berl" <[email protected]> schrieb im Newsbeitrag
> news:[email protected]
>>
>> or is your output some kind of streaming? fixed data-rate?
>>

>
> Unfortunately it is. It HAS to be lossless and it's based on streaming
> data.
>

Then you need to
1. Compute a guaranteed upper bound on the amount of output data produced
per input in your worst case scenario
2. Run the fifo fast enough per the above computation that it will not
overflow.
3. If the output side has flow control then when you perform #1 you also
have to figure out and take into account the worst case amount of time when
the output may be saying 'not ready' and add that in plus any latency in
your logic in responding once it finally does say 'ready'.

KJ


Reply With Quote
  #6 (permalink)  
Old 11-10-2006, 06:50 PM
John_H
Guest
 
Posts: n/a
Default Re: constant bitrate approach with lossless data compression on an FPGA

I'm an FPGA guy that's flirted with compression and decompression in the
past so I have a good feel for your world. First, you must know that you
cannot compress all of the data all of the time. The comment that you'll
have to be able to go lossy at some point could is valid whether it's an
algorithm that tosses out some of the less significant information or if the
link "comes down" until the data is back to normal. If your data set is
typically well behaved, you've got a good shot of keeping things lossless
most of the time but there can always be a problem case: imagine 100
hawaiian-shirt-wearing leprechauns dancing across a teleconference screen.
The movement and virtual randomness of those colorful patterns across the
majority of the image will play havoc with an encoder that expects a static
background image.

If you can figure the absolute worst case scenario that your lossless
algorithm has to keep up with, you have your speed. If you want all random
data to compress losslessly at a fixed streaming rate, it cannot happen.
There are no FIFOs big enough to guarantee you can cover all situations
losslessly without having a *higher* output rate than your input.


"Kurt Kaiser" <[email protected]> wrote in message
news:[email protected]
> Hi folks,
>
> I've implemented a lossless data compression (kind of experimental
> proprietary solution) algorithm in VHDL. For buffering the non-constant
> data output I've chosen a FIFO in the encoder and decoder although I'm not
> very happy with that. Because of the high variance it will happen sooner
> or later that the FIFOs run under or over, respectively. Is there a common
> practice or trick of "enforcing" a certain constant bitrate over certain
> periods?
>
> Any ideas? Answeers and tips are very appreciated.
>
>
>
> Regards Kurt
>
>



Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

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 On


Similar Threads
Thread Thread Starter Forum Replies Last Post
lossless compression in hardware: what to do in case of uncompressibility? Denkedran Joe FPGA 24 12-05-2007 05:13 PM
Re: lossless compression in hardware: what to do in case of uncompressibility? Pascal Peyremorte FPGA 0 12-02-2007 02:34 PM
Re: lossless compression in hardware: what to do in case of uncompressibility? Jim Granville FPGA 0 11-30-2007 03:09 AM
data compression algorithms on FPGA Geronimo Stempovski FPGA 4 06-06-2007 03:32 PM
FPGA Implementation Of Real Time Data Compression [email protected] FPGA 0 12-16-2005 07:22 PM


All times are GMT +1. The time now is 06:17 AM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved