Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to learn how to implement the Arithmetic Encoder algorithm for one of my classes. The thing is the notes we have explaining the actual algorithm are a bit on the confusing side. I have been looking up tutorials and videos about the algorithm and found some on youtube. I was wondering if anyone could tell me the difference between Infinite Precision Arithmetic Encoding and Finite Precision Arithmetic Encoding as shown in these videos..

Finite Precision Video

Infinite Precision Video

From what I can gather, Static Arithmetic encoding uses predefined probabilities for each character in the input. Meaning that it needs to know what symbols are going to be in the input and their probabilities.

Adaptive has a predefined set of characters that can come up and assigns equal probabilities to all of these characters until a character is read and then raises the probability of this character, and so on.

Do the videos above correspond to my interpretations of the algorithm? I'm a bit wary as he doesn't mention static or adaptive anywhere in the videos.

Thanks, Aimee

share|improve this question
2  
Just from watching a few minutes of the infinite precision video, it is stated at the outset that it is only theoretical. So the difference is -- one is for conceptual purposes and cannot be programmed, the other is not, but has complications due to finite precision arithmetic. Static and adaptive are different concepts, nothing to do with finite versus infinite precision in this context. –  adam W Apr 7 '13 at 17:39
add comment

1 Answer

up vote 2 down vote accepted

Both of the videos linked to use static arithmetic encoding. So the symbols and probabalities associated with them are constant. This is why the video does not mention static or adaptive anything in the videos, they are not related for the specific subject matter.

As for infinite versus finite, there is no such thing as an actual infinite precision method because at each step the values are shifted and scaled and divided, and the numbers to represent them grow in their respective bitsize. They do so with no end (in the theoretical infinite precision method). So do not think of the two as two different methods, they are both one in the same. But the one is introduced as a way to avoid the extra complication of precision. Just to concentrate only on the important concepts.

The other (finite precision encoder) is the actual implementation. When you attempt the algorithm, you realize that you do not want to keep longer and longer (in bitsize) values, which is what happens with the infinite precision algorithm. I would say "algorithm" (in quotes), except technically it is an algorithm; just one that runs on a theoretical machine capable of infinite precision.

I hope that helps.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.