[vorbis-dev] another entropy coder that might be very useful

[Yann Guidon]

Hello,

I want to let you know about an algo that will soon be published
and that may be of interest to Vorbis (and other Ogg projects) :

http://f-cpu.seul.org/whygee/ddj-3r/ddj-3r.tgz

this is the archive of the article i submitted.
It describes the "Recursive Range Reduction" algorithm
(3R for short) and uses only a few basic computer
principles (a binary tree being the most complex structure).
Really, it's so simple that i wonder why nobody uses it.

It is quite efficient (compared to other classical methods)
for reducing the size of histograms
(my first intent) but also DCT, FFT, Huffman tables ...
It is a low complexity (add/sub, shift, masks ...)
code that works well on small datasets that have
some kind of correllation that is not easily modelised.
Depending on the type of data (large variance and
grouped chunks), it can be used to compress/pack
as little as 4 or 8 values, sometimes beating Rice and Huffman codes.

It requires O(N) temporary storage for compression
(usually N plus a stack in log2(N)), and it can be modified
for in-place decompression. I have tried to illustrate its operation
with simple, non-optimised code, which has a lot
of headroom for adaptation (i design most algos
with DSPs/uCs/ASICs/FPGA in mind)

It is new so many optimisations, heuristics and applications
remain to be invented and implemented, i hope that
it will be useful for the next version of Vorbis, speex etc.
One of the most promising use is as a "baseline JPEG"
replacement, as it can do the zigzag+RLE+entropy coding
in a single, tunable, step. As it is low-CPU, it is good
for low-power video as well. And it is patent-free AFAIK !
(so no worries about
http://yro.slashdot.org/article.pl?sid=04/04/24/1621203
http://yro.slashdot.org/article.pl?sid=04/04/24/1621203 )

I have no time to look closely at the Vorbis source code,
so i won't hack&patch it. However i encourage
everybody to look at the 3R algorithm and use it in Ogg projects.

Have fun,
YG

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.