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 .
1.1 1bit random variable Quantization Example
Let , assume the distortion measure is . 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: . It's said to be bounded if
Distortion between sequences and is
2.3 rate distortion function
A rate distortion pair (R,D) is said to be achievable if there exists a sequence of -rate distortion codes with . 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 :
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 denote modulo 2 addition. means .
The lower bound is found by a joint distribution that meets the distortion constraint, just like:
. If D >= p, just set . The function is illustrated in:
2.3.2 rate distortion function of Gaussian Source
The rate distortion rate R(D) for a source with squared-error distortion is given by:
Proof:
The joint distribution that achieves this lower bound is shown as:
if , we choose . If , .
The function is illustrated in:
2.3.2 rate distortion function of Independent normal random sources
The information rate distortion function of vector is :
, where
Comments (0)
You don't have permission to comment on this page.