Is it possible to code with less bits than calculated by Shannon's source coding theorem?

Question

In information theory, Shannon's source coding theorem establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. Consider that we have data generated by source.It's A B A B C C C C A B C C A B A B C C C C A B C C C C A B A B C C If I calculate the total number of bits required to encode this data efficiently, it will be 48bits. I think there is a more efficient way but it's not uniquely decodable. Is it possible to code with less bits than Shannon's source coding theorem? Can it be a uniquely decodable code?

Answer 1

The source coding theorem tells us that, if $L = (l_1,l_2,\dots,)$ is the length distribution of a code satisfying Kraft inequality (unique decodability) $\sum_i 2^{-l_i}\le 1$, then $\mathbb{E}[L] \ge H(X)$ with equality iff $p_i = 2^{-l_i}$, i.e., iff $P=(p_i)$ is a dyadic probability distribution.

Hence one can not beat entropy unless compromises with unique decodability.

Answer 2

Is it possible to code with less bits than Shannon's source coding theorem? Can it be a uniquely decodable code?

Shannon's source coding theorem says that there is no uniquely decodable code that produces less than $H$ bits per symbol. So, the answer to the question is no. If you relax the restriction, of course you can perform better, but in practice a non-uniquely decodable code is rarely useful.

Bear in mind that the bound applies to the average code length. It's possible that for some particular message the code length is less than the entropy (an example: a source with probabilities $(1/2, 1/4, 1/8, 1/8)$ emits a long sequence of the most probable symbol)

Also bear in mind that the theorem applies to a source with given probabilities (known both at the coder and decoder sides). If that's not the case, and the probabilities are estimated from a single long message (as you seem to imply), then the length will be greater because you need to code/trasmit also the encoding tree to the receiver.