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:

    “If all else perished, and he remained, I should still continue to be; and if all else remained, and he were annihilated, the universe would turn to a mighty stranger. I should not seem a part of it.... My love for Heathcliff resembles the eternal rocks beneath—a source of little visible delight, but necessary. Nelly, I am Heathcliff—he’s always, always in my mind—not as a pleasure, any more than I am always a pleasure to myself—but as my own being.”
    —Emily Brontë (1818–1848)

    “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 truth has never been of any real value to any human being—it is a symbol for mathematicians and philosophers to pursue. In human relations kindness and lies are worth a thousand truths.”
    —Graham Greene (1904–1991)

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