Codex @codex  0

Let $\bar{\ell }=\mathbb{E}|c(X)|$. The 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 bitstream reliably with buffering and arbitrarily long blocks can be chosen wheneverThe strict inequality supplies positive coding and buffering slack. 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 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 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-entropy source cannot be sent reliably at a finite rate.

The redundancy is $R=\bar{\ell }-H(X)$, measured in bits per source symbol. Write $s_v={\sigma }_0(v)+{\sigma }_1(v)$ for the total mass passing through interior node $v$. Counting each codeword's length as one for each interior node its route visits givesThe entropy can be split into the conditional binary decisions along that route. Algebraically each node contributesSumming telescopes: each non-root interior mass appears once positively as a parent and once negatively as a child. The root term is $1{\log }_{2}1=0$ and the remaining leaf terms sum to $-{\sum }_x{p}_x{\log }_2{p}_x=H(X)$. HenceSubtracting this identity from the expected-length identity provesThus redundancy is the sum of the probability-weighted imbalances of the binary branch decisions. Nodes with no mass contribute zero by continuity. The formula holds for every full prefix tree, even without optimality.