# How to prove that shannon coding is pre-fix free.

Here is the definition of shannon coding: https://en.wikipedia.org/wiki/Shannon_coding

I intuitively tried a few distributions and it seemed to work fine. furthermore I tried looking at the relation between the $l_i$ and $p_i$ but seemed to get stuck. Since binary strings of fractions can be defined as $\sum 2^{-k}$, i tried to compare the $p_i$ and see how the binary strings would look like and it seems that these strings only grow in length. Any tips on how to tackle this problem?

Kees

• Where's the confusion? The relation is given in the linked page by $$l_i = \lceil -\log(p_i)\rceil$$ so the smaller the probability of a given symbol the longer the binary representation and conversely, more likely symbols have shorter representations. – adfriedman Nov 23 '17 at 19:28
• but how do you know for sure that for example there cant be some $s = s_1s_2 \dots s_n$ and some $t = t_1 \dots t_m$ such that $s+t = k$, where $k$ is in the codebook? – Kees Til Nov 23 '17 at 20:25

I'll give you the idea, so you can formalize it.

Let $m_i = \sum_{k=1}^{i-1} p_i$, the accumulated probabilities. Let's assume some codeword is, say, $c_i=1010$. We ask ourselves: could it happen that some next codeword $c_j$ with $j>i$ has this $c_i$ as prefix? Say, could it happen that $c_{i+1}=10101....$ ? This could only happen if $m_{i+1}-m_i < 0.0001 = \frac{1}{16}$.

But $m_{i+1}-m_i =p_i$ And we know that, $l_i=4 =\lceil -\log(p_i)\rceil \implies -\log(p_i) \le 4 \implies p_i \ge \frac{1}{16}$

Hence that's impossible.

• i did not think about using a contradiction thanks you :D – Kees Til Nov 24 '17 at 15:07