We study the redundancy of D-ary Fano source codes. We show that a novel splitting criterion allows to prove a bound on the redundancy of the resulting code which sharpens the guarantee provided by Shannon's classical result for the case of an optimal code. In particular we show that, for any D ≥ 2 and for every source distribution p = p_1,… ,p_n, there is a D-ary Fano code that satisfies the redundancy bound L-H_D(p)≤1-p_(min), (1) where, L- denotes the average codeword length, p_(min) = min_ip_i, and H_D(p) = -Σ_(i=1)~n p_i log_D(p_i) is the D-ary entropy of the source. The existence of D-ary Fano codes achieving such a bound had been conjectured in [ISIT2015], where, however, the construction proposed achieves the bound only for D = 2,3,4. In [ISIT2020], a novel construction was proposed leading to the proof that the redundancy bound in (1) above also holds for D = 5 (and some other special cases). This result was attained by a dynamic programming based algorithm with time complexity O(Dn) (per node of the codetree). Here, besides proving that the redundancy bound in (1) can be achieved, unconditionally, for every D ＞ 3, we also significantly improve the time complexity of the algorithm building a D-ary Fano code tree achieving such a bound: We show that, for every D ≥ 4, a D-ary Fano code tree satisfying (1) can be constructed by an efficient greedy procedure that has complexity O(D log_2 n) per node of the codetree (i.e., improving from linear time to logarithmic time in n).
展开▼
