Let's say I have an alphabet $$\Sigma = \{A, B, C, D, E\}$$

with probabilities $$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$

I know that the entropy then is: $$H(\Sigma) = 3 \cdot 0.25 \cdot \log 4 + 2 \cdot 0.125 \cdot \log 8 = 2.25.$$

My question now is: What does this mean in relation to the lower limit of compression? How many bits will I at least need to compress a text that consists of the above alphabet?

  • $\begingroup$ According to Shannon's source coding theorem, the entropy of a source is the optimal rate of compression. The theorem gives both an upper bound and a lower bound. $\endgroup$ Apr 22, 2020 at 12:04
  • $\begingroup$ So I would need min. 2.25 bits per character? $\endgroup$
    – user119620
    Apr 22, 2020 at 12:05
  • $\begingroup$ en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem $\endgroup$ Apr 22, 2020 at 12:07
  • $\begingroup$ (Keep in mind that Shannon presumes independent distribution: not given in many applications.) $\endgroup$
    – greybeard
    Apr 22, 2020 at 16:52

1 Answer 1


The idea is to decode the more frequently used symbols with less number of bits than the less used ones

So ur example means we can compress more if we decode A, B, C in less bits than E, D rather than equiprobable decoding By Huffman Coding A, B, C is represented by 2 bits (that's log 4); while D, E take 3 bits (log 8) This way ur expected coding size is minimal (2.25* text length) because u expect ur file to have 0.25 of its characters as A,... 0.125 as E,...

I hope this makes it clear...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.