A Gallager-Type Redundancy Bound for Binary Shannon-Fano Coding

Abstract

Krajči, Liu, Mikeš, and Moser proved in 2015 that the redundancy of binary Shannon-Fano coding is always below one bit. We sharpen this to a bound depending on the largest source probability $p_1$: an explicit seven-piece envelope $R<f(p_1)$. The envelope equals the exact supremum of $R$ given $p_1$ for every $p_1\ge \frac{1}{2}$ and on a subinterval below $\frac{1}{3}$, and gives the cap $R<\frac{5}{2}-\frac{5}{6}{\log }_{2}5=0.5651$ for $p_1<\frac{1}{2}$. It is the first $p_1$-dependent redundancy bound for Fano codes. The method is more sophisticated than the approach typical for Huffman codes: Fano trees are built top-down by contiguous balanced splits and lack the sibling property. From the $R<1$ theorem the rest follows from the Fano recursion, through a min-corrected affine potential and a no-burial lemma. Every scalar inequality in the proof reduces to a comparison of integer powers.

16 pages