2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You need a way to code multicharacter strings to do better. Your source has 8 occurences of the string AB and 8 occurences of the string CC. The catch is to compress it in the way that first defines these atoms. I don't know the theory too well, but Lempel-Ziv have such tools. $\endgroup$ – Jyrki Lahtonen Oct 14 '15 at 5:01
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ... and because the probabilities estimated from the relative frequencies are not the exact probabilities. $\endgroup$ – joriki Oct 15 '15 at 12:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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