A Gallager-Type Redundancy Bound for Binary Shannon-Fano Coding
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\tfrac12$ and on a subinterval below $\tfrac13$, and gives the cap $R<\tfrac52-\tfrac56\log_2 5=0.5651$ for $p_1<\tfrac12$. 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.04192
curl -X POST /api/v1/records/arxiv/2607.04192/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.04192/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'