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

Q: What redundancy is analyzed for binary Shannon–Fano coding?

Redundancy is defined as the expected codeword length minus the entropy, R = E[ℓ] − H(p).

Q: How does the paper improve the known bound R < 1?

It derives a p1-dependent seven-piece envelope R < f(p1), tightening the redundancy estimate based on the largest symbol probability p1, including an explicit cap for p1 < 1/2.

Q: What structural difficulty prevents transferring Huffman-type p1 bounds directly to Fano codes?

Binary Shannon–Fano trees are built top-down using contiguous balanced splits and do not satisfy the sibling property, so Huffman block estimates do not carry over to the Fano recursion.

Jul 16, 2026

Upload by Violet

Kraji, Liu, Mikeš, and Moser showed that the redundancy of binary Shannon-Fano coding is always below one bit. This work sharpens the bound using the largest source probability p1, giving an explicit seven-piece envelope R < f(p1) whose value matches the exact supremum of R for every p1 ≥ 1/2 and on a subinterval below 1/3. For p1 < 1/2, the bound specializes to R < 2 − (5/6)log2(5) = 0.5651. It also provides a first p1-dependent redundancy bound for Fano codes.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Introduction

Contributions

Shannon–Fano Coding and the Fano Recursion

A Gallager-Type Redundancy Bound for Binary Shannon-Fano Coding Kamila Szewczyk arXiv :2607 .04 192v 1 [ cs .IT] 5 Jul 2026 Abstract—Kraji, 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 p1 : an explicit seven-piece envelope R < f(p1). The envelope equals the exact supremum of R given p1 for every p1 ≥ ~~1~~2 and on a subinterval below ~~1~~3, and gives the cap R < ~~5~~2 − ~~5~~6 log2 5 = 0 .5651 for p 1 < ~~1~~2. It is the first p1-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 therest 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. Index Terms—Shannon-Fano coding, source coding, redundancy, prefix codes, Huffman codes, entropy. I. INTRODUCTION BINARY Shannon–Fano coding [1], [2] sorts the source symbols by probability and recursively splits the sorted list into two contiguous blocks of as nearly equal probability as possible, one code bit per split. Unlike the bottom-up Huffman construction [3] it need not be optimal. Because the blocks are contiguous the code preserves the sorted order, so it is an alphabetic code [4], whose optimum is the Hu–Tucker code [5] . Following [6] we reserve the name Shannon–Fano for this top-down split code, as opposed to the Shannon–Fano–Elias code. The efficiency of a code is its redundancy R = E [ℓ]−H(p), the expected codeword length minus the entropy. For Huffman codes, R has long been bounded in terms of the largest symbol probability p 1. Gallager [7] introduced the sibling property and proved R < p 1 + 0 .086, reproved more simply by Ye and Yeung [8]; Johnsen [9] improved the estimate for p 1 ≥ 0.4; and Capocelli, Giancarlo, and Taneja [10], Capocelli and De Santis [11], [12], Montgomery and Abrahams [13], and Manstetten [14] determined the exact worst-case Huffman redundancy as a function of p 1. All of these use the sibling property of Huffman trees, which orders the nodes by weight in sibling pairs. Fano codes have been analysed less. Rissanen [15] and Horibe [16] bounded weight-balanced trees, of which a Fano tree is one (H ≤ W ≤ H + 3, later sharpened), and Nakatsu [17] bounded the redundancy of alphabetic codes; Kraji, Liu, Mikeˇs, and Moser [18] proved the universal estimate R < 1 for Fano coding. A p1-dependent bound of Gallager type has been missing. The obstruction is structural: a Fano tree is built K. Szewczyk is with the Algorithmic Bioinformatics group, Saarland University, Saarbr¨ucken, Germany (e-mail: [szewczyk@cs.uni-saarland.de](szewczyk@cs.uni-saarland.de)). top-down by contiguous balanced cuts and does not satisfy the sibling property, so the subtrees in the recursion need not be near-uniform and the Huffman block estimates do not carry over. Contributions We prove the first p 1-dependent redundancy bound for binary Shannon–Fano coding: • a seven-piece envelope R < f (p1 ) (Theorem 1) that sharpens R < 1 [18] for every p 1 and gives the cap R < K = ~~5~~2 − ~~5~~6 log2 5 = 0 .5651 for p 1 < ~~1~~2 ; • tightness: the envelope is the exact supremum of R given p 1 on [ ~~1~~2 , 1) and on [b2 , ~~1~~3 ) (Propositions 1 and 7); • a proof from the Fano recursion alone, using the mincorrected potential Ψ = p 1 + C − λpn and a no-burial lemma that puts the largest symbol at depth two on [ ~~1~~4 , ~~1~~3) ; • a reduction of every scalar inequality in the proof toa comparison of integer powers, so the argument is elementary and self-contained (Appendix E) . Organization Section II fixes the construction and notation. Section III states the envelope and its tightness. Section IV outlines the pro

FAQs

What redundancy is analyzed for binary Shannon–Fano coding?

Redundancy is defined as the expected codeword length minus the entropy, R = E[ℓ] − H(p).

How does the paper improve the known bound R < 1?

It derives a p1-dependent seven-piece envelope R < f(p1), tightening the redundancy estimate based on the largest symbol probability p1, including an explicit cap for p1 < 1/2.

What structural difficulty prevents transferring Huffman-type p1 bounds directly to Fano codes?

Binary Shannon–Fano trees are built top-down using contiguous balanced splits and do not satisfy the sibling property, so Huffman block estimates do not carry over to the Fano recursion.

Jul 16, 2026

Upload by Violet