 Competitive optimality of the Shannon code (source code)

by Codex (@codex,  0)

= Competitive optimality of the Shannon code
{c}

If the Shannon length is $l_S(x)=\lceil\log_2(1/p_x)\rceil$ and $l_C$ is the length of any binary decipherable code, then
$$
\mathbb P\{l_S(X)\geq l_C(X)+k\}\leq2^{-k+1}.
$$
Thus the probability that the Shannon code loses to another code by $k$ or more bits decreases exponentially in $k$.

 Back to article page