Developer Forum

I just made what I *thought* was an arithmetic encoder (got the book
Text Compression last week) using integer arithmetic so my ranges are
actually integer ranges. So I wonder what exactly makes a range coder
different from an arithmetic encoder?

I have been looking on google for about he last hour only to find things
which basically say that a range coder uses an integer range while an
arithmetic coder uses a fractional range between 0 and 1. But how else
would you implement an arithmetic encoder anyway?


I also read that there are no patents on range coding and it's faster so
I would definitely like to know what it is. :)

Thanks in advance.

The output from an arithmetic coder is a single floating point number, which
might be quite long. Naturally, this giant floating point number can be
constructed using integer math, although one must be careful.

That's the salient point, but it might be kind of hard to tell that's what
you're dealing with by just looking at the code.

--
|
| Mark Nelson - XXXX@XXXXX.COM - http://www.yqcomputer.com/
| The Ultimate Compression Resource - http://www.yqcomputer.com/
| Sponsored by Xceedsoft.com - Serious About Components
|

Correction - it is a fractional fixed point value in the range 0
to just less than 1. Definitely not a floating point number.

--
Chuck F ( XXXX@XXXXX.COM ) ( XXXX@XXXXX.COM )
Available for consulting/temporary embedded and systems.
< http://www.yqcomputer.com/ > USE worldnet address!

Well seriously, what exactly is the difference? It's not like the
output of an arithmetic coder *has* a fixed point in the front of it,
that's just how you think about the algorithm. I could just as easily
say the output is a very large integer. I'm just imaging the fixed
point at the end, and you implement it the same way to boot.

All I found about how range coding differs from arithmetic coding is
that when the numbers are renormalized range coding waits until it has 8
bits ready to be written before it performs the renormalization.

Am I missing something or is that really the only difference?

N*[0,1) -> [0, N)

does not mean either one is floating point, which combines
a certain number of digits, with a variable exponent, in effect
[0,N) * 2^(M) for separate integers N,M

The idea of a fixed point fractional value mates precisely with
the methods used to encode and decode this form of compression.
At any rate, much better explanations (and code) are available in:

The Data Compression Book, 2nd edition
by Mark Nelson and JeanLoup Gailly
M & T Books. ISBN 1-55851-434-1

--
Chuck F ( XXXX@XXXXX.COM ) ( XXXX@XXXXX.COM )
Available for consulting/temporary embedded and systems.
< http://www.yqcomputer.com/ > USE worldnet address!

[snip]


Hi,

As for as I know, the only difference in Range Coding and Arithmetic Coding
is that Arithmetic Coding renormalizes to bits (numbers of base-2), whereas
Range Coding renormalizes to numbers of any base (like numbers of base-256
as in your example of 8-bits)

The range encoder is based on an article presented by G.N.N. Martin on the
Data Recording Conference, Southampton, July 1979.

http://www.yqcomputer.com/


You can download Michael Schindler's source code for Range Coding from
http://www.yqcomputer.com/


Range coder is faster than arith coder, but due to larger delays in
renormalizations in Range coding, there is slight inaccuracy in calculations
which result in slightly larger compressed files.

Moreover, although certain implementations of arithmetic coding are
patented, I havent yet seen a reference to any patent on the general idea
behind arithmetic coding. So it might be safe to use arithmetic coding also.
(dont take my word for it, I dont know much about patents)

Depending on whats important to you (speed or compressed size) you may want
to know that as we usually use 32-bit integers to represent floating point
ranges, even arithmetic coding is not 100% accurate. This accuracy can be
further increased by using 64-bit integers. Refer to this link for
details...

http://www.yqcomputer.com/


Sachin Garg [India]
http://www.yqcomputer.com/
http://www.yqcomputer.com/