= Solution
Let $\bar\ell=\mathbb E|c(X)|$. The <Huffman coding>[Huffman encoder] emits an average of $w\bar\ell$ binary digits per minute. Shannon's <noisy-channel coding theorem> states that for a <discrete memoryless channel> of capacity $K$, every information rate strictly below $K$ bits per use is achievable with error probability tending to zero as block length grows; rates above $K$ are not achievable for unrestricted messages.
Thus a channel code carrying the <Huffman coding>[Huffman bitstream] reliably with buffering and arbitrarily long blocks can be chosen whenever
$$
\boxed{rK>w\bar\ell,\qquad r>\frac{w\bar\ell}{K}}.
$$
The strict inequality supplies positive coding and buffering slack. <Huffman codeword length bounds>[Huffman's expected-length bound] is $H(X)\le\bar\ell<H(X)+1$ for a nontrivial finite source. Therefore the simpler bound $r>w(H(X)+1)/K$ is sufficient without knowing its exact Huffman lengths.
Distinguish this bitstream construction from the absolute source-channel limit. The <Shannon's source coding theorem>[noiseless source coding theorem] permits long source blocks to be compressed to any rate above $H(X)$ bits per source symbol, with arbitrarily small overhead. Together with channel coding, this gives the sharper limiting requirement $rK>wH(X)$; $rK<wH(X)$ is impossible by the source-channel converse. Further compression can exploit <redundancy of a binary prefix code>[redundancy] remaining in a single-symbol Huffman stream, so $w\bar\ell/K$ need not be the universal minimum channel symbol rate. At $K=0$ a positive-<Shannon entropy>[entropy] source cannot be sent reliably at a finite rate.
Back to article page
