An input sequence consists of two symbols, each independently and randomly chosen from a set of symbols with known associated probabilities. Each symbol is independently encoded using a prefix code that minimizes the expected codeword length. Is it possible to reduce the expected total length of codewords by using instead of this code a prefix code where the symbols are ordered pairs of the original symbols?

  • $\begingroup$ Would this be equivalent to having two concatenated encoders? My (quick) guess is that either it can't be done or the gains will be small. Shannon says that the big gains are obtained by looking at larger sequences of uncoded symbols, not by concatenating encoders. $\endgroup$ – MBaz Apr 8 '19 at 14:55
  • $\begingroup$ @MBaz I reworded the question. I did not mean concatenation. Even small gains would be of interest! $\endgroup$ – Olli Niemitalo Apr 8 '19 at 17:42
  • $\begingroup$ The answer then is yes, per Shannon's source coding theorem. In fact, to get good compression you have to take $N$ of the original symbols, with large $N$; taking pairs will buy you a little bit extra compression, but not much. $\endgroup$ – MBaz Apr 8 '19 at 18:28

A simple example: consider a source $S = \lbrace 0, 1 \rbrace$ with probabilities $\lbrace 0.9, 0.1\rbrace$.

If you take one symbol at a time, no compression is possible: you need one bit per symbol.

Taking two symbols at a time, compression is possible. Now you have a source $S_2 = \lbrace 00, 01, 10, 11 \rbrace$ with probabilities $\lbrace 0.81, 0.09, 0.09, 0.01 \rbrace$. A possible encoding is:

Message | Codeword
00      | 0
01      | 10
10      | 110
11      | 111

Here, the average number of bits per message from source $S$ is $(1 \cdot 0.81 + 2 \cdot 0.09 + 3 \cdot 0.09 + 3 \cdot 0.01)/2 = 0.645$. It is clear, however, that by having only four combinations, the prefix code is not as short as it could be -- for example, $01$ and $10$ should have codewords of the same length, which in turn should be shorter than the codeword for $11$. If you group more $S$ messages, then you have more room for optimizing the code.

Note that the entropy of $S$ is around $0.47$; this means that the code above is still far from optimal. What Shannon says is that one may approach the entropy by increasing the number of symbols that are considered as input to the prefix code.

| improve this answer | |
  • $\begingroup$ Exactly what I was looking for. $\endgroup$ – Olli Niemitalo Apr 9 '19 at 4:25

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.