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