Arithmetic coding

[High-Voltage]

Hi all,


I do have a question about videocoding. I'm not sure if this is the right forum, but I hope someone could help me.
My question handles about the working of a video encoder, so let's say the sourcecode part of the encoder.

The last stage of the encoding proces is the "entropy coder". This block puts the motion vectors, quantised coefficients, headers etc together to create the actual bitstream. But it doesn't put it just togheter, no it compresses also a bit.
One way of compressing is by using "Arithmetic coding". This method divides a domain into smaller domains based on the probability of each symbol. Each domain is again divided into smaller domains based on the probability of the symbols. This is repeated several times. The domain is getting smaller and smaller. Finally we have a lot of small domains each representing a sequence of the original symbols. By sending a fractional number from a specific domain we can actually send the sequence of those symbols.
The decoder decodes this fractional number again in domains to determine the sequence of symbols.

I hope this is a bit clear. But if it isn't you are probably not capable to answer my question.

My question is: How does the decoder know the boundries of each domain? The decoder doesn't know the probablities of the symbols, so I couldn't reconstruct the dividing.

I really hope someone could give me the answer!


Many Thanks

High-Voltage

[Manao]

Encoder and decoder must agree on the probability of each symbols. That can be achieved either by transmitting the probability of each symbols in a header, or by supposing each probability to be constant accross several encoding.

If we take cabac's example, you have in a header a bit selecting one of two set of probability tables. Once the set is chosen, the probability of each symbol is known (by the decoder and the encoder). Each time the encoder encode a symbol, it updates its probability in a standardize manner, so that whenever the decoder decode that symbol, it can update its probability accordingly.

[High-Voltage]

So actually both (encoder and decoder) are armed with some "probability tables" ?
But what if a specific symbol isn't listed in the table?

[LoRd_MuldeR]

I assume both (encoder and decoder) need identical probability tables to start with. And all symbols that might occur need to be in the table...

[MfA]

With only 2 symbols it's rather unlikely not to be in there :p (The b in cabac is for binary after all.)

For an M-ary arithmetic coder you could simply have an escape code for rare symbols, coding the escaped symbols in a separate stream.

[High-Voltage]

I assume both (encoder and decoder) need identical probability tables to start with.
I'm quite sure about that. But the question is how do both get the same table(s)? Do they use a pre-calculated table or is the table real-time generated?
I think (based on Manao's post) the probabilities of the symbols in a specific sequence are put in a header. So the "table" will be generated in real-time.


And all symbols that might occur need to be in the table...
True, but there are a lot of symbols... So it's nearly impossible to list them ALL. But sending the probabilities in a header will fix this problem.


I guess I understand.
Thanks all for your help!! :)

[Manao]

Usually, arithmetic encoders are made adaptive, thus they don't rely heavily on initial probability since they will be updated each time a symbol is encoded/decoded.

For example, CABAC (Context-Adaptive BAC) assumes at the start of a picture that probabilities are all set to predetermined values (which don't have to be transmitted, they have been decided once and for all). The adaptive part ensures that it is efficient.

[MfA]

True, but there are a lot of symbols
Even ignoring binarization 10 bits precision is at the high end for coded values.