| 
  • 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!

View
 

Scribe_Note_7_2

This version was saved 12 years, 3 months ago View current version     Page history
Saved by Xixuan Wu
on December 10, 2011 at 11:09:30 pm
 

Scribe Notes 7 (by Xixuan Wu)

Generally source coding reduce the redundancy, channel coding add the redundancy.

Description of an arbitrary real number requires an infinite number of bits. Finite representation of a continuous random variable can never be perfect. So it's necessary to define the "goodness" of a representation of a source. The problem is: Given a source distribution and a distortion measure, what is the minimum expected distortion achievable at a particular rate? or What's the minimum rate required to get a proper distortion?

 

1. Quantization

The representation of X is denoted as Formula.

 

1.1 1bit random variable Quantization Example

Let Formula, assume the distortion measure is Formula. We have only one bit to represent X, so it's clear that the bit will show whether X>0 or not. To minimize squared error, each reproduced symbol should be the conditional mean of its region, the equation and figure is showed as below:

The reconstruction points are at -0.79 and 0.79.

 

1.2 2bit Quantization Example

Like PS7 Q1, if we choose one bit to express X which is from {0,1,2,3}, we will choose 0 to express X=0 or 1, choose 1 to express X=2 or 3. When we're decoding, we decode 0 to X=0, decode 1 to X=1.

So the distortion's expectation E(distortion) = 0.25*1+0.25*1 = 0.5.f

If X is from {0,1,2,3}^2, we use 2 bits to express X, it's just like to select 4 positions in the graph:


The left side is the same choice as 1bit quantization, but for some positions(?), the distortion > 1. If we choose picture of right side, the distortion will keep 1.

 

2. Definitions

2.1 Rate distortion encoder and decoder

2.2 distortion measure

Distortion measure is a mapping: Formula. It's said to be bounded if Formula

Distortion between sequences Formula and Formula is Formula

 

2.3 rate distortion function

A rate distortion pair (R,D) is said to be achievable if there exists a sequence of Formula-rate distortion codes Formula with Formula. R(D) is the infimum of rates R such that (R,D) is in the rate distortion region of the source for a given distortion D. D(R) is the infimum of all distortions D such that (R,D) is in the rate distortion region of the source for a given rate R.

 

The information rate distortion function : Formula

 

2.3.1 rate distortion function of binary source

The rate distortion rate R(D) for a Bernoulli(p) source with Hamming distortion is given by:

 

Proof: Let Formula denote modulo 2 addition. Formula means Formula.

Formula

The lower bound is found by a joint distribution that meets the distortion constraint, just like: 

Formula. If D >= p, just set Formula. The function is illustrated in:

 

2.3.2 rate distortion function of Gaussian Source

The rate distortion rate R(D) for a Formula source with squared-error distortion is given by:


Proof:

Formula

FormulaFormula

The joint distribution that achieves this lower bound is shown as:

if Formula, we choose Formula. If FormulaFormula.

The function is illustrated in:

 

2.3.2 rate distortion function of Independent normal random sources

The information rate distortion function of vector is :

Formula, where 

 

Comments (0)

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