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:

    “A comfortable house is a great source of happiness. It ranks immediately after health and a good conscience.”
    —Sydney Smith (1771–1845)

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

    “No one is without Christianity, if we agree on what we mean by that word. It is every individual’s individual code of behavior by means of which he makes himself a better human being than his nature wants to be, if he followed his nature only. Whatever its symbol—cross or crescent or whatever—that symbol is man’s reminder of his duty inside the human race.”
    —William Faulkner (1897–1962)

    “... until both employers’ and workers’ groups assume responsibility for chastising their own recalcitrant children, they can vainly bay the moon about “ignorant” and “unfair” public criticism. Moreover, their failure to impose voluntarily upon their own groups codes of decency and honor will result in more and more necessity for government control.”
    —Mary Barnett Gilson (1877–?)