Source coding and Entropy

Question

Hell people,

I have a small question I came by , but I am not quite sure about the right approach to it.

Suppose that we have a source that transmits 5 symbols. We have two cases.

• When all symbols got the same chance.

and

• When one symbol got 1/2 chance and the rest got the same chance.

Question: In which of the above two case does the source coding works better and why?

Intuitively, I feel that in second case, source coding works better.

My attempt to justify this, is through Shannon's entropy! (though I am not sure if I am correct!)

Case1 entropy would be: H1= log2(5) = 2.32 bits/symbol

Case2 entropy: H2= 1/2log2(2) + 1/8log2(8)*4 = 2bits/symbol.

In case 2 , we know more info about the source and therefore we need less bit to represent it.

Any opinions on this? Cheers!

Answer 1

Your answer is probably the desired answer. A really pedantic answer might observe that the term "source coding" doesn't constrain the code to be sensibly designed, so it's possible to design a code for the first which is optimal and for the second which is highly wasteful.

Answer 2

A uniform source is incompressible - we know the rate of a source code is lower bounded by the entropy (and by coding over longer block lengths under some conditions on the source, we approach the entropy of the source). Thus, you can't compress the first source further than log(5) bits per symbol.

On the other hand, the second source is not uniform (so its entropy is less than log(5)) so by coding over longer and longer block lengths, you can achieve a rate lower than log(5) bits per symbol.