3
$\begingroup$

Given an optimal binary code (ie the expected word length if as small as possible while the code is still decipherable) with word lengths $s_1, \ldots,s_m$, I'd like to show the following inequalities:

$$m\log m\leq s_1+\ldots+s_m\leq(m^2+m-2)/2$$

The first inequality basically says the average word length (not: expected word length) should be at least $\log m$ which seems very reasonable to me, no matter if the code is optimal or not. But how can I formally proof it?

For the second inequality I need the optimality property I suppose but I don't know how to approach it. Can someone give me a hint please?

$\endgroup$
3
  • 1
    $\begingroup$ Is $m$ the number of different symbols you want to encode, i.e., is it the alphabet size? How do you define the average word length? In any case, I would expect that the upper bound is $m \cdot \lceil \log m\rceil$, since you can always use a code with $\lceil \log m\rceil$ bits for each word. $\endgroup$
    – Bernhard
    Feb 1, 2016 at 12:36
  • $\begingroup$ We have $m$ messages each of which is encoded by a binary codeword. The codeword for the $i$-th message has length $s_i$. Each message is sent with a certain probability, so a block code where each codeword has length $\lceil\log m\rceil$ is unlikely to be optimal. By average I just meant $(s_1+\ldots+s_m)/m$ as opposed to the expected word length $\sum p_is_i$ which our code actually minimises. $\endgroup$
    – akkarin
    Feb 1, 2016 at 13:02
  • 1
    $\begingroup$ I see, thanks for the clarification. Yes, $m\cdot \lceil \log m\rceil$ will not be optimal, but it is a uniquely decodable code, so it will be an upper bound. For large $m$, this upper bound will be better than your bound depending on $m^2/2$, right? Your lower bound is right, I guess. I will write an answer. $\endgroup$
    – Bernhard
    Feb 1, 2016 at 13:37

1 Answer 1

0
$\begingroup$

The lower bound is correct. Looking for the average word length is equivalent to assuming that all code words occur with equal probability. Then, a lower bound on the expected word length (which equals the average word length now) is the entropy of the code. Since all code words are equally probably, you get

$$ \log m \le \frac{1}{m}\sum_{i=1}^m s_i. $$

Similarly, every word can be enumerated by a binary string of length $\lceil \log m\rceil$ (the ceiling operation is used to get integer length). This gives the upper bound

$$ \frac{1}{m}\sum_{i=1}^m s_i \le \lceil \log m\rceil.$$

$\endgroup$
4
  • $\begingroup$ Lower bound: You implicitly use the fact that the average word length of an optimal code is minimal if the probabilities are equal. Is that obvious or does it require further reasoning? Upper bound: Your bound is definitely better for big $m$ but what about small $m$? Is my bound false? $\endgroup$
    – akkarin
    Feb 1, 2016 at 15:54
  • $\begingroup$ The lower bound is not obvious, but well-known. It is essentially a consequence of the fact that relative entropy is non-negative. You will find details in the data compression chapter of Cover and Thomas' book "Elements of Information Theory". I'm not sure if your upper bound is wrong. How did you get this result? $\endgroup$
    – Bernhard
    Feb 2, 2016 at 15:25
  • $\begingroup$ I'll have a look at that! I'm pretty sure I saw the upper bound in a book, I can't find it right now. $\endgroup$
    – akkarin
    Feb 2, 2016 at 18:32
  • $\begingroup$ This answer is incorrect. An optimal code minimises expected word length across all decipherable codes, but it doesn't necessarily minimise the sum of the word lengths. It depends on the probabilites of the messages. For example, doing Huffman coding on the probabilites 0.7, 0.1, 0.1, 0.1 gives codewords 0, 11, 100, 101. This is optimal, but the sum of the codeword lengths is 9, which is more than m⌈logm⌉=8 , which is the sum of the word lengths of the block code 00, 01, 10, 11. Minimising expected word length is a very different thing to minimising the sum of the word lengths. $\endgroup$
    – jeff honky
    Jan 29 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .