Rate Distortion Theory February 20, 2006

Source coding aims to reduce redundancy in information to improve storage/transmission efficiency, while channel coding aims to increase redundancy to improve reliable transmission over a noisy channel. The source coding theorem:

Given a discrete memoryless source of entropy, H(ζ), the average code-word length L for any distortionless source encoding scheme, is bounded as L ≥ H(ζ)

In a system, source symbols with alphabet X~p(X=xi) go through an encoder and become representation symbols with alphabet Y~p(Y=yj)

The single letter distortion measure, d(xi, yj) is defined as the cost in representing xi by yj. Define

Single Letter Distortion Measure

p(yj| xi) is said to be “D-admissible” iff d≤D for some D. The set of D-admissible p(yj| xi) is denoted by PD = {p(yj | xi) : d ≤ D}

[Mutual Information]
The mutual information, I(X; Y) is given by

Mutual Information

[Rate Distortion Measure]
A rate distortion function, R(D) (and measured in bits) is defined as the smallest coding rate possible for which the average distortion, d is guaranteed not to exceed D.

subject to the constraint

Related Tags

Leave a Reply

You must be logged in to post a comment.

This entry was posted on Monday, February 20th, 2006 at 5:08 pm. You can follow any responses to this entry through the RSS 2.0 feed. If you're wondering how to get your own icon next to your comment, go visit gravatar.com and get yourself hooked up.
 steal compass, drive north, disappear...