Shannon's Source Coding Theorem - Proof: Source Coding Theorem For Symbol Codes

Proof: Source Coding Theorem For Symbol Codes

Let denote the wordlength of each possible . Define, where C is chosen so that .

Then

\begin{align} H(X) &= - \sum_{i=1}^n p_i \log_2 p_i \\ &\leq - \sum_{i=1}^n p_i \log_2 q_i \\ &= - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \sum_{i=1}^n p_i \log_2 C \\ &= - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \log_2 C \\ &\leq - \sum_{i=1}^n - s_i p_i \log_2 a \\ &\leq \mathbb{E}S \log_2 a \\ \end{align}

where the second line follows from Gibbs' inequality and the fifth line follows from Kraft's inequality: so .

For the second inequality we may set

so that

and so

and

and so by Kraft's inequality there exists a prefix-free code having those wordlengths. Thus the minimal S satisfies

\begin{align} \mathbb{E}S & = \sum p_i s_i \\ & < \sum p_i \left( -\log_a p_i +1 \right) \\ & = \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\ & = \frac{H(X)}{\log_2 a} +1. \\ \end{align}

Read more about this topic:  Shannon's Source Coding Theorem

Famous quotes containing the words source, theorem, symbol and/or codes:

    “By recognizing a favorable opinion of yourself, and taking pleasure in it, you in a measure give yourself and your peace of mind into the keeping of another, of whose attitude you can never be certain. You have a new source of doubt and apprehension.”
    —Charles Horton Cooley (1864–1929)

    “To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
    —Albert Camus (1913–1960)

    “The glance is natural magic. The mysterious communication established across a house between two entire strangers, moves all the springs of wonder. The communication by the glance is in the greatest part not subject to the control of the will. It is the bodily symbol of identity with nature. We look into the eyes to know if this other form is another self, and the eyes will not lie, but make a faithful confession what inhabitant is there.”
    —Ralph Waldo Emerson (1803–1882)

    “We must trust infinitely to the beneficent necessity which shines through all laws. Human nature expresses itself in them as characteristically as in statues, or songs, or railroads, and an abstract of the codes of nations would be an abstract of the common conscience.”
    —Ralph Waldo Emerson (1803–1882)