[:shannon's noiseless coding theorem:]
• For some code $f : W \to \Sigma^*$,
• Let $\text{avglength}(f)$ be the average length of a code word coming out of $f$, i.e. $\sum_{w \in W}P(w)\text{len}(f(w))$. (We are modelling $f$ as choosing words $w \in W$ at random)
• Then if $\text{avglength}(f)$ is minimal, then:
• $H(W)/\log_2(n) \leq \text{avglength}(f) < 1 + H(W)/\log_2(n)$
• Where $H$ gives the entropy of a word set
• Where $n$ is the number of characters in the output alphabet
• Note that by log rules, $H(W)/\log_2(n)$ is basically the base-$n$ entropy of $W$
• This is proven using Kraft-McMillan
__Referenced by:__