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
lossless compression in hardware: what to do in case of uncompressibility?
Started by ●November 29, 2007
Reply by ●November 29, 20072007-11-29
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 JoeGiven 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
Reply by ●November 29, 20072007-11-29
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 JoeIf 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
Reply by ●November 29, 20072007-11-29
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 by ●November 29, 20072007-11-29
"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!
Reply by ●November 29, 20072007-11-29
>> 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 by ●November 29, 20072007-11-29
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 JoeYou 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
Reply by ●November 29, 20072007-11-29
"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
Reply by ●November 29, 20072007-11-29
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 by ●December 2, 20072007-12-02
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