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

  • Buried in cloud files? We can help with Spring cleaning!

    Whether you use Dropbox, Drive, G-Suite, OneDrive, Gmail, Slack, Notion, or all of the above, Dokkio will organize your files for you. Try Dokkio (from the makers of PBworks) for free today.

  • Dokkio (from the makers of PBworks) was #2 on Product Hunt! Check out what people are saying by clicking here.

View
 

Scribe Notes 5-1

Page history last edited by Lingxiao XIA 13 years, 2 months ago

Arithmetic Codes

 

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

 

(Encoding)

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).

 

 

(Decoding)

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.

 

Remarks:

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:

 

Formula.

By manipulating the equation above, we get:

 

Formula.

Formula in probability.

 

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

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:

 

Formula.

 

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

 

Formula

Formula

Then we try to get a lower bound for Formula:

Formula

Formula

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.