Source Information Rate

The information rate of a Source is the infimum of all rates at which it is Reliably encodable

Lemma

The Source Information Rate of a Discrete Memoryless Source is at most the expected word length of an Optimal Code.

Proof

Let be an optimal code Let be codeword lengths when we encode Let Let

Then

by Weak Law of Large Numbers.

Now is injective, hence . Making larger if necessary, we can assume Taking logarithms

So the source is Reliably encodable at rate for all . Hence the information rate is at most .

Corollary

A Discrete Memoryless Source has information rate less than .

Proof

Shannon’s noiseless coding theorem

Proposition

The information rate of a Discrete Memoryless Source is at most .

Proof

Encode in blocks of size . Let etc. Then if has information rate , has information rate Apply the previous corollary:

to find so .