# Word lengths of optimal binary code

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?

• 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. Feb 1, 2016 at 12:36
• 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. Feb 1, 2016 at 13:02
• 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. Feb 1, 2016 at 13:37

$$\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.$$
• 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? Feb 1, 2016 at 15:54