We define a $D$-ary Fano code based on a natural generalization of the splitting criterion of the binary Fano code to the case of $D$-ary code. We show that this choice allows for an efficient computation of the code tree and also leads to a strong guarantee with respect to the redundancy of the resulting code: for any source distribution p = (p_1, ..., p_n) 1) for D = 2, 3, 4, the resulting code satisfies L - H_D(p) \leq 1 - p_{min}, (*) where L is the average codeword length, p_{min} = min_i p_i and $H_D(\p) = \sum_{i=1}^n p_i \log_D \frac{1}{p_i}$ (the $D$-ary entropy); 2) inequality (*) holds for every $D >= 2$ whenever every internal node has exactly $D$ children in the code tree produced by our construction. We also formulate a conjecture on the basic step applied by our algorithm in each internal node of the code tree, that, if true, would imply that the bound in (*) is actually achieved for all $D \geq 2$ without the restriction of item 2).


Ferdinando Cicalese

University of Verona

Eros Rossi

University of Verona

Session Chair

Marcelo Weinberger

Center for Science of Information