Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The source coding theorem says that information transfer with variable length code uses less bits and is equal to the entropy of the distribution. It also says that there is no code that uses lesser number of bits ( or does it? Have I misunderstood this). My question is, there is obviously a way to transmit the same information using lesser number of bits than the entropy. For example:

Let

$P(x) = \frac{1}{2}, \frac{1}{4}, \frac{1}{16}, \frac{1}{32}, \frac{1}{64},\frac{1}{64}$ respectively for x= 1,2,3,4,5,6.

If by using source coding theorem, a variable code of length = $log_2(p(x))$ is used, then

the average bits used is $1*\frac{1}{2} + 2*\frac{1}{4} + 4*\frac{1}{16} + 5*\frac{1}{32} + 6*\frac{1}{64} + 6*\frac{1}{64}$ = 1.5938.

But obviously, there is a better way of doing this:

Just use the following codes: 0,1,10,11,100,101.

This definitely uses less bits on average ( bits $\lt 1.5938$). So what is the actual meaning of the source coding theorem?

share|improve this question
3  
How would you decode $100101$? As $baaf$ or $cacb$ or ...? –  Hagen von Eitzen Jun 4 '13 at 11:44

1 Answer 1

up vote 4 down vote accepted

The source coding theorem restricts to uniquely decodable codes, which in practice are the only useful codes.

To see that your code is not uniquely decodable, and hence practically useless, consider that you receive the sequence $01$ . You cannot know it that correspond to a concatenation of $0|1$ (two first symbols), or $01$ (third symbol).

Usually, one restricts even more the set of acceptable codes, by restricting to prefix codes. It can be shown that doing so one loses nothing (in terms of average length), and prefix codes are more practical to decode and more easy to analyze.

share|improve this answer
    
@PeterTaylor : Yes, now I think it's better. –  leonbloy Jun 4 '13 at 11:59
    
But I need to send only one symbol at a time. I don't have to send multiple symbols. Or maybe I do. Okay. I think I get it. –  SPRajagopal Jun 4 '13 at 12:49
    
@SPRajagopal, if you add a third symbol to separate the tokens then you have to adjust all of your stream entropy calculations upwards. –  Peter Taylor Jun 4 '13 at 13:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.