Technical Program

Paper Detail

Paper IDO.1.4
Paper Title On D-ary Fano Codes
Authors Ferdinando Cicalese, Eros Rossi, University of Verona, Italy
Session O.1: Data Compression
Presentation Lecture
Track Source Coding
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract 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).

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!