1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – adfriedman Nov 23 '17 at 19:28
  • $\begingroup$ 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? $\endgroup$ – Kees Til Nov 23 '17 at 20:25
1
$\begingroup$

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.

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

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.