• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!


Scribe Notes 5-1

Page history last edited by Lingxiao XIA 14 years, 11 months ago

Arithmetic Codes


This is going to be the last lossless source coding scheme covered by this course.



We are going to illustrate the principle of arithmetic code by an example:

Consider a binary source with Formula and Formula, instead of using a sequence of bits to represent a certain outcome, we use a subinterval of [0, 1) to denote the outcome.

As shown in the chart below, all different possible outcomes with Formula symbols are represented by some intervals in level Formula. For example, Formula is represented by the interval Formula.


After we know the length Formula of the interval, we can be sure that the point given by the first Formula bits of the binary representation of the midpoint of the interval will fall into this interval, so we choose this finite digit number to be the representation of this interval.

For example, in this case, Formula has an interval length of Formula, so this interval can be represented by the first Formula bits of its midpoint Formula, i.e. Formula will represent this interval(the digit Formula before the floating point and also the floating point is omitted because they are the same for every point).




After the code is sent to the decoder, the decoder will construct the same subintervals corresponding to the level the encoder is using and see which subinterval the code falls in. Using this the decoder will be able to find the original code.



1. Adding an additional bit to the source block takes a constant Time Complexity to encode again for Arithmetic Codes, which is a lot better then Hoffman Codes (exponemtial).

2. The arithmetic coding procedure, given any length n and probability mass function Formula, enables one to encode the sequence Formula in a code of length Formula, this procedure achieves an average length for the block that is within 2 bits of the entropy.

3. Arithmetic Coding scheme works even if the source codes are not independent. For example, when the source codes follows a Markov Chain, then Formula, but the principle does not need to change.

4. When the encoder and the decoder does not know the distribution of the source, they can use the information they already know to estimate the distribution, and by the law of large number, this estimated distribution will converge to the real distribution in probability.



Weak Typicality


We define the Formula-weakly typical set Formula as the set of all Formula such that:



By manipulating the equation above, we get:



Formula in probability.


Now what if the Formulas are not i.i.d.? Recall the definition of Formula:


so even if Formulas are not i.i.d., we can still define weak typical in a similar way.


The Formula-weakly typical set Formula as the set of all Formula such that:




Now let's calculate the number of elements in Formula:




Then we try to get a lower bound for Formula:




Hence, we can get Formula.


So weak typicality is also a good way of saying typicality.





Comments (1)

Lingxiao XIA said

at 10:04 pm on Mar 20, 2009

sorry for this late modification of the scribe note, i thought i already finished it until i saw the *under construction* sign... anyway it is finished now, welcome for any comments

You don't have permission to comment on this page.