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$
$\endgroup$
3
asked Apr 8, 2019 at 14:31
-
$\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$– MBazCommented Apr 8, 2019 at 14:55
-
$\begingroup$ @MBaz I reworded the question. I did not mean concatenation. Even small gains would be of interest! $\endgroup$– Olli NiemitaloCommented Apr 8, 2019 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$– MBazCommented Apr 8, 2019 at 18:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Exactly what I was looking for. $\endgroup$ Commented Apr 9, 2019 at 4:25