Shannon's noiseless coding theorem

'''Shannon's noiseless coding theorem''' places an upper and a lower bound on the minimal possible expected length of codewords as a function of the [[mathematical entropy|entropy]] of the input word (which is viewed as a [[random variable]]) and of the size of the target alphabet. ==Shannon's statement== Let ''X'' be a random variable taking values in some finite alphabet $\backslash Sigma\_1$ and let ''f'' be a decipherable code from $\backslash Sigma\_1$ to $\backslash Sigma\_2$ where $|\backslash Sigma\_2^*|=a$. Let ''S'' denote the resulting wordlength of ''f(X)''. If ''f'' is optimal in the sense that it has the minimal expected wordlength for ''X'', then : ==Proof== Let $s\_i$ denote the wordlength of each possible $x\_i$ ($i=1,\backslash ldots,n$). Define $q\_i\; =\; a^\{-s\_i\}/C$, where ''C'' is chosen so that $\backslash sum\; q\_i\; =\; 1$. Then : where the second line follows from [[Gibbs' inequality]] and the third line follows from [[Kraft's inequality]]: $C\; =\; \backslash sum\_\{i=1\}^n\; a^\{-s\_i\}\; \backslash leq\; 1$ so $\backslash log\; C\; \backslash leq\; 0$. For the second inequality we may set :$s\_i\; =\; \backslash lceil\; -\; \backslash log\_a\; p\_i\; \backslash rceil$ so that : and so :$a^\{-s\_i\}\; \backslash leq\; p\_i$ and :$\backslash sum\; a^\{-s\_i\}\; \backslash leq\; \backslash sum\; p\_i\; =\; 1$ and so by Kraft's inequality there exists a prefix-free code having those wordlengths. Thus the minimal ''S'' satisfies : {{FromWikipedia}} [[Category: Quantum Information Theory]]